[Algorithm][DP] 동적 계획법(Dynamic Programming) 알아보기 (참고 문제: 프로그래머스 - 정수 삼각형)

Summary

- 동적 계획법의 기본적인 개념과 구현 과정에 대해서 소개하였다. 그리고 코드를 통해 실제 문제에 적용해보았다. (프로그래머스 정수 삼각형 문제)

- 동적 계획법과 분할 정복 알고리즘의 차이를 간단하게 언급하였다.

---

Description

1. 동적 계획법(DP, Dynamic Programming)이란?

동적 계획법은 문제를 효율적으로 해결하기 위하여 문제 해결 과정에서 생성된 결과를 미리 저장해두고, 그 값을 주어진 문제에 활용하는 방법이다. 달리 표현하면 본 문제를 해결하기 위하여 활용하기 좋은 하위 문제들로 분리하고, 하위 문제의 결과값들을 재활용하여 본 문제를 해결하는 방법이다.

 

글로만 설명하였을 때 쉽게 이해하기 어려울  수 있기 때문에 '피보나치 수열'을 예시로 들어보겠다.

[Pixabay] Fibonacci

피보나치 수열은 [1, 1, 2, 3, 5, 8, 13, 21, ...] 와 같이 표현할 수 있다. 숫자들을 보았을 때 어떤 규칙이 있을까?

1+1 = 2, 2+3 = 5, 3+5=8, ...

 

위 식이 힌트이다. 알아차릴 수 있겠는가?

규칙은 바로 i번째 값은 i-1번째 값과 i-2번째 값의 합이라는 것이다.

따라서 7번 인덱스에 위치한 21이라는 값을 구하기 위해서는 5번 인덱스에 위치한 8과 6번 인덱스에 위치한 13을 통해 구할 수 있다. 그렇다면 13은 마찬가지로, 4번 인덱스에 위치한 5와 5번 인덱스에 위치한 8을 필요로 한다는 것이다.

 

위 두 가지 사례를 보면 n번째에 있는 값을 구하기 위해서는(본문제) n-1번, n-2번 값을 구해야 하고, 또 n-1번 문제를 해결하기 위해서는 그 이전 값들을 알고 있어야 한다는 것을 알 수 있다.

 

[나무위키] 동적 계획법

 

그럼 만약 우리가 100번째 값을 구한다면? 10,000번째 값을 구한다면? 앞서 나오는 모든 값을 구해야 할까?

100번을 구하기 위해 99, 98번, 99번을 구하기 위해 98, 97번, 98번을 구하기 위해 97, 96번, ......

이렇게 모든 경우의 수를 문제를 해결할 때 마다 구해야 한다면 너무 많은 양의 연산을 수행해야 할 것이다.

 

따라서 이를 효율적으로 해결하기 위해 동적 계획법은 값을 저장하는 기법인 Memoization / Tabulation 방법을 활용한다.

Memoization / Tabulation 은 방법의 차이가 있지만, 간단히 설명하면 문제 해결 과정에서 나온 하위 문제들의 정답들을 기록해두는 것이다. 즉, 필요한 연산이 한 번 수행되었을 때 저장해두었다가 동일한 연산을 수행해야 할 때 다시 연산되는 일 없이 저장된 값을 쓰는 것이다.

 

 

2. 동적 계획법과 분할 정복 알고리즘의 차이는 무엇일까?

이렇게 하위 문제로 분할하는 방법으로는 '분할 정복 알고리즘(Devide and Conquer)'이 있다. 두 방법 사이에는 일부 차이가 있는데 자세한 내용은 별도 포스팅으로 게시하고, 여기에서는 간단히 언급만 하도록 한다.

 

동적 계획법은 답을 구할 때 여러 번 활용되어야 하는 문제들을 하위 문제로 두고 그 값을 '미리 저장해두어' 연산량을 줄이는 기법이다. 반면 분할 정복 알고리즘의 경우에는 너무 크고 방대하여 해결하기 어려운 문제를 순차적으로 해결 가능한 범위까지 나누어진 하위 문제를 해결하며 다시 병합해오는 기법이다.

 

