Bottom-up Approach

동적 계획법(Dynamic Programming)은 복잡한 문제를 더 작고 간단한 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.
이 방법은 문제가 최적 부분 구조(Optimal Substructure)와 중복되는 하위 문제(Overlapping Subproblems)라는 두 가지 핵심 특성을 가질 때 적용할 수 있다.
동적 계획법을 구현하는 방법에는, 하향식 접근(Top-down Approach)과 상향식 접근(Bottom-up Approach) 두 가지가 있다.

상향식 접근법(Bottom-up Approach)은 동적 계획법 구현의 강력한 방법으로, 특히 대규모 입력과 메모리 최적화가 필요한 상황에서 유용하다.
이 접근법은 작은 하위 문제부터 시작하여 점진적으로 원래 문제를 해결하는 방식으로, 재귀 호출의 오버헤드를 피하고 메모리 접근 패턴을 최적화할 수 있다.

효과적인 상향식 동적 계획법 구현을 위해서는 다음 사항에 주의해야 한다:

문제의 구조와 하위 문제 간의 의존성을 명확히 파악한다.
상태를 효율적으로 표현하고 점화식을 정확히 도출한다.
기본 사례를 올바르게 초기화한다.
하위 문제를 올바른 순서로 해결한다.
가능한 경우 공간 최적화 기법을 적용한다.

상향식 접근(Bottom-up Approach)의 기본 개념

상향식 접근법은 동적 계획법 구현 방식 중 하나로, “테이블링(Tabulation)“이라고도 불린다. 이 방식은 가장 작은 하위 문제부터 시작하여 점진적으로 더 큰 문제를 해결해 나가는 방식이다.
모든 하위 문제의 결과를 테이블(일반적으로 배열)에 저장하고, 이미 계산된 결과를 활용하여 상위 문제를 해결한다.

상향식 접근의 핵심 요소

초기화: 기본 사례(Base Case)에 대한 값을 테이블에 초기화한다.
반복적 접근: 작은 하위 문제부터 시작하여 점진적으로 더 큰 문제로 진행한다.
테이블 구축: 각 하위 문제의 결과를 테이블에 저장한다.
의존성 순서: 하위 문제 간의 의존성을 고려하여 올바른 순서로 계산한다.
최종 결과: 테이블에서 원래 문제의 해답을 찾는다.

상향식 접근의 구현 과정

상향식 접근을 구현하는 일반적인 단계는 다음과 같다:

문제 분석: 문제의 구조를 분석하고 하위 문제를 식별한다.
상태 정의: 각 하위 문제를 나타내는 상태를 정의한다.
점화식 도출: 하위 문제 간의 관계를 나타내는 점화식을 도출한다.
테이블 초기화: 기본 사례(Base Case)에 대한 값으로 테이블을 초기화한다.
테이블 채우기: 작은 하위 문제부터 시작하여 테이블을 채운다.
결과 추출: 테이블에서 원래 문제의 해답을 찾아 반환한다.

상향식 접근의 실제 예시

피보나치 수열(Fibonacci Sequence)

피보나치 수열은 동적 계획법의 가장 간단한 예시 중 하나.
n번째 피보나치 수를 계산하는 상향식 구현은 다음과 같다:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def fibonacci_bottom_up(n):
    # 기본 사례 처리
    if n <= 1:
        return n
    
    # DP 테이블 초기화
    dp = [0] * (n+1)
    dp[0], dp[1] = 0, 1
    
    # 상향식으로 테이블 채우기
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

설명:

먼저 DP 테이블 dp를 크기 n+1로 초기화한다.
기본 사례인 F(0) = 0과 F(1) = 1을 설정한다.
인덱스 2부터 n까지 반복하며, 각 피보나치 수를 이전 두 수의 합으로 계산한다.
최종적으로 n번째 피보나치 수인 dp[n]을 반환한다.

계단 오르기 문제(Climbing Stairs)

n개의 계단이 있고, 한 번에 1계단 또는 2계단씩 오를 수 있을 때, 꼭대기에 도달하는 서로 다른 방법의 수를 구하는 문제이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def climb_stairs_bottom_up(n):
    # 기본 사례 처리
    if n <= 2:
        return n
    
    # DP 테이블 초기화
    dp = [0] * (n+1)
    dp[1], dp[2] = 1, 2
    
    # 상향식으로 테이블 채우기
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

설명:

DP 테이블 dp를 크기 n+1로 초기화한다.
기본 사례: 1계단은 1가지 방법, 2계단은 2가지 방법으로 설정한다.
3계단부터 n계단까지 각 계단에 도달하는 방법의 수를 계산한다.
i번째 계단에 도달하는 방법은 (i-1)번째 계단에서 1계단 오르는 방법과 (i-2)번째 계단에서 2계단 오르는 방법의 합이다.

