[프로그래머스 Lv.3] 정수 삼각형

이번 문제는 Dynamic Programming 문제의 대표적인 예제인 정수 삼각형로, 대각선 방향으로만 움직일 수 있을 때 거쳐간 숫자의 합이 최대가 되도록 만드는 문제이다.

 

단순하게 완전탐색(DFS/BFS)로 풀 순 있겠지만, 이 문제의 경우 삼각형의 높이가 한 층씩 높아질수록 경우의 수 가 2배씩 늘어나는 문제로 단순히 완전탐색 알고리즘으로 풀게 되면 문제의 조건(높이는 1이상 500이하) 때문에 O(2^n)의 시간복잡도로 인해 시간초과가 발생할 것이다.

 

따라서 모든 경우의 수를 전부 구하는 완전 탐색이 아니라, 별도의 자료구조에 정보들을 저장하면서 중복된 연산을 최대한 줄여주는 DP 알고리즘을 사용하여 풀어야만 한다.

 

먼저 이전에 포스팅한  DP 알고리즘에 대한 내용을 복습할 겸 이 문제가 왜 DP로 풀어야하는지 알아보도록 하자.

[DP] Dynamic Programming 알고리즘의 개념 및 코드

 

1. 큰 문제를 작은 문제로 쪼갤 수 있는가 ?

삼각형의 꼭대기에서부터 바닥까지 이동하기 위해서는 대각선 방향으로 한칸 씩 이동해야 하는데, 이 문제에서 비교하고자 하는 것은 꼭대기부터 바닥까지 거쳐간 숫자들의 '총합'이므로 전체 경로에 대한 수의 합을 각 층간의 합으로 분할할 수 있다.

ex) 7 - 3 - 8 - 2 - 4 를 7 - 3 / 3 - 8 / 8 - 2 .. 로 분할할 수 있다.

 

2. 작은 문제들로부터 구한 정답으로 큰 문제를 해결할 수 있는가 ?

위에서 설명한 것처럼 각 층간의 합은 누적되어 전체 경로에 대한 수의 합으로 만들어지기 때문에, 작은 문제에서 구한 정답들이 큰 문제에 대한 정답으로 이어진다.

 

3. 작은 문제들이 중복적으로 연산되는가 ?

간단하게 7 - 3 - 8 - 2 - 4 와 7 - 3 - 8 - 2 - 5 두 가지 경로만 비교해보자.

위 경우를 보면 두 가지 경로를 비교하는 과정에서 7 - 3 - 8 - 2 라는 경로가 중복되는 것을 알 수 있다. 그렇다면 우리는 꼭대기에서부터 내려가면서 여태까지 거친 숫자들의 합에 최대값을 별도의 공간(DP List)에 저장함으로써 중복된 연산들을 줄일 수 있다 ! (이 방법을 사용하면 n번째 행을 계산할 때 이미 n-1번째 행까지는 합에 대한 최대값으로 이루어져 있다는 것을 보장받을 수 있기 때문에 이전 과정을 반복할 필요가 X)

 

이러한 세가지 근거로 DP 알고리즘을 사용하여 풀어야한다는 것을 알았으니, 본격적으로 구현에 들어가보자.

def solution(triangle):
    
    height = len(triangle) # 삼각형의 높이
    
    dp_list = [[0]*height for _ in range(height)] # DP 리스트
    
    dp_list[0][0] = triangle[0][0]
    
    for i in range(1,height):
        for j in range(len(triangle[i])):
            if j==0: # 가장 왼쪽 원소인 경우
                dp_list[i][j] = dp_list[i-1][0] + triangle[i][0]
            elif i==j: # 가장 오른쪽 원소인 경우
                dp_list[i][j] = dp_list[i-1][j-1] + triangle[i][j] 
            else:
                dp_list[i][j] = max(dp_list[i-1][j-1]+triangle[i][j], dp_list[i-1][j]+triangle[i][j])
               
    max_value = max(dp_list[-1])

    return max_value

본인은 먼저 DP 알고리즘을 사용하기 위해 dp_list라는 별도의 2차원 리스트를 선언 및 초기화하였다.

그 후 입력의 꼭대기에 들어있는 값을 dp_list[0][0]에 저장한 뒤에 2번째 줄부터 시작하여 DP 테이블을 채워나갔다.

 

• 삼각형의 가장 왼쪽 원소인 경우 : 현재 위치의 값(triangle[i][0])과 상단의 값(dp_list[i-1][0])을 더해준다.
• 삼각형의 가장 오른쪽 원소인 경우 : 현재 위치의 값(triangle[i][j])과 좌측 상단의 값(dp_list[i-1][j-1])을 더해준다.
• 그 외의 경우 : 상단의 값(dp_list[i-1][j])과 좌측 상단의 값(dp_list[i-1][j-1])을 비교하여 더 큰 값을 현재 위치의 값(triangle[i][j])과 합해준다. (각 층의 값들은 위에서부터 거치는 숫자들의 총합들이 최대 값이 되도록 유지되어야 하기 때문)

이 과정들을 꼭대기에서 바닥까지 마치고 나면, 바닥의 값들은 꼭대기에서부터 바닥까지 거친 숫자들의 최대 총합이 된다.

 

이 문제를 풀기 위해서는 완전 탐색이 아닌 DP로 풀이해야한다는 것을 파악하고, 별도의 자료구조(2차원 리스트)를 만들어 꼭대기에서부터 반복되는 연산을 방지하기 위해 누적된 최대값을 저장해주어야 한다.

 

이번 문제는 DP 알고리즘 기법의 개념과 사용조건들을 이해하고 복습해볼 수 있었던 좋은 문제였다 :)