2026-02-03 | 9 min read | 205 | 코딩 테스트 DP 그래프 알고리즘

8-10. 코딩 테스트: 고급 문제 풀이 (동적 계획법, 그래프 이론)

1. 동적 계획법 (Dynamic Programming, DP) 심화: 복잡한 문제 해결의 핵심

동적 계획법(DP)은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 그 부분 문제들의 해를 결합하여 최종 문제를 해결하는 강력한 알고리즘 설계 기법입니다. 핵심은 "메모이제이션(memoization)" 또는 "타뷸레이션(tabulation)"을 통해 중복 계산을 피하고, 효율성을 극대화하는 것입니다. 특히 코딩 테스트에서는 DP를 활용하여 다양한 최적화 문제를 해결해야 합니다. 이번 글에서는 DP의 심화된 개념과 그래프 이론과의 융합을 통해 해결할 수 있는 문제들을 살펴보겠습니다.

1) DP의 기본 원리 복습

DP는 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)라는 두 가지 중요한 특징을 가집니다.

최적 부분 구조: 전체 문제의 최적해가 부분 문제들의 최적해로 구성될 수 있다는 의미입니다. 즉, 부분 문제들의 최적해를 이용하여 전체 문제의 최적해를 구할 수 있습니다.
중복되는 부분 문제: 동일한 부분 문제가 여러 번 나타나는 경우를 의미합니다. DP는 이러한 중복 계산을 피하기 위해 부분 문제의 해를 저장하고 재사용합니다.

2) DP의 구현 방식

DP는 주로 두 가지 방식으로 구현됩니다.

탑다운(Top-down) 방식 (메모이제이션): 재귀 함수를 사용하여 문제를 해결하고, 각 부분 문제의 해를 메모합니다. 재귀 호출을 통해 문제를 작은 단위로 쪼개고, 이미 계산된 부분 문제는 메모에서 가져와 사용합니다.
바텀업(Bottom-up) 방식 (타뷸레이션): 반복문을 사용하여 문제를 해결하고, 부분 문제의 해를 테이블에 저장합니다. 작은 부분 문제부터 해결하여 테이블을 채워나가고, 최종적으로 전체 문제의 해를 구합니다.

DP 탑다운, 바텀업 방식 비교 설명 뒤

2. 그래프 이론과의 융합: DP 기반 그래프 문제 풀이

그래프 이론과 DP를 결합하면 최단 경로 문제, 최소 비용 문제 등 다양한 그래프 문제를 효율적으로 해결할 수 있습니다. 대표적인 예시로는 다익스트라 알고리즘, 벨만-포드 알고리즘, 그리고 네트워크 플로우 관련 문제가 있습니다.

1) 다익스트라 알고리즘과 DP의 관계

다익스트라 알고리즘은 가중치가 있는 그래프에서 특정 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. DP의 관점에서 보면, 다익스트라 알고리즘은 각 노드까지의 최단 경로를 부분 문제로 정의하고, 이 부분 문제들을 해결해나가면서 최종적으로 모든 노드까지의 최단 경로를 구하는 방식입니다.

DP 적용: dist[i]를 시작 노드에서 노드 i까지의 최단 거리라고 정의하면, 다익스트라 알고리즘은 다음과 같은 점화식을 가집니다.

$dist[v] = \min(dist[v], dist[u] + weight(u, v))$

여기서 u는 현재 노드, v는 u의 인접 노드, weight(u, v)는 u에서 v로 가는 간선의 가중치입니다. 이 점화식은 DP의 최적 부분 구조와 중복되는 부분 문제를 잘 보여줍니다.

2) 벨만-포드 알고리즘과 DP

벨만-포드 알고리즘은 다익스트라 알고리즘과 유사하게 최단 경로를 찾는 알고리즘이지만, 음수 가중치를 갖는 간선이 있는 그래프에서도 사용 가능하다는 차이점이 있습니다. DP 관점에서 벨만-포드 알고리즘은 각 단계에서 모든 간선을 확인하며 최단 거리를 갱신합니다.

DP 적용: dist[i][k]를 시작 노드에서 노드 i까지, 최대 k개의 간선을 사용하여 가는 최단 거리라고 정의합니다. 벨만-포드 알고리즘은 다음과 같은 점화식을 사용합니다.

$dist[v][k] = \min(dist[v][k], dist[u][k-1] + weight(u, v))$