0/1 배낭 문제(0/1 Knapsack Problem)

n개의 물건이 있고, 각 물건은 무게 w[i]와 가치 v[i]를 가질 때, 최대 무게 W를 초과하지 않으면서 최대 가치를 가지는 물건의 조합을 찾는 문제입니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def knapsack_bottom_up(weights, values, capacity):
    n = len(weights)
    
    # DP 테이블 초기화: dp[i][w]는 처음 i개 물건으로 무게 w를 채웠을 때의 최대 가치
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    # 상향식으로 테이블 채우기
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i-1] <= w:
                # 현재 물건을 포함하거나 포함하지 않는 경우 중 최대값 선택
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                # 현재 물건이 용량을 초과하면 포함하지 않음
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

설명:

2차원 DP 테이블 dp를 초기화한다. dp[i][w]는 처음 i개 물건을 고려했을 때, 최대 무게 w에서의 최대 가치를 나타낸다.
각 물건(i)과 각 가능한 무게(w)에 대해 반복한다.
현재 물건이 현재 무게 한도 내에 들어간다면, 이 물건을 포함하는 경우와 포함하지 않는 경우 중 더 큰 가치를 선택한다.
물건이 무게 한도를 초과하면, 이전 물건까지 고려한 최대 가치를 유지한다.

최장 증가 부분 수열(Longest Increasing Subsequence)

주어진 배열에서 값이 증가하는 가장 긴 부분 수열의 길이를 찾는 문제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def longest_increasing_subsequence(nums):
    if not nums:
        return 0
    
    n = len(nums)
    
    # DP 테이블 초기화: dp[i]는 nums[i]를 마지막 요소로 하는 LIS의 길이
    dp = [1] * n
    
    # 상향식으로 테이블 채우기
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

설명:

DP 테이블 dp를 초기화하며, 각 원소는 적어도 길이가 1인 부분 수열을 형성한다.
각 위치 i에 대해, 이전의 모든 위치 j를 검사한다.
만약 nums[i]가 nums[j]보다 크다면, i로 끝나는 증가 부분 수열은 j로 끝나는 증가 부분 수열에 nums[i]를 추가하여 확장할 수 있다.
모든 가능한 LIS 길이 중 최대값을 반환한다.

상향식 접근의 장단점

장점

효율적인 메모리 접근: 일반적으로 메모리 접근 패턴이 더 효율적(캐시 지역성 향상).
스택 오버플로우 방지: 재귀 호출을 사용하지 않기 때문에 스택 오버플로우 위험이 없다.
불필요한 하위 문제 계산 방지: 필요한 모든 하위 문제를 순서대로 해결하므로, 불필요한 하위 문제 계산을 피할 수 있다.
반복적 구현: 반복문을 사용하기 때문에 일반적으로 실행 속도가 더 빠르다.
공간 최적화 용이: 필요한 이전 상태만 저장하는 방식으로 공간 복잡도를 최적화하기 쉽다.

단점

직관적이지 않을 수 있음: 문제에 따라 하향식 접근보다 직관적이지 않을 수 있다.
모든 하위 문제 계산: 원래 문제 해결에 필요하지 않은 하위 문제도 모두 계산한다.
구현 복잡성: 일부 복잡한 문제에서는 구현이 더 어려울 수 있다.
디버깅 난이도: 재귀적 구조가 아니기 때문에 디버깅이 어려울 수 있다.
의존성 순서 관리: 하위 문제 간의 의존성 순서를 올바르게 관리해야 한다.

공간 최적화 기법

상향식 접근의 장점 중 하나는 공간 복잡도를 최적화하기 쉽다는 것이다.

슬라이딩 윈도우(Sliding Window)

많은 동적 계획법 문제에서 현재 상태를 계산하기 위해 이전의 몇 개 상태만 필요한 경우, 전체 테이블 대신 필요한 상태만 저장할 수 있다.

피보나치 수열 예시:

1
2
3
4
5
6
7
8
9
def fibonacci_optimized(n):
    if n <= 1:
        return n
    
    a, b = 0, 1
    for i in range(2, n+1):
        a, b = b, a + b
    
    return b

이 최적화된 구현에서는 전체 배열 대신 이전 두 값만 저장하므로, 공간 복잡도가 O(n)에서 O(1)로 감소한다.

차원 감소(Dimension Reduction)

일부 다차원 DP 문제에서는 현재 행을 계산하기 위해 이전 행만 필요한 경우가 있다.
이런 경우 2차원 배열 대신 1차원 배열만 사용할 수 있다.

