탐색(Search)
- 다수의 데이터 속 원하는 데이터를 찾는 과정
- 그래프 트리 등의 자료구조 안에서 사용하는 대표적인 탐색 알고리즘으로 BFS/DFS가 있다.
- BFS/DFS 탐색를 이해하려면 기본 자료구조에 대한 사전 지식이 수반되어야 한다.
자료구조(Data Structure)
- 데이터를 표현/관리/처리 하기 위한 구조
- 스택 / 큐 / 덱 / 그래프 / 트리 등이 있다
오버플로(Overflow)
- 특정 자료구조의 수용 범위를 넘어섰을 때, 추가로 데이터를 삽입할 때 나타나는 연산 오류
- Over(넘쳐) + flow(흐르다) ->> 데이터가 너무 많아서 넘쳐 흘러 버린다.
언더플로(Underflow)
- 오버플로의 반대로, 데이터가 전혀 없는데 데이터를 삭제할 때 나타나는 연산 오류
스택(Stack)
- 박스 쌓기와 같은 구조
- 박스는 아래서부터 위로 차곡차곡 쌓고, 아래의 박스를 꺼내려면 위의 박스를 치워야만 한다.
- 선입후출(First in Last Out / FILO) -> 먼저 들어온게(선입), 나중에 나간다(후출)
- 파이썬 리스트의 append()와 pop() 함수를 사용하면 stack과 동일하게 사용할 수 있다.
큐(Queue)
- 마트의 대기 줄이나 도로의 터널을 생각해보자.
- 먼저 들어온 (대기한) 사람이 먼저 나가는(우선권을 가지는) 자료구조로 선입선출(First In First Out / FIFO)이다.
- 파이썬 collections 모듈의 deque 자료 구조를 사용하자 (스택과 큐의 장점 둘 다를 가짐)
재귀 함수(Recursive Function)
- 자기 자신을 다시 호출하는 함수
# 예시
def recursive_function():
print("나 불렀어?")
recursive_function()
recursive_function()
이 경우에는 "나 불렀어?"가 무한히 출력된다.
파이썬에서는 재귀함수의 무한 출력을 방지하기 위해 횟수 제한을 두고있다. (기본 1000회)
따라서 코드 시작에
import sys
sys.setrecursionlimit(횟수)를 삽입하여 필요에 따라 재귀함수의 출력 최대 횟수를 지정해주자.
하지만 애초에 재귀 함수를 사용할 때는 무한 출력이 발생하지 않도록, 종료 조건을 명시해주어야 한다.
컴퓨터 내부에서 재귀함수는 스택 자료구조를 이용한다.
따라서 가장 마지막에 호출된 재귀함수가 끝나야 순차적으로 앞선 호출이 완료되는 것이다.