탐색 알고리즘과 그래프

탐색 알고리즘

방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘을 말한다. 일반적으로 탐색 알고리즘이라고 하면 트리 검색 알고리즘을 떠올리는 경우가 많으나, 탐색 알고리즘은 이론적인 정의는 다양한 범위를 포함한다.

 

순차 탐색(Linear Search)

배열의 처음부터 끝까지 하나씩 확인하여 찾는 방법

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 예제
numbers = [3, 7, 1, 9, 4, 6, 2]
print(f"순차 탐색 결과: {linear_search(numbers, 9)}")

 

이진 탐색(Binary Search)

정렬된 배열에서 중간값과 비교하여 탐색 범위를 절반씩 줄여가며 찾는 방법

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

# 예제
sorted_numbers = [1, 2, 3, 4, 6, 7, 9]
print(f"이진 탐색 결과: {binary_search(sorted_numbers, 6)}")

 

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

그래프에서 시작 노드부터 가까운 노드들을 먼저 탐색하는 방법

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    result = []
    
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            result.append(node)
            
            # 인접 노드들을 큐에 추가
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
    
    return result

# 예제 그래프
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(f"BFS 탐색 결과: {bfs(graph, 'A')}")

 

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

그래프에서 시작 노드부터 가능한 깊이까지 탐색한 후 다른 경로를 탐색하는 방법

 def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    result = [start]
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))
    
    return result

# 스택을 사용한 반복적 DFS
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node)
            
            # 인접 노드들을 스택에 추가 (역순으로 추가)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result

print(f"DFS 탐색 결과 (재귀): {dfs(graph, 'A')}")
print(f"DFS 탐색 결과 (반복): {dfs_iterative(graph, 'A')}")