배낭 문제 최적화 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def knapsack_optimized(weights, values, capacity):
    n = len(weights)
    
    # 1차원 DP 테이블 사용
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 중요: 역순으로 순회하여 중복 계산 방지
        for w in range(capacity, weights[i]-1, -1):
            dp[w] = max(dp[w], values[i] + dp[w-weights[i]])
    
    return dp[capacity]

이 최적화된 구현에서는 2차원 배열 대신 1차원 배열을 사용하므로, 공간 복잡도가 O(n×W)에서 O(W)로 감소한다.

실전 최적화 기법

캐시 지역성 최적화

상향식 접근에서는 메모리 접근 패턴이 중요하다.
캐시 지역성(Cache Locality)을 고려하여 코드를 최적화할 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# 2차원 배열에서의 효율적인 메모리 접근 패턴
def efficient_dp_traversal(n, m):
    dp = [[0 for _ in range(m)] for _ in range(n)]
    
    # 행 우선 순회 (캐시 지역성 활용)
    for i in range(n):
        for j in range(m):
            # 상태 계산
            dp[i][j] = compute_state(i, j)
    
    return dp

루프 언롤링(Loop Unrolling)

반복되는 패턴의 계산이 많은 DP 문제에서는 루프 언롤링을 통해 성능을 향상시킬 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def fibonacci_unrolled(n):
    if n <= 1:
        return n
    
    a, b = 0, 1
    
    # 루프 언롤링: 한 번에 2개씩 계산
    for i in range(2, n + 1, 2):
        a = a + b
        b = a + b
        
    # n이 홀수인 경우 마지막 계산 추가
    if n % 2 == 0:
        return a
    else:
        return b

메모리 접근 최소화

필요한 상태만 유지하여 메모리 접근을 최소화할 수 있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def min_cost_path(grid):
    n, m = len(grid), len(grid[0])
    
    # 전체 2차원 배열 대신 현재 행과 이전 행만 유지
    prev_row = [0] * m
    curr_row = [0] * m
    
    prev_row[0] = grid[0][0]
    for j in range(1, m):
        prev_row[j] = prev_row[j-1] + grid[0][j]
    
    for i in range(1, n):
        curr_row[0] = prev_row[0] + grid[i][0]
        
        for j in range(1, m):
            curr_row[j] = min(curr_row[j-1], prev_row[j]) + grid[i][j]
        
        # 행 교체
        prev_row, curr_row = curr_row, prev_row
    
    return prev_row[m-1]

실제 개발 시 상향식 접근 사용 지침

상향식 접근이 적합한 상황
1. 대규모 입력: 입력 크기가 큰 경우, 스택 오버플로우를 피하기 위해 상향식 접근이 좋다.
2. 모든 하위 문제 필요: 모든 하위 문제의 해결책이 필요한 경우에 효율적이다.
3. 메모리 제약: 공간 복잡도 최적화가 중요한 경우에 적합하다.
4. 간단한 의존성: 하위 문제 간의 의존성이 명확하고 단순한 경우에 적합하다.
5. 반복적 패턴: 문제가 반복적 패턴을 가지고 있을 때 더 자연스럽다.
효과적인 구현 팁
1. 의존성 순서 파악: 하위 문제 간의 의존성을 명확히 파악하고, 올바른 순서로 계산한다.
2. 테이블 크기 최적화: 필요한 최소한의 크기로 DP 테이블을 초기화한다.
3. 공간 최적화 고려: 가능한 경우 슬라이딩 윈도우나 차원 감소 기법을 적용한다.
4. 경계 조건 주의: 인덱스 범위와 경계 조건을 신중히 처리한다.
5. 초기화 명확히: 기본 사례에 대한 초기화를 명확히 한다.
6. 중간 결과 검증: 복잡한 문제의 경우, 중간 결과를 검증하여 알고리즘의 정확성을 확인한다.
상태 설계 및 점화식 도출 방법
상향식 접근의 핵심은 올바른 상태 설계와 점화식 도출:
1. 상태 정의: 각 하위 문제를 명확하게 정의한다. 상태는 일반적으로 DP 테이블의 인덱스로 표현된다.
2. 상태 전이 파악: 한 상태에서 다른 상태로 어떻게 전이되는지 파악한다.
3. 화식 도출: 현재 상태와 이전 상태 간의 관계를 수학적으로 표현한다.
4. 본 사례 식별: 계산의 시작점이 되는 가장 작은 하위 문제를 식별한다.

고급 상향식 동적 계획법 기법

비트마스킹 DP(Bitmask DP)

