DFS/BFS

• 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야하며 스택과 큐, 재귀 함수에 대해 알아야한다.

• 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
• 스택, 큐는 두 핵심적인 함수로 구성된다.
  • 삽입(Push): 데이터를 삽입한다.
  • 삭제(Pop): 데이터를 삭제한다.
  • 오버플로(overflow): 데이터가 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생
  • 언더플로(underflow): 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 발생

스택

박스 쌓기에 비유할 수 있다. 선입후출(FILO) 혹은 후입선출(LIFO) 구조.

Python에서는 별도의 라이브러리를 사용할 필요가 없고 append(), pop()을 사용하면 된다.

stack = []
stack.append(5)
stack.append(3)
stack.pop()
print(stack) #[5]

큐

대기줄에 비유할 수 있다. 선입선출(FIFO) 구조.

Python에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용해야 한다.

deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다.

from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.popleft()
print(queue) #deque([2, 3])
queue.reverse()
print(queue) #deque([3, 2])

재귀 함수

• 재귀 함수(Recursive Function): 자기 자신을 다시 호출하는 함수

def recursive_function():
	print("재귀함수 호출")
	recursive_function()
recursive_function()
#무한히 출력되다가 RecursiveError: maximum recursion depth
#exceed while pickling an object 오류가 발생한다.

재귀 함수의 종료 조건

재귀 함수를 사용할 때에는 반드시 종료 조건을 명시해야 한다.