탐색 알고리즘은 주어진 데이터에서 원하는 값을 찾는 방법을 의미합니다. 탐색 알고리즘에는 선형 탐색, 이진 탐색, 깊이 우선 탐색, 너비 우선 탐색 등이 있습니다.
선형 탐색
선형 탐색은 데이터를 순서대로 하나씩 비교하면서 원하는 값을 찾는 가장 간단한 방법입니다. 예를 들어, 1부터 10까지의 숫자가 저장된 배열에서 7을 찾으려면, 배열의 첫 번째 원소부터 마지막 원소까지 차례대로 7과 비교하면 됩니다. 선형 탐색은 구현이 쉽지만, 데이터의 크기가 커질수록 비교 횟수가 증가하여 시간 복잡도가 O(n)이 됩니다.
이진 탐색
이진 탐색은 데이터가 정렬되어 있을 때 사용할 수 있는 더 빠른 방법입니다. 이진 탐색은 데이터의 중간값과 원하는 값을 비교하면서 범위를 절반씩 줄여나가는 방법입니다.
이진 탐색은 데이터의 크기가 커져도 비교 횟수가 적게 증가하여 시간 복잡도가 O(log n)이 됩니다.
깊이 우선 탐색(Depth-First Search)
DFS는 그래프나 트리와 같은 자료구조에서 루트 노드부터 시작하여 모든 노드를 방문하는 방법입니다. DFS는 스택이나 재귀함수를 이용하여 구현할 수 있습니다.
코딩테스트에서 DFS를 사용해야 하는 문제 유형은 다음과 같습니다.
- 그래프의 연결성을 확인하거나 분리된 영역의 개수를 세는 문제
- 그래프의 경로를 찾거나 최단 경로를 구하는 문제
- 백트래킹을 이용하여 가능한 모든 경우의 수를 탐색하는 문제
- 그리드 형태의 맵에서 방문할 수 있는 칸의 개수를 세거나 최대 영역을 구하는 문제
- 트리의 깊이나 높이를 구하거나 트리의 순회 방식을 구하는 문제
DFS를 사용하는 문제 유형은 많습니다. 주의해야 할 점은 재귀적인 특성을 가지기 때문에 문제의 조건에 따라 적절한 종료 조건 및 방문 여부를 체크하는 로직이 반드시 필요합니다. 또한 모든 노드를 방문하기 때문에 시간 복잡도가 높을 수 있어 최적화 기법을 적용할 수 있으면 좋습니다.
예제
너비 우선 탐색(BFS)
BFS는 그래프나 트리와 같은 자료구조에서 노드를 방문하는 방법 중 하나로, 시작 노드부터 인접한 노드들을 모두 방문한 후에 다음 깊이의 노드들을 방문하는 순서로 진행됩니다. BFS는 큐(Queue)라는 자료구조를 사용하여 구현할 수 있습니다. 큐는 선입선출(FIFO)의 원칙을 따르는 자료구조로, 먼저 들어온 데이터가 먼저 나가는 구조입니다. BFS 동작 과정은 다음과 같습니다.
코딩테스트에서 BFS를 사용해야 하는 문제 유형은 다음과 같습니다.
- 최단 경로 문제 : BFS는 시작 노드로부터 각 노드까지의 최단 거리를 구할 수 있습니다. 예를 들어, 미로 탈출 문제나 소수 경로 문제와 같은 문제에서 BFS를 사용할 수 있습니다.
- 연결 요소 문제 : BFS는 그래프가 여러 개의 연결 요소로 나뉘어져 있을 때, 각 연결 요소에 속하는 노드들을 구분할 수 있습니다. 예를 들어, 섬의 개수 문제나 바이러스 문제와 같은 문제에서 BFS를 사용할 수 있습니다.
- 최소 신장 트리 문제 : BFS는 그래프의 모든 노드들을 연결하는 최소 비용의 트리를 구할 수 있습니다. 예를 들어, 네트워크 연결 문제나 전기가 부족한 도시 문제와 같은 문제에서 BFS를 사용할 수 있습니다.
예제
코딩테스트에서 탐색 알고리즘은 매우 중요한 주제입니다. 적절한 탐색 알고리즘을 선택하고 구현할 수 있어야만, 시간 제한 내에 문제를 풀 수 있습니다. 따라서 다른 종류의 탐색 알고리즘에 대해서도 공부하고 연습하는 것이 좋습니다.
