알고리즘 정리(2) - DP, 분할 정복, 다익스트라

DP

큰 문제를 작은 문제로 나누고, 중복되는 하위 문제의 결과를 저장해두어 재사용하는 방식의 알고리즘 설계 기법입니다.
탑다운(재귀 + 메모이제이션), 바텀업(반복문 + 테이블) 방식이 있습니다.

DP는 중복 계산 방지로 인해 시간이 단축되며 최적해를 구할 때 자주 사용된다는 특징을 가지고 있습니다.

가장 잘 알려진 DP 문제인 피보나치 수열을 탑다운 방식과 바텀업 방식을 활용해 구현해보겠습니다.

def fib(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

def fib(n):
    dp = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

분할 정복

문제를 여러 개의 작은 문제로 나누어(분할) 해결한 뒤, 결과를 합쳐(정복) 전체 문제를 해결하는 알고리즘 기법입니다.

<구조>
1. 문제를 나눈다
2. 각각을 해결한다.
3. 결과를 합친다.

분할 정복은 하위(작은) 문제간의 의존성이 없을때 효율적이고 병렬 처리에 적합합니다.

가장 대표적인 분할 정복 알고리즘 활용 예시인 합병 정렬 코드입니다.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

다익스트라

가중치가 있는 그래프에서 시작 정점으로부터의 최단 경로를 구하는 알고리즘입니다. 이때, 음수 가중치는 허용되지 않습니다.

시작 노드부터 거리가 가장 짧은 노드를 우선 선택하며 우선순위 큐를 활용하여 구현합니다.

"모든 노드"에 대한 최단 거리를 한 번에 구할 수 있으나 음수 간선이 있으면 사용할 수 없다는 단점을 가지고 있습니다.(이 경우 벨만-포드나 플로이드 워셜 방법을 활용하여 최단 경로를 구해야 합니다.)

import heapq

def dijkstra(graph, start):
    distance = [float('inf')] * len(graph)
    distance[start] = 0
    pq = [(0, start)]  # (비용, 노드)

    while pq:
        dist, now = heapq.heappop(pq)
        if dist > distance[now]:
            continue
        for next_node, cost in graph[now]:
            new_cost = dist + cost
            if new_cost < distance[next_node]:
                distance[next_node] = new_cost
                heapq.heappush(pq, (new_cost, next_node))
    return distance