탐색(Search) 알고리즘

3.1 선형 탐색(Linear Search)

선형 탐색은 가장 기본적인 탐색 알고리즘으로, 배열이나 리스트와 같은 데이터 집합에서 원하는 값을 찾기 위해 처음부터 끝까지 차례대로 각 원소를 하나씩 비교합니다. 탐색 대상(키 값)이 배열의 첫 번째 원소에 있다면 한 번의 비교로 찾을 수 있지만, 배열의 마지막에 있거나 존재하지 않는 경우에는 모든 원소를 확인해야 하므로 비교 횟수가 최대가 됩니다. 선형 탐색은 정렬 여부에 상관없이 사용할 수 있으며, 구현이 매우 간단하고 직관적입니다. 하지만 데이터가 많아질수록 효율이 떨어지므로, 소규모 데이터나 정렬되어 있지 않은 데이터에서 주로 사용됩니다. 최악의 경우 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)입니다. 탐색에 실패하면 -1이나 NULL 등으로 결과를 반환합니다.

3.2 이진 탐색(Binary Search)

이진 탐색은 정렬된 배열이나 리스트에서만 사용할 수 있는 매우 효율적인 탐색 알고리즘입니다. "분할 정복(divide and conquer)" 원리를 이용하여, 탐색 구간을 반씩 줄여가며 원하는 값을 찾습니다. 먼저 배열의 중간값과 찾고자 하는 값을 비교하고, 만약 중간값이 찾는 값보다 크면 왼쪽 절반에서, 작으면 오른쪽 절반에서 다시 탐색을 반복합니다. 이 과정을 값이 발견되거나 탐색 구간이 사라질 때까지 반복합니다. 이진 탐색의 시간 복잡도는 O(log n)으로, 선형 탐색에 비해 매우 빠릅니다. 이진 탐색은 반복문(iterative)이나 재귀(recursive)로 구현할 수 있습니다. 단, 데이터가 반드시 정렬되어 있어야 하며, 정렬되지 않은 경우에는 사용할 수 없습니다.

3.3 BFS(너비 우선 탐색, Breadth-First Search)

너비 우선 탐색(BFS)은 트리나 그래프에서 사용되는 탐색 알고리즘으로, 루트(혹은 시작 노드)에서 시작하여 인접한 노드들을 먼저 모두 방문한 후, 그 다음 레벨의 노드들을 방문하는 방식으로 탐색을 진행합니다. BFS는 큐(Queue) 자료구조를 활용하여, 방문해야 할 노드들을 순서대로 저장하고, 앞에서부터 하나씩 꺼내어 인접한 노드를 차례로 방문합니다. 이 방식은 모든 노드를 레벨(거리) 순서대로 방문하기 때문에, 최단 경로(특히 가중치가 없는 그래프에서)를 찾을 때 매우 유용합니다. BFS는 그래프가 연결되어 있지 않은 경우에도 모든 노드를 방문할 수 있도록 반복적으로 시작점을 바꿔가며 수행할 수 있습니다. 시간 복잡도는 O(V+E) (V: 정점 수, E: 간선 수)이며, 공간 복잡도는 방문 여부를 저장하는 배열과 큐의 크기에 비례합니다.

3.4 DFS(깊이 우선 탐색, Depth-First Search)

깊이 우선 탐색(DFS)은 트리나 그래프에서 한 경로를 따라 가능한 한 깊게 탐색하다가 더 이상 갈 곳이 없으면, 이전 분기점으로 돌아가서 다른 경로를 탐색하는 방식입니다. DFS는 스택(Stack) 자료구조를 활용하거나, 재귀 호출을 통해 구현할 수 있습니다. 시작 노드에서 출발하여, 방문하지 않은 인접 노드를 따라 계속 이동하다가, 더 이상 방문할 노드가 없으면 스택에서 꺼내어(혹은 재귀적으로 복귀하여) 이전 노드로 돌아갑니다. 이 과정을 모든 노드를 방문할 때까지 반복합니다. DFS는 경로의 존재 여부, 사이클 탐지, 연결 요소 찾기 등 다양한 문제에 활용됩니다. 시간 복잡도는 O(V+E)이며, 공간 복잡도는 재귀 호출 깊이(최대 V) 또는 스택의 크기에 비례합니다.