[프로그래머스] 동적계획법(Dynamic Programming) - 정수 삼각형 (Python / Swift 풀이)

programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

삼각형 구조

삼각형 구조의 데이터는 각 열의 행의 크기가 다른 2차원 배열로 데이터가 들어오게 된다.

triangle[0] 의 크기는 1
triangle[1] 의 크기는 2
...
triangle[n] 의 크기는 n+1

 

문제에서는 정삼각형으로 표현하였지만

        *
      *   *
   *    *    *
*    *    *    *

 

2차원 배열 형태로 값이 들어오므로 다음과 같이 왼쪽으로 밀어 직각삼각형으로 생각할 수 있다.

        0  1   2   3   
0  |   *
1   |   *   *
2  |   *   *   *
3  |   *   *   *   *

 

i열의 j행 위치의 숫자는 triangle[i][j]로 얻을 수 있다.

 

이동경로

아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다는 조건이 있었다.

정삼각형 형태를 직각삼각형 형태로 바꾸었으므로 위 조건은 바로 아래칸 또는 오른쪽 아래 대각선으로만 이동 가능하다고 이해할 수 있다.

즉, (i, j)에서는 (i+1, j) 또는 (i+1, j+1)로만 이동 가능하다.

 

이전 단계를 알면 다음 단계를 구할 수 있다.

꼭대기 (0,0)에서부터 (i,j)까지 거쳐간 숫자의 최댓값을 구하는 함수를 먼저 만들어야 한다.

꼭대기층부터 (i,j)로 오려면 반드시 (i-1, j-1) 또는 (i-1, j)를 거쳐서 오게 된다.

따라서 (i-1, j-1) 또는 (i-1, j) 위치까지의 최대값 중 더 큰 값과, (i, j)값을 더하면 된다.

 

위의 아이디어를 간단하게 표현해보자면 다음과 같다.

def maxPath(i,j):
    if maxPath(i-1,j-1) < maxPath(i-1, j):
        return maxPath(i-1, j) + triangle[i][j]
    return maxPath(i-1, j-1) + triangle[i][j]

 

여기서 세부적인 내용을 확장하자면,

• i == 0인 경우는 (0,0) 한가지 뿐이다. (0,0)은 이전 단계가 없으므로 자기 자신을 반환하면 된다.
• j == 0인 경우는 maxPath(i-1, j-1)를 구할 수 없다. 따라서 maxPath(i-1, j)와 자기 자신의 합을 반환하면 된다.
• i-1 < j 인 경우는 triangle[i-1][j]를 구할 수 없다. 따라서 maxPath(i-1, j-1)와 자기 자신의 합을 반환하면 된다.
• 이미 계산된 값은 다시 계산하지 말고 데이터를 저장했다가 꺼내 오면 연산 시간이 단축된다. => 동적계획법의 핵심!
  • 저장할 공간은 triangle과 같은 크기의 2차원 배열이어야 함!

# 저장할 공간은 -1로 채워 넣는다.
storage = [[-1 for i in range(len(triangle[j]))] for j in range(len(triangle))]

def maxPath(i,j):
    # 이미 계산된 값이 있으면 바로 반환한다.
    if storage[i][j] != -1:
        return storage[i][j]
        
    # (0,0)은 자기 자신 반환
    if i == 0 and j == 0:
        storage[i][j] = triangle[0][0]
        return storage[i][j]
        
    # j == 0 이면 왼쪽 대각선 위로부터는 올 수 없음
    if j == 0:
        storage[i][j] = maxPath(i-1, j) + triangle[i][j]
        return storage[i][j]
        
    # i-1 < j 이면 바로 위로부터는 올 수 없음
    if i-1 < j:
        storage[i][j] = maxPath(i-1, j-1) + triangle[i][j]
        return storage[i][j]
        
    if maxPath(i-1,j-1) < maxPath(i-1, j):
        storage[i][j] = maxPath(i-1, j) + triangle[i][j]
    else:
        storage[i][j] = maxPath(i-1, j-1) + triangle[i][j]
        
    return storage[i][j]

 

바닥에 있는 모든 요소까지 도달하는 최대 경로를 구했으면, 그 중 최댓값을 구하면 된다!

바닥이라고 하면, len(triangle)-1 열에 있는 값들을 말한다.

바닥에 있는 모든 값들의 maxPath값 중 가장 큰 값이 이 문제의 답이 된다.

for i in range(len(triangle)):
	maxPath(len(triangle)-1, i)
    
return max(storage[len(triangle)-1])

 

 

최종 코드

python

def solution(triangle):
    
    # 저장할 공간은 -1로 채워 넣는다.
    storage = [[-1 for i in range(len(triangle[j]))] for j in range(len(triangle))]

    def maxPath(i,j):
        # 이미 계산된 값이 있으면 바로 반환한다.
        if storage[i][j] != -1:
            return storage[i][j]

        # (0,0)은 자기 자신 반환
        if i == 0:
            storage[i][j] = triangle[0][0]
            return storage[i][j]

        # j == 0 이면 왼쪽 대각선 위로부터는 올 수 없음
        if j == 0:
            storage[i][j] = maxPath(i-1, j) + triangle[i][j]
            return storage[i][j]

        # i-1 < j 이면 바로 위로부터는 올 수 없음
        if i-1 < j:
            storage[i][j] = maxPath(i-1, j-1) + triangle[i][j]
            return storage[i][j]

        if maxPath(i-1,j-1) < maxPath(i-1, j):
            storage[i][j] = maxPath(i-1, j) + triangle[i][j]
        else:
            storage[i][j] = maxPath(i-1, j-1) + triangle[i][j]

        return storage[i][j]
    
    for i in range(len(triangle)):
        maxPath(len(triangle)-1, i)

    return max(storage[len(triangle)-1])

 

swift

func solution(_ triangle: [[Int]]) -> Int {
    
    // 저장할 공간은 -1로 채워 넣는다.
    var storage = [[Int]]()
    for i in 0..<triangle.count {
        storage.append([Int](repeating: -1, count: i+1))
    }

    func maxPath(_ i: Int,_ j: Int) {
        // 이미 계산된 값이 있으면 바로 반환한다.
        if storage[i][j] != -1 {
            return storage[i][j]
        }

        // (0,0)은 자기 자신 반환
        if i == 0 {
            storage[i][j] = triangle[0][0]
            return storage[i][j]
        }

        // j == 0 이면 왼쪽 대각선 위로부터는 올 수 없음
        if j == 0 {
            storage[i][j] = maxPath(i-1, j) + triangle[i][j]
            return storage[i][j]
        }

        // i-1 < j 이면 바로 위로부터는 올 수 없음
        if i-1 < j {
            storage[i][j] = maxPath(i-1, j-1) + triangle[i][j]
            return storage[i][j]
        }

        if maxPath(i-1,j-1) < maxPath(i-1, j) {
            storage[i][j] = maxPath(i-1, j) + triangle[i][j]
        } else {
            storage[i][j] = maxPath(i-1, j-1) + triangle[i][j]
        }
        return storage[i][j]
    
    for i in range(len(triangle)) {
        maxPath(len(triangle)-1, i)
    }

    return storage[triangle.count-1].max()!
}