[코딩 테스트, 더 이상 미룰 수 없다] 프로그래머스lv3 - 정수 삼각형 : DP 사고하기

이번에는 프로그래머스 정수 삼각형 문제를 풀면서 DP를 어떻게 생각했는지 정리해보려고 한다.

 

코딩 테스트를 준비하며 DP 형태는 꼭 준비해야 하기에 꼼꼼히 이해하고 넘어가야 활용이 가능할 것이라 생각한다.

 

DP는 Dynamic Programming의 줄임말로, 이미 계산한 값을 저장해두고 다시 활용하는 방식이다.

핵심은 다음과 같다.

현재 위치의 답을 이전에 구한 답으로 만들 수 있는가?

즉, 모든 경우를 매번 새로 계산하지 않고, 이전 단계에서 구한 값을 이용해 현재 단계의 답을 채우는 방식이다.

 

 

이번에 푼 문제는 프로그래머스의 정수 삼각형이다. 위에서 아래로 내려가면서 숫자를 더할 때, 만들 수 있는 가장 큰 합을 구하는 문제다.

https://school.programmers.co.kr/learn/courses/30/lessons/43105

1. 처음 생각한 방식

문제를 보고 가장 먼저 떠올린 생각은 각 위치까지 도착했을 때의 최대 합을 저장하면 된다는 것이었다.

삼각형의 특정 위치에 도착하는 방법은 위쪽에서 내려오는 방식으로 정해진다. 그래서 각 칸마다 “여기까지 왔을 때 얻을 수 있는 최대 합”을 저장하면 마지막 줄에서 답을 구할 수 있다고 생각했다.

먼저 DP 배열의 의미를 다음과 같이 잡았다.

dp[i][j] = i번째 줄 j번째 칸까지 내려왔을 때 얻을 수 있는 최대 합

 

 

이렇게 정의하면 현재 위치의 값은 이전 줄의 값에서 이어진다. 가운데에 있는 칸은 바로 위쪽과 왼쪽 위쪽, 두 방향에서 올 수 있다.

그래서 기본 점화식은 다음과 같이 세울 수 있다.

dp[i][j] = triangle[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j])

현재 칸의 값에 이전 줄에서 올 수 있는 두 경로 중 더 큰 값을 더하는 방식이다.

2. 경계 처리 생각하기

점화식을 세운 뒤에는 모든 위치에 같은 식을 적용할 수 있는지 확인했다.

가운데 칸은 두 방향에서 올 수 있지만, 양쪽 끝은 다르다.

왼쪽 끝은 바로 위에서만 올 수 있다.

if j == 0:
    dp[i][j] = triangle[i][j] + dp[i - 1][j]

오른쪽 끝은 왼쪽 위에서만 올 수 있다.

elif j == len(triangle[i]) - 1:
    dp[i][j] = triangle[i][j] + dp[i - 1][j - 1]

그 외의 가운데 칸은 두 방향 중 큰 값을 선택한다.

else:
    dp[i][j] = triangle[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j])

이 과정에서 점화식을 세운 뒤에는 인덱스가 실제로 존재하는지 확인해야 한다는 점을 알 수 있었다.

3. 내가 처음 작성한 코드

처음 작성한 코드는 다음과 같았다.

def solution(triangle):
    
    dp = [[0] * len(triangle) for _ in range(len(triangle))]
    
    for i, lst in enumerate(triangle):
        for j in range(len(lst)):
            if j == 0:
                dp[i][j] = lst[j] + dp[i - 1][j]
            elif j == len(lst) - 1:
                dp[i][j] = lst[j] + dp[i - 1][j - 1]
            else:
                dp[i][j] = lst[j] + max(dp[i - 1][j - 1], dp[i - 1][j])
            
    return max(dp[len(triangle) - 1])

전체적인 방향은 맞았다.
현재 위치까지의 최대 합을 저장하고, 마지막 줄에서 최댓값을 반환하는 흐름으로 접근했다.

