1. DFS (깊이 우선 탐색, Depth-First Search)
-
사용: 그래프 탐색, 백트래킹, 경로 찾기
-
특징: 한 경로를 끝까지 탐색한 후 다른 경로로 넘어가는 방식
-
응용 문제: 미로 찾기, 섬의 개수 세기, 그래프에서의 경로 탐색
def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(graph, i, visited)
2. BFS (너비 우선 탐색, Breadth-First Search)
-
사용: 그래프 탐색, 최단 경로 탐색
-
특징: 가까운 노드부터 탐색하는 방식 (큐를 사용)
-
응용 문제: 최단 경로 문제, 미로 찾기
from collections import deque def bfs(graph, start, visited): queue = deque([start]) visited[start] = True while queue: v = queue.popleft() print(v, end=' ') for i in graph[v]: if not visited[i]: queue.append(i) visited[i] = True
3. 이진 탐색 (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
4. 다익스트라 알고리즘 (Dijkstra's Algorithm)
-
사용: 가중치가 있는 그래프에서의 최단 경로 탐색
-
특징: 우선순위 큐(최소 힙)를 사용해 현재까지의 최단 경로를 계속 갱신하는 방식
-
응용 문제: 특정 노드에서 다른 노드까지의 최단 경로
import heapq def dijkstra(graph, start): distances = {node: float('inf') for node in graph} distances[start] = 0 queue = [(0, start)] while queue: current_distance, current_node = heapq.heappop(queue) if current_distance > distances[current_node]: continue for adjacent, weight in graph[current_node].items(): distance = current_distance + weight if distance < distances[adjacent]: distances[adjacent] = distance heapq.heappush(queue, (distance, adjacent)) return distances
5. 동적 계획법 (Dynamic Programming, DP)
-
사용: 작은 문제를 풀고, 그 결과를 저장해서 큰 문제를 푸는 방식
-
특징: 재귀적 접근과 메모이제이션을 사용해 중복 계산을 피함
-
응용 문제: 피보나치 수열, 배낭 문제, 최소 비용 경로
def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n]
6. 최소 신장 트리 (Minimum Spanning Tree, MST)
-
사용: 그래프에서 모든 정점을 연결하는 최소 비용의 트리 구하기
-
주요 알고리즘: Kruskal's Algorithm, Prim's Algorithm
-
응용 문제: 네트워크 연결, 도로 건설
-
크루스칼 알고리즘 (Kruskal's Algorithm):
- 간선을 정렬한 후 최소 비용으로 연결하는 방식 (Union-Find 사용)
def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x] def union(parent, a, b): rootA = find(parent, a) rootB = find(parent, b) if rootA < rootB: parent[rootB] = rootA else: parent[rootA] = rootB
7. 투 포인터 (Two Pointer)
-
사용: 배열에서 두 개의 포인터를 사용해 특정 조건을 만족하는 구간 찾기
-
특징: 양 끝에서 포인터를 이동시켜가며 문제 해결
-
응용 문제: 부분합 구하기, 특정 구간 찾기
def two_pointer(arr, target): left, right = 0, len(arr) - 1 while left < right: current_sum = arr[left] + arr[right] if current_sum == target: return (left, right) elif current_sum < target: left += 1 else: right -= 1 return None
8. 슬라이딩 윈도우 (Sliding Window)
-
사용: 고정된 크기 또는 가변적인 크기의 구간을 이동하면서 문제 해결
-
특징: 부분 합, 최대값/최소값을 구하는 문제에 적합
-
응용 문제: 최대 부분합 구하기, 문자열에서 특정 패턴 찾기
def sliding_window(arr, k): current_sum = sum(arr[:k]) max_sum = current_sum for i in range(k, len(arr)): current_sum += arr[i] - arr[i - k] max_sum = max(max_sum, current_sum) return max_sum
9. 유니온 파인드 (Union-Find)
-
사용: 그래프에서 연결된 컴포넌트를 찾는 알고리즘
-
특징: 집합을 합치고 연결 여부를 판단할 때 사용 (서로소 집합)
-
응용 문제: 사이클 판별, 네트워크 연결 여부 확인
def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x] def union(parent, a, b): rootA = find(parent, a) rootB = find(parent, b) if rootA != rootB: parent[rootB] = rootA
10. 백트래킹 (Backtracking)
-
사용: 가능한 모든 경우를 탐색하면서 조건을 만족하는 해를 찾는 방식
-
특징: 해를 찾다가 조건에 맞지 않으면 이전 단계로 돌아가는 방식
-
응용 문제: N-Queen 문제, 부분 집합 구하기
def backtracking(path, choices): if 조건에 만족: 결과 저장 return for choice in choices: if 조건에 맞는 choice: backtracking(path + [choice], choices)