동적 계획법과 분할 정복 알고리즘의 예시를 대표로 들자면, 동적 계획법은 앞서 설명한 피보나치 수열이 있을 것이고, 분할 정복 알고리즘은 퀵 소트가 있다.

 

---

Code

동적 계획법을 더 잘 이해하기 위한 코드를 함께 알아보자.

 

[프로그래머스] 코딩테스트 연습 / 정수 삼각형

 

위와 같은 삼각형이 있다고 하자. 가장 상단에 있는 7에서 출발하여 아래로 내려오는데 내려올 수 있는 방향은 대각선 좌측과 대각선 우측 뿐이다. 즉, 최상단에 있는 7은 3과 8, 3은 8과 1, 8은 1과 0으로 내려오게 된다.

그렇다면 거쳐간 숫자들의 누적이 가장 큰 값을 갖도록 내려온다면, 최대값은 어떤 값일까?

 

이를 해결하기 위해서는 이 문제가 이전에 생성된 과거 값을 활용한다는 것을 이해해야한다.

맨 위층이 1층, 아래로 내려갈수록 2, 3, 4, 5층이라고 정의했을 때, 4층에서 최대값을 갖는 값은 3층에서 최대값을 갖는 값이었을 것이다. 아래 그림으로 함께 살펴보자.

012345

동적 계획법 / 정수 삼각형

최종적으로 3층(8 1 0)에 있는 1까지의 누적 값이 최대가 되기 위해서는 어떻게 해야 할까?

3층의 1에 도달하기 이전 스텝은 2층의 3과 8이다. 즉, 이전의 스텝에서 최대 누적값을 가진 값이 1 위치에서 최대값을 갖는다.

 

1. 2층에 있는 3의 경우에는, 이전 스텝이 7밖에 존재하지 않으므로 누적 값이 10이 된다. (7+3)

2. 2층에 있는 8도 3과 동일하게 이전 스텝이 8밖에 존재하지 않으므로 누적 값이 15가 된다. (7+8)

3. 3층에 있는 1의 경우에는 2층의 3이나 8과 달리, 이전 스텝이 3일 수도 있고 8일 수도 있다. 3에서의 누적값은 10이기 때문에 1이 더해졌을 때 11이 되고, 8에서의 누적값은 15이기 때문에 1이 더해졌을 때 15가 된다. 따라서 최대 누적값을 갖기 위해서는 이전 스텝에서의 최대값이었던 8로 왔을 때 최대 누적값 16을 갖는다. (7+8+1)

 

 

따라서 k층의 어떤 값은 이전 스텝에서의 최대값에 좌우되기 때문에, 이전 스텝 값이 중요하다.

분할 정복법으로 이를 해결하기 위해서는 누적 (최대)값을 저장하며 순차적으로 문제를 해결할 수 있다.

(이 과정이 이해가 안 된다면 손으로 직접 위 삼각형을 계산해보도록 하자)

 

코드를 살펴보면 아래와 같다.

def solution(triangle):
    answer = 0
    # 삼각형 꼭대기에서 바닥까지 순차적으로 이동 (단 1층은 이전 스텝이 없으므로 생략)
    for i in range(1, len(triangle)):
        for j in range(i+1):
            
            # 본 위치에서의 값 (예: 1)
            left = right = triangle[i][j]
            # 이전 스텝(좌/우)의 누적 값 더하기 (예: 10(3) / 15(8))
            if j > 0: left += triangle[i-1][j-1]
            if j < i: right += triangle[i-1][j]
            # 최대값 저장
            triangle[i][j] = max(left, right)
    # 모든 연산 후 맨 하단의 최대 누적값 계산
    answer = max(triangle[len(triangle)-1])
    
    return answer

 

동적 계획법의 경우 개념과 구현 과정, 코드를 함께 살펴보았을 때 더 이해하기 좋을 것 같아 함께 정리해보았다.

동적 계획법에 대해 처음 접하는 경우 이해하기 어려울 수 있으나, 차근차근 살펴보면 어렵지 않을 것이라는 생각이 든다.

 

동적 계획법과 분할 정복 알고리즘의 차이 등의 이 글을 이해하는 데에 도움이 될만한 포스팅을 하게 되면 아래에 링크로 첨부하도록 하겠다.

 

그럼 이만!