여기서 u는 v로 가는 간선의 시작 노드입니다. 이 점화식은 DP의 전형적인 형태를 보여주며, 이전 단계의 결과를 사용하여 현재 단계를 계산합니다. 벨만-포드 알고리즘은 음수 사이클이 존재하는지 여부도 판단할 수 있습니다.

3) 네트워크 플로우 (Network Flow) 문제와 DP

네트워크 플로우는 그래프 이론의 중요한 개념으로, 최대 유량(Maximum Flow)과 최소 컷(Minimum Cut) 문제를 포함합니다. 이러한 문제들은 DP와 유사한 접근 방식을 통해 해결될 수 있습니다.

최대 유량: 그래프 내에서 시작 노드(Source)에서 종료 노드(Sink)로 보낼 수 있는 최대 유량을 찾는 문제입니다. 포드-풀커슨(Ford-Fulkerson) 알고리즘이나 에드몬드-카프(Edmonds-Karp) 알고리즘 등이 사용됩니다.
- DP와의 연관성: 각 단계에서 잔여 네트워크(Residual Network)를 구성하고, 증가 경로(Augmenting Path)를 찾아 유량을 증가시키는 과정은 일종의 DP적 접근 방식입니다. 각 단계에서 부분 문제의 해(현재까지의 유량)를 기반으로 다음 단계의 해를 계산합니다.
- 최소 컷: 네트워크에서 시작 노드와 종료 노드를 분리하는 간선들의 최소 용량 합을 찾는 문제입니다. 최대 유량-최소 컷 정리(Max-flow min-cut theorem)에 의해 최대 유량은 최소 컷과 같습니다.
- DP와의 연관성: 최소 컷을 찾는 과정은 그래프를 분할하는 여러 경우의 수를 고려하며, 부분 문제들의 해를 결합하여 최종 해를 구하는 과정과 유사합니다.

Ford-Fulkerson 알고리즘 설명 뒤

3. 고급 문제 풀이: 실전 예제

DP와 그래프 이론을 활용한 몇 가지 고급 문제 풀이 예시를 살펴보겠습니다.

1) 가중치가 있는 방향 그래프의 최단 경로 (Dijkstra)

가중치가 있는 방향 그래프가 주어지고, 시작 노드와 도착 노드가 주어졌을 때, 최단 경로의 길이를 구하는 문제입니다. 이 문제는 다익스트라 알고리즘을 사용하여 해결할 수 있습니다.

import heapq

def dijkstra(graph, start, end):
    """
    다익스트라 알고리즘을 사용하여 최단 경로를 계산합니다.

    Args:
        graph: 인접 리스트로 표현된 그래프 (예: {0: [(1, 2), (2, 4)], 1: [(2, 1)]})
        start: 시작 노드
        end: 종료 노드

    Returns:
        시작 노드에서 종료 노드까지의 최단 거리. 도달할 수 없으면 -1 반환.
    """
    distances = {node: float('inf') for node in graph}  # 모든 노드까지의 거리를 무한대로 초기화
    distances[start] = 0
    pq = [(0, start)]  # 우선순위 큐 (거리, 노드)

    while pq:
        dist, current_node = heapq.heappop(pq)

        if dist > distances[current_node]:
            continue  # 이미 더 짧은 경로를 찾았다면 무시

        if current_node == end:
            return dist  # 종료 노드에 도달

        for neighbor, weight in graph.get(current_node, []):
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    return -1  # 도달할 수 없는 경우


# 예시 그래프
graph = {
    0: [(1, 2), (2, 4)],
    1: [(2, 1)],
    2: [(3, 3)],
    3: []
}

start_node = 0
end_node = 3
shortest_distance = dijkstra(graph, start_node, end_node)
print(f"최단 거리: {shortest_distance}")

2) 음수 가중치가 있는 그래프의 최단 경로 (Bellman-Ford)

음수 가중치를 갖는 간선이 있는 방향 그래프가 주어지고, 시작 노드와 도착 노드가 주어졌을 때, 최단 경로의 길이를 구하는 문제입니다. 이 문제는 벨만-포드 알고리즘을 사용하여 해결할 수 있습니다.

