기본 개념 및 전제 지식
1. 유니온-파인드 (Disjoint Set Union)
유니온-파인드 자료구조는 서로소 집합을 관리하는 데 사용되는 효율적인 알고리즘입니다. 주로 최소 신장 트리, 사이클 检测, 집합 합치기 등의 문제에 활용됩니다.
핵심 연산:
- find: 특정 원소의 집합 대표자(ROOT)를 찾습니다. 경로 압축 기법으로 성능을 최적화합니다.
- merge: 두 집합을 하나의 집합으로 합칩니다. 랭크 기반 합치기로 균형을 유지합니다.
최소 신장 트리 (Minimum Spanning Tree)
Kruskal 알고리즘
Kruskal 알고리즘은 그래프의 모든 정점을 포함하면서 가장 작은 가중치의 간선만 선택하는 방법입니다. 유니온-파인드 자료구조와 결합하여 효율적으로 구현할 수 있습니다.
알고리즘 원리:
- 모든 간선을 가중치 기준 오름차순으로 정렬
- 순차적으로 간선을 선택하며, 선택한 간선이 사이클을 形成하지 않으면 MST에 추가
- MST의 간선 수가 (정점 수 - 1)이 되면 종료
class UnionFind:
def __init__(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
elif self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def kruskal_mst(vertices, edges):
uf = UnionFind(vertices)
mst = []
sorted_edges = sorted(edges, key=lambda e: e[2])
for u, v, weight in sorted_edges:
if uf.union(u, v):
mst.append((u, v, weight))
if len(mst) == len(vertices) - 1:
break
return mst
응용 상황:
- 새로운 그래프: 모든 간선이 처음부터 주어지는 경우
- 부분 그래프: 일부 간선이 이미 존재하는 경우 - 이미 존재하는 간선의 가중치를 0으로 처리하고 동일하게 적용
그래프 사이클 检测
모든 간선을 처리한 후, 모든 정점이 같은 집합 대표자를 공유하는지 확인합니다. 다르다면 그래프가 연결되지 않았음을 의미합니다.
def validate_graph_connectivity(vertices, edges):
uf = UnionFind(vertices)
cycle_detected = False
for u, v, _ in edges:
if not uf.union(u, v):
cycle_detected = True
roots = [uf.find(v) for v in vertices]
is_connected = len(set(roots)) == 1
return is_connected, cycle_detected
이진 트리 (Binary Tree)
대칭 이진 트리 검증
왼쪽子树와 오른쪽子树가 서로 대칭인지 확인하는 문제입니다. 재귀적으로 좌우를 반전하여 비교합니다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_symmetric(root):
def check(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
check(left.right, right.left) and
check(left.left, right.right))
return check(root, root)
이진 트리 직경 계산
임의의 두 노드 사이의 가장 긴 경로를 구합니다. 각 노드에서 좌우子树의 최대 깊이 합이 최대 거리가 됩니다.
class TreeInfo:
def __init__(self):
self.diameter = 0
def calculate_diameter(root):
def dfs(node):
if not node:
return 0
left_depth = dfs(node.left)
right_depth = dfs(node.right)
info.diameter = max(info.diameter, left_depth + right_depth)
return 1 + max(left_depth, right_depth)
info = TreeInfo()
dfs(root)
return info.diameter
레벨 순회 (BFS)
각 레벨별로 노드를 수집합니다. 큐를 사용하여 너비 우선으로 탐색합니다.
from collections import deque
def level_order_traversal(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
그래프 최단 경로
Dijkstra 알고리즘
가중치가 양수인 그래프에서 단일 시작점부터 모든 다른 정점까지의 최단 경로를 찾습니다. 우선순위 큐를 활용하여 효율적으로 구현합니다.
import heapq
def dijkstra_shortest_path(graph, start):
dist = {node: float('inf') for node in graph}
prev = {node: None for node in graph}
dist[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_dist, u = heapq.heappop(priority_queue)
if current_dist > dist[u]:
continue
for v, weight in graph[u]:
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
prev[v] = u
heapq.heappush(priority_queue, (new_dist, v))
return dist, prev
핵심 포인트:
- 우선순위 큐로 아직 처리되지 않은 정점 중 최소 거리의 정점을 선택
- 각 인접 정점까지의 새로운 거리를 계산하고 갱신
- 모든 정점이 처리될 때까지 반복
연결 리스트 (Linked List)
교차점 찾기
두 연결 리스트가 교차하는 지점을 찾습니다. 서로의 헤드를 교환하며 순회하면 같은 위치에서 만납니다.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def find_intersection(head_a, head_b):
pointer_a = head_a
pointer_b = head_b
while pointer_a != pointer_b:
pointer_a = pointer_a.next if pointer_a else head_b
pointer_b = pointer_b.next if pointer_b else head_a
return pointer_a
팰린드롬 연결 리스트
연결 리스트가 회문인지 확인합니다. 리스트를 반으로 나눈 후前半부를 뒤집어 后半부와 비교합니다.
def is_palindrome(head):
if not head or not head.next:
return True
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
prev = None
current = slow.next
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
left = head
right = prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
환형 연결 리스트 检测
Floyd의 토끼와 거북이 알고리즘을 활용합니다. 느린 포인터와 빠른 포인터를 사용하여 사이클 존재 여부를 判断합니다.
def has_cycle(head):
if not head or not head.next:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
원리:
- 순환이 없으면 빠른 포인터가 NULL에 도달
- 순환이 있으면 두 포인터가 반드시 만남
- 시간 복잡도: O(n), 공간 복잡도: O(1)
스택 (Stack) 활용
유효한 괄호 검증
문자열의 괄호가 올바르게 짝지어졌는지 확인합니다. 스택을 사용하여 여는 괄호를_push하고, 닫는 괄호마다 스택 top과 비교합니다.
def is_valid_parentheses(s):
bracket_map = {
')': '(',
'}': '{',
']': '['
}
stack = []
for char in s:
if char in bracket_map:
if not stack or stack.pop() != bracket_map[char]:
return False
else:
stack.append(char)
return len(stack) == 0
구현 순서:
- 해시 테이블로 괄호 쌍 매핑
- 문자열을 순회하며 여는 괄호는 스택에 저장
- 닫는 괄호出现 시 스택 top과 매핑 값 비교
- 최종적으로 스택이 비어있으면 유효한 괄호