4. 풀고 나서 발견한 예외

코드를 다시 보면서 가장 먼저 확인한 부분은 i == 0이었다.

첫 번째 줄에서는 이전 줄이 존재하지 않는다. 그런데 처음 코드에서는 i = 0일 때도 다음 코드가 실행된다.

dp[0][0] = triangle[0][0] + dp[-1][0]

파이썬에서 dp[-1]은 마지막 행을 의미한다. 이번 문제에서는 마지막 행의 초기값이 0이라서 결과에 큰 영향을 주지 않았지만, 논리적으로 좋은 출발점은 아니었다.

이 문제의 시작값은 직접 넣어주는 것이 맞다.

dp[0][0] = triangle[0][0]

또 하나는 DP 배열을 500으로 고정해서 만든 점이다.

dp = [[0] * 500 for _ in range(len(triangle))]

문제 제한을 알고 있으면 통과할 수는 있지만, 입력 크기에 맞춰 만드는 편이 더 자연스럽다.

n = len(triangle)
dp = [[0] * n for _ in range(n)]

마지막 줄에도 실제 값 뒤에 0이 남게 된다. 이번 문제는 삼각형의 값이 양수라서 영향이 없지만, 값의 범위가 달라지는 문제에서는 오답이 될 수 있다.

5. 보완한 방식

처음 사고 과정은 다음 순서였다.

점화식 정의
→ 경계 처리 분리
→ i가 바뀔 때 조건 확인
→ 반환 위치 확인

이 흐름은 괜찮았다. 점화식을 먼저 떠올렸고, 경계에서 식이 달라진다는 점도 확인했다. 마지막에 어떤 값을 반환해야 하는지도 따로 생각했다.

 

 

다만 앞으로는 두 가지를 더 명확히 하려고 한다.

첫째, 점화식보다 먼저 DP 배열의 의미를 한 문장으로 정의한다.

dp[i][j]는 i번째 줄 j번째 칸까지 왔을 때의 최대 합이다.

둘째, 점화식을 적용할 수 없는 초기 상태를 먼저 처리한다.

dp[0][0] = triangle[0][0]

이후에 1번째 줄부터 반복을 시작하면 이전 줄이 없는 상황을 피할 수 있다.

6. 최종 코드

def solution(triangle):
    n = len(triangle)
    dp = [[0] * n for _ in range(n)]

    dp[0][0] = triangle[0][0]

    for i in range(1, n):
        for j in range(len(triangle[i])):
            if j == 0:
                dp[i][j] = triangle[i][j] + dp[i - 1][j]
            elif j == len(triangle[i]) - 1:
                dp[i][j] = triangle[i][j] + dp[i - 1][j - 1]
            else:
                dp[i][j] = triangle[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j])

    return max(dp[n - 1])

 

 

7. 이번 문제로 정리한 DP 사고 순서

이번 문제를 풀면서 DP 문제를 볼 때 다음 순서로 생각하면 좋겠다고 느꼈다.

1. dp 배열의 의미를 정의한다.
2. 현재 상태가 어떤 이전 상태에서 오는지 찾는다.
3. 점화식을 세운다.
4. 점화식이 적용되지 않는 경계를 확인한다.
5. 초기값을 따로 설정한다.
6. 반복 순서를 정한다.
7. 최종 답이 dp의 어느 위치에 있는지 확인한다.

이번 정수 삼각형 문제에서는 이 흐름이 비교적 잘 맞았다.
처음에는 점화식을 기준으로 문제를 풀었고, 이후 경계 조건과 반환 위치를 확인하면서 코드를 완성했다.

풀고 나서 보니 첫 행의 초기값 처리가 부족했다. 다음 DP 문제부터는 점화식을 쓰기 전에 dp[i][j]가 정확히 무엇을 의미하는지, 그리고 시작값은 어디인지를 먼저 확인해야겠다.