문제 링크: https://www.acmicpc.net/problem/1932

Thumbnail: Photo by Rafael Garcin (Unsplash)

간단한 DP 문제입니다.

풀이

DP (Dynamic Programming)

DP (Dynamic Programming, 동적 계획법)은 크고 복잡한 문제를 작고 단순한 문제로 쪼개어 푸는 알고리즘 설계 기법입니다.

💡 알고리즘 기법과 알고리즘 설계 기법의 차이?

알고리즘 기법은 문제 해결을 위한 구체적인 방법입니다.
ex) 정렬 알고리즘, 그래프 탐색 알고리즘 등

알고리즘 설계 기법은 문제를 해결하기 위해 사용할 방법(알고리즘 기법)을 설계하는 방법이나 접근 방식을 의미합니다.
ex) 분할 정복, 동적 계획법, 탐욕적 알고리즘(그리디), 백트래킹 등

동적 계획법의 조건

DP로 문제를 풀기 위해서는, 문제가 다음 조건을 만족해야 합니다.

1) Overlapping Subproblem : 겹치는 부분(작은) 문제

DP는 본래의 큰 문제가 여러 개의 부분 문제로 쪼개질 수 있을 때 사용합니다.

다만, 단순히 부분 문제로 쪼개는 것은 분할 정복(Divide & Conquer) 기법과 비슷합니다. 그렇다고 DP가 분할정복과 같은 것은 아닙니다!

분할 정복은 전체 문제를 부분 문제의 합으로 보는 설계 기법으로, 쪼개진 부분 문제가 다시 사용 되지 않습니다.

하지만 DP는 본래의 문제를 여러 개의 부분 문제로 쪼갠 뒤, 다른 부분 문제나 본래의 문제를 풀 때 이전에 구한 부분 문제의 답을 다시 사용합니다. 다시 말해, 동일한 부분 문제가 풀이 과정에 반복해서 나타날 수 있다는 뜻입니다.

그래서, DP는 겹치는 부분 문제를 가진다고 표현합니다.

2) Optimal Substructure : 최적 부분 구조

DP로 문제를 풀기 위해서는 문제를 부분 문제로 쪼갰을 때, 부분 문제의 최적 결과 값을 활용해 전체 문제의 최적 결과 값을 구할 수 있어야 합니다.

이를 최적 부분 구조를 가진다고 표현합니다.

Memoization

DP로 문제를 풀기 위한 두 가지 조건에 따라, 부분 문제들의 최적 결과는 언제나 일정함을 알 수 있습니다. 그렇다면, 이미 한번 풀었던 부분 문제를 다시 풀어야 할까요?

한 번 풀어낸 부분 문제의 답을 기억해, 다음 번에 동일한 부분 문제를 마주할 때 다시 풀지 않고 기억해 둔 답을 사용하는 방법을 Memoization이라고 합니다. 즉, 부분 문제의 답을 캐싱하는 방법입니다.

아래에서 피보나치 수열을 DP를 활용해 푸는 코드를 적어 두었는데, cache 배열을 풀이에 활용하는 점이 Memoization이 도입된 부분입니다.

DP를 구현하는 2가지 방식: 반복문 vs 재귀

반복문으로도, 재귀 호출로도 동적 계획법 풀이를 구현할 수 있습니다. 이 두 방식의 차이점은 접근 방식에 있습니다. 두 방법을 피보나치 수열을 계산하는 코드와 함께 이해해봅시다.

재귀 호출의 경우, 하향식(Top-down) 접근의 풀이입니다. 구해야 하는 본래 문제에서 시작해 더 작은 부분 문제로 내려가면서 풀이를 진행합니다.

cache = [0 for _ in range(100)] # 부분 문제의 결과를 저장할 캐시 배열
cache[1] = cache[2] = 1         # 초기항

def fibonacci(n: int) -> int:
    """N번째 피보나치 수열의 항을 계산합니다."""
    if cache[n] != 0:           # 이미 풀었던 부분 문제라면
        return cache[n]         # 캐시에 저장된 값을 바로 반환한다.
    
    res: int = fibonacci(n-1) + fibonacci(n-2)
    cache[n] = res              # 캐시 배열에 결과 저장
    return res

print(fibonacci(100))

반복문의 경우, 상향식(Bottom-up) 접근의 풀이입니다. 부분 문제에서 시작해 본래 문제까지 풀이를 진행합니다.

cache = [0 for _ in range(101)] # 부분 문제의 결과를 저장할 캐시 배열
cache[1] = cache[2] = 1         # 초기항

for i in range(3, 101):
    cache[i] = cache[i-1] + cache[i-2]

print(cache[100])

이제 문제를 풀어봅시다.

이번 문제는 삼각형 모양으로 배열된 숫자의 합이 최대가 되는 경로를 찾아야 합니다. 단, 아래층으로 이동할 때는 대각선 왼쪽/오른쪽만 이동할 수 있습니다.

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

실제로 입력받을 때는 직각삼각형 모양이니, 수직 아래 또는 한칸 옆으로 이동 가능합니다.

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

DP 배열도 입력과 동일하게 삼각형 모양으로 구성하고 생각하면 됩니다.

DP 배열에는 삼각형의 \(i, j\) (\(i\)는 세로 좌표, \(j\)는 가로 좌표) 위치에 도달할 수 있는 경우 중 값이 최대가 되는 경우의 합을 저장합니다.

DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + INPUT[i][j]

전체 코드

input = open(0).readline
N = int(input())
pyramid = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(N)] for _ in range(N)]
dp[0][0] = pyramid[0][0]

for i in range(1, N): # 다음 층의 dp 배열을 계산한다.
    for j in range(i + 1):
        if j == 0:
            dp[i][j] = dp[i - 1][j] + pyramid[i][j] # 무조건 오른쪽밖에 못가는 경우
        elif j == i:
            dp[i][j] = dp[i - 1][j - 1] + pyramid[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + pyramid[i][j]

print(max(dp[N - 1]))