def bellman_ford(graph, start, end):
    """
    벨만-포드 알고리즘을 사용하여 최단 경로를 계산합니다.

    Args:
        graph: 인접 리스트로 표현된 그래프 (예: {0: [(1, -1), (2, 4)], 1: [(2, 3), (3, 2)], 2: [], 3: []})
        start: 시작 노드
        end: 종료 노드

    Returns:
        시작 노드에서 종료 노드까지의 최단 거리. 음수 사이클이 있으면 None 반환.
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    num_nodes = len(graph)

    for _ in range(num_nodes - 1):  # 모든 간선을 |V|-1 번 반복
        for u in graph:
            for v, weight in graph.get(u, []):
                if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                    distances[v] = distances[u] + weight

    # 음수 사이클 검출
    for u in graph:
        for v, weight in graph.get(u, []):
            if distances[u] != float('inf') and distances[u] + weight < distances[v]:
                return None  # 음수 사이클 존재

    if distances[end] == float('inf'):
        return -1  # 도달할 수 없는 경우
    else:
        return distances[end]


# 예시 그래프
graph = {
    0: [(1, -1), (2, 4)],
    1: [(2, 3), (3, 2)],
    2: [],
    3: []
}

start_node = 0
end_node = 3
shortest_distance = bellman_ford(graph, start_node, end_node)
print(f"최단 거리: {shortest_distance}")

3) 최대 유량 문제 (Ford-Fulkerson)

주어진 네트워크에서 시작 노드에서 종료 노드로 보낼 수 있는 최대 유량을 구하는 문제입니다. 이 문제는 포드-풀커슨 알고리즘을 사용하여 해결할 수 있습니다.

def ford_fulkerson(graph, source, sink):
    """
    포드-풀커슨 알고리즘을 사용하여 최대 유량을 계산합니다.

    Args:
        graph: 인접 리스트로 표현된 그래프 (예: {0: {1: 16, 2: 13}, 1: {2: 10, 3: 12}, ...})
        source: 시작 노드
        sink: 종료 노드

    Returns:
        최대 유량
    """
    def bfs(graph, source, sink, parent):
        """
        BFS를 사용하여 증가 경로를 찾습니다.
        """
        visited = {node: False for node in graph}
        queue = [source]
        visited[source] = True

        while queue:
            u = queue.pop(0)
            for v, capacity in graph.get(u, {}).items():
                if not visited[v] and capacity > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
                    if v == sink:
                        return True
        return False

    parent = {}  # 증가 경로를 추적하기 위한 딕셔너리
    max_flow = 0

    # 잔여 네트워크가 존재하는 동안
    while bfs(graph, source, sink, parent):
        path_flow = float('inf')
        s = sink

        # 증가 경로 상의 최소 잔여 용량을 찾습니다.
        while s != source:
            u = parent[s]
            path_flow = min(path_flow, graph[u][s])
            s = u

        # 경로 상의 용량을 업데이트합니다.
        v = sink
        while v != source:
            u = parent[v]
            graph[u][v] -= path_flow
            if v not in graph[u] or graph[u][v] == 0:
                graph[u].pop(v, None) # capacity가 0이 되면 삭제
            if v not in graph or u not in graph:
                graph[v] = {u: path_flow} # 역방향 간선 생성
            elif u not in graph[v]:
                graph[v][u] = path_flow
            else:
                graph[v][u] += path_flow
            v = u

        max_flow += path_flow

    return max_flow

# 예시 그래프 (인접 리스트 + 용량)
graph = {
    0: {1: 16, 2: 13},
    1: {2: 10, 3: 12},
    2: {1: 4, 3: 14},
    3: {}
}

source_node = 0
sink_node = 3
max_flow = ford_fulkerson(graph, source_node, sink_node)
print(f"최대 유량: {max_flow}")

4. 고급 문제 풀이: 네트워크 플로우의 응용

네트워크 플로우는 다양한 실생활 문제를 해결하는 데 응용될 수 있습니다. 최대 유량 문제는 자원 배분, 스케줄링, 이미지 분할 등 다양한 분야에 적용될 수 있습니다.

1) 이분 매칭 (Bipartite Matching)

이분 그래프(Bipartite Graph)에서 최대 매칭(Maximum Matching)을 찾는 문제는 네트워크 플로우 문제로 변환하여 해결할 수 있습니다.

변환: 이분 그래프의 각 노드를 네트워크의 노드로 변환하고, 각 간선을 용량이 1인 간선으로 변환합니다. 시작 노드(Source)와 각 왼쪽 노드를 연결하고, 각 오른쪽 노드와 종료 노드(Sink)를 연결합니다.
해결: 이 네트워크에서 최대 유량을 구하면, 그 값이 최대 매칭의 크기가 됩니다.

2) 최소 컷을 이용한 이미지 분할 (Image Segmentation)

이미지 분할은 픽셀들을 그룹으로 묶어 특정 객체를 인식하는 문제입니다. 최소 컷을 사용하여 이 문제를 해결할 수 있습니다.

변환: 이미지 픽셀을 그래프의 노드로 표현하고, 픽셀 간의 유사성을 간선의 용량으로 표현합니다. 전경(Foreground)과 배경(Background)을 시작 노드와 종료 노드로 각각 간주합니다.
해결: 최소 컷을 구하면, 컷에 의해 분리된 영역이 이미지 분할 결과가 됩니다.

5. 주의사항 및 트러블 슈팅

1) DP 문제의 일반적인 함정

올바른 상태 정의: DP 문제에서 가장 중요한 것은 상태(state)를 올바르게 정의하는 것입니다. 상태를 잘못 정의하면 점화식을 세우기 어렵고, 문제 해결에 실패할 수 있습니다. 상태는 문제의 부분 해를 나타내야 하며, 부분 문제들의 해를 결합하여 전체 문제의 해를 구할 수 있어야 합니다.
점화식의 정확성: 점화식은 DP의 핵심입니다. 점화식을 잘못 세우면 예상치 못한 결과가 발생하거나, 최적해를 찾지 못할 수 있습니다. 점화식을 세울 때는 최적 부분 구조와 중복되는 부분 문제를 고려해야 합니다.
기저 사례 (Base Cases): DP 알고리즘은 기저 사례를 올바르게 정의하는 것이 중요합니다. 기저 사례는 재귀 호출의 종료 조건이며, DP 테이블의 초기 값을 결정합니다. 기저 사례를 잘못 정의하면 알고리즘이 올바르게 동작하지 않을 수 있습니다.
시간 복잡도: DP 알고리즘의 시간 복잡도를 분석하고, 시간 초과를 방지해야 합니다. DP는 중복 계산을 피하여 효율성을 높이지만, 상태의 개수와 점화식의 복잡도에 따라 시간 복잡도가 달라질 수 있습니다.

2) 그래프 문제의 주의사항

그래프 표현: 그래프를 인접 리스트 또는 인접 행렬로 표현할지 결정해야 합니다. 문제의 특성과 간선의 수에 따라 적절한 표현 방식을 선택해야 합니다. 인접 리스트는 희소 그래프(sparse graph)에 적합하고, 인접 행렬은 밀집 그래프(dense graph)에 적합합니다.
사이클 처리: 그래프에 사이클이 있는지 여부를 고려해야 합니다. 다익스트라 알고리즘은 사이클이 없는 그래프에서만 올바르게 동작합니다. 벨만-포드 알고리즘은 음수 사이클을 감지할 수 있습니다.
음수 가중치: 음수 가중치를 갖는 간선이 있는 경우, 다익스트라 알고리즘을 사용할 수 없습니다. 벨만-포드 알고리즘이나 SPFA (Shortest Path Faster Algorithm)와 같은 알고리즘을 사용해야 합니다.
오버플로우: 간선의 가중치가 큰 경우, 자료형의 오버플로우를 방지해야 합니다. int 대신 long long과 같은 더 큰 자료형을 사용하거나, INF (무한대) 값을 적절하게 설정해야 합니다.

3) 디버깅 팁

작은 테스트 케이스: 문제를 해결하기 전에 작은 테스트 케이스를 만들어 알고리즘의 동작을 확인합니다.
DP 테이블 출력: DP 테이블의 값을 출력하여 알고리즘이 올바르게 동작하는지 확인합니다.
경계 조건 확인: 경계 조건을 꼼꼼하게 확인합니다. 예를 들어, 그래프가 비어 있거나, 시작 노드와 종료 노드가 같거나, 간선이 없는 경우 등을 고려해야 합니다.
예외 처리: 예외 상황을 처리합니다. 예를 들어, 도달할 수 없는 노드가 있거나, 음수 사이클이 존재하는 경우를 처리해야 합니다.
자료형 확인: 자료형이 올바르게 사용되었는지 확인합니다. 특히, 오버플로우가 발생하지 않도록 주의해야 합니다.

6. 결론

DP와 그래프 이론은 코딩 테스트에서 매우 중요한 주제입니다. 특히, 네트워크 플로우는 실생활 문제 해결에도 널리 활용되는 강력한 도구입니다. DP와 그래프 이론에 대한 깊이 있는 이해와 문제 풀이 경험을 통해, 코딩 테스트에서 더욱 높은 점수를 얻을 수 있을 것입니다. 지속적인 연습과 다양한 문제 풀이를 통해 숙련도를 높이는 것이 중요합니다.