비트마스킹을 사용하여 상태를 효율적으로 표현하는 기법으로, 주로 집합이나 선택 상태를 다루는 문제에 유용하다.

외판원 문제(TSP) 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def tsp_bottom_up(dist):
    n = len(dist)
    # dp[mask][i] = 방문한 도시 집합이 mask이고 현재 도시가 i일 때, 남은 도시를 방문하고 0으로 돌아가는 최소 비용
    dp = [[float('inf')] * n for _ in range(1 << n)]
    
    # 기본 사례: 모든 도시를 방문하고 0으로 돌아가는 비용
    for i in range(1, n):
        dp[(1 << n) - 1][i] = dist[i][0]
    
    # 상향식으로 테이블 채우기 (역순으로 진행)
    for mask in range((1 << n) - 2, 0, -1):
        for i in range(n):
            # 현재 도시 i가 mask에 포함되어 있는지 확인
            if mask & (1 << i):
                for j in range(n):
                    # 다음 도시 j가 mask에 포함되어 있지 않은지 확인
                    if not (mask & (1 << j)):
                        dp[mask][i] = min(dp[mask][i], dist[i][j] + dp[mask | (1 << j)][j])
    
    # 시작 도시 0에서 시작하여 모든 도시를 방문하는 최소 비용
    return dp[1][0]

구간 DP(Interval DP)

구간에 대한 최적해를 구하는 문제에 적용되는 기법으로, 일반적으로 구간의 길이를 점진적으로 늘려가며 계산한다.

행렬 곱셈 연쇄(Matrix Chain Multiplication) 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def matrix_chain_multiplication(dims):
    n = len(dims) - 1  # 행렬 개수
    
    # dp[i][j] = i부터 j까지의 행렬을 곱하는 최소 연산 횟수
    dp = [[0 for _ in range(n)] for _ in range(n)]
    
    # 구간 길이를 1부터 n-1까지 증가
    for l in range(1, n):
        for i in range(n - l):
            j = i + l
            dp[i][j] = float('inf')
            
            # 모든 가능한 분할점 k에 대해 최소값 찾기
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

트리 DP(Tree DP)

트리 구조에서의 동적 계획법으로, 일반적으로 후위 순회(post-order traversal)를 사용하여 리프 노드부터 루트 노드까지 계산한다.

트리에서의 최대 독립 집합(Maximum Independent Set in Trees) 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def max_independent_set(tree):
    # tree: 인접 리스트로 표현된 트리
    n = len(tree)
    
    # dp[node][0]: node를 선택하지 않았을 때의 최대 독립 집합 크기
    # dp[node][1]: node를 선택했을 때의 최대 독립 집합 크기
    dp = [[0, 0] for _ in range(n)]
    
    def dfs(node, parent):
        for child in tree[node]:
            if child != parent:
                dfs(child, node)
                # node를 선택하지 않은 경우, 자식은 선택하거나 선택하지 않을 수 있음
                dp[node][0] += max(dp[child][0], dp[child][1])
                # node를 선택한 경우, 자식은 선택할 수 없음
                dp[node][1] += dp[child][0]
        
        # node를 선택한 경우 자신의 값도 더함
        dp[node][1] += 1
    
    dfs(0, -1)  # 루트를 0으로 가정
    return max(dp[0][0], dp[0][1])

실제 응용 사례

문자열 처리 알고리즘

최장 공통 부분 수열(Longest Common Subsequence) 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    
    # dp[i][j] = text1[:i]와 text2[:j]의 LCS 길이
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

그래프 알고리즘

모든 쌍 최단 경로(All-Pairs Shortest Path) - 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def floyd_warshall(graph):
    n = len(graph)
    
    # dp[k][i][j] = 0부터 k까지의 중간 정점만 사용하여 i에서 j로 가는 최단 경로
    dp = [row[:] for row in graph]  # graph의 깊은 복사
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    
    return dp

게임 이론 알고리즘

님 게임(Nim Game) 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def can_win_nim(n):
    # dp[i] = 돌이 i개 남았을 때 현재 플레이어가 이길 수 있는지 여부
    dp = [False] * (n + 1)
    
    # 기본 사례: 돌이 1, 2, 3개 남은 경우 현재 플레이어가 이김
    for i in range(1, min(4, n + 1)):
        dp[i] = True
    
    # 상향식으로 테이블 채우기
    for i in range(4, n + 1):
        # 현재 플레이어가 1, 2, 3개를 가져갔을 때, 상대방이 지는 경우가 하나라도 있으면 이김
        dp[i] = not dp[i-1] or not dp[i-2] or not dp[i-3]
    
    return dp[n]

Bottom-up Approach