탐색은 많은 양의 데이터 중 원하는 데이터를 찾는 과정으로 그래프나 트리 등의 자료구조에서 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있고, 이를 확실히 이해하려면 스택과 큐가 뭔지 알아야 한다.
스택과 큐의 핵심 함수는 삽입(push)과 삭제(pop)다. 따라서 항상 오버플로와 언더플로를 고려해야 한다.
- overflow : 저장 공간을 벗어나 데이터가 넘쳐흐르는 상황
- underflow : 데이터가 들어 있지 않은 상태에서 삭제 연산을 수행하는 상황
Stack
- LIFO (Last In First Out) : 후입선출로 접시를 쌓는 모습을 연상하면 된다. 깨끗이 닦은 접시를 쌓아두면 맨 위 접시부터 사용한다.
Queue
- FIFO (First In First Out) : 선입선출로 식당에 줄 서는 모습을 연상하면 된다. 가장 먼저 줄 선 사람부터 차례대로 식당에 들어간다.
Recursive function
재귀 함수는 자기 자신을 다시 호출하는 함수로 수학의 점화식과 비슷하다. 팩토리얼 코드를 살펴보자.
n이 1일 때 1을 반환하는 조건을 주지 않는다면 에러가 발생하므로 종료 조건을 꼭 명시해야 한다.
DFS / BFS Algorithm
DFS (Depth-First Search), 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택을 이용하며 아래와 같이 동작한다. (스택을 이용하기 때문에 재귀로도 구현 가능하다.)
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 삽입하고 방문 처리. 방문하지 않은 인접 노드가 없는 경우 스택에서 최상단 노드를 꺼냄
- 2의 과정을 더 이상 수행할 수 없을 때까지 반복
반면 가까운 노드부터 탐색하는 BFS (Breath-First Search) 알고리즘은 큐를 이용하여 동작한다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입
- 2의 과정을 더 이상 수행할 수 없을 때까지 반복
참고
- 이것이 취업을 위한 코딩 테스트다