자료구조
탐색 : 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조이다.•
삽입 : 데이터를 삽입한다.
•
삭제 : 데이터를 삭제한다.
오버플로와 언더플로•
오버플로 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 즉, 저장 공간을 벗어나 데이터가 넘쳐 흐를때 발생한다.
•
언더플로 : 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행할 때 발생한다.
스택
먼저 들어온 데이터가 나중에 나가는 형식(선입후출) 의 자료구조 입니다. 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다.[예시 코드]
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.pop()
stack.append(1)
stack.append(4)
# 최상단 원소부터 출력
print(stack[::-1])
# output : [4,1,2,5]
# 최하단 원소부터 출력
print(stack)
# output : [5,2,1,4]
Python
복사
큐
먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다. 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.[예시 코드]
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.popleft()
queue.append(1)
queue.append(4)
# 먼저 들어온 순서대로 출력
print(queue)
# output : deque([2,1,4])
# 역순으로 바꾸기
queue.reverse()
# 나중에 들어온 원소부터 출력
print(queue)
# output : deque([4,1,2])
Python
복사
재귀함수
재귀함수(Recursive Function) 란 자기 자신을 다시 호출하는 함수를 의미합니다. 단순한 형태의 재귀 함수 예제def recursive_function() :
print('재귀함수를 호출합니다.')
recursice_function()
recursive_function()
Python
복사
•
‘재귀 함수를 호출합니다’ 라는 문자열을 무한히 출력합니다.
•
어느 정도 출력하다가 최대 재귀 깊이 초과 메세지가 출력됩니다.
재귀함수의 종료 조건재귀 함수를 문제 풀이에서 사용할 때에는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.
컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용한다.함수를 계속 호출 했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.
재귀함수 사용의 유의사항•
재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
(단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다.)
•
모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
•
재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
•
컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
◦
그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.