다이나믹 프로그래밍 (Dynamic Programming, DP)

기본 개념

---

다이나믹 프로그래밍(동적 계획법)은 큰 문제를 여러 작은 문제들의 해결을 통해 풀어가는 알고리즘을 뜻한다. 쉽게 말해 하나의 큰 문제를 쪼개 작은 여러 개의 문제로 만들고, 이 작은 문제들을 해결하다 보면 큰 문제를 해결할 수 있게 된다는 개념이다. (작은 문제들은 큰 문제의 조각들이니까)

 

언뜻 보면 분할 정복(Divide and Conquer)과 비슷하게 생각할 수 있지만 다이나믹 프로그래밍이 가진 다음 두 가지 조건으로 분할 정복과 구별된다. 

• 최적 부분 구조(optimal substructure)
• 중복된 하위 구조(overlapping subproblems)

최적 부분 구조는 현재 최적 선택이 전체 최적 선택이 되어야 한다는 조건이다. 큰 문제를 여러 작은 문제들로 나눠놨으니 이는 당연한 조건이라고 볼 수 있다. 중복된 하위 구조는 말 그대로 큰 문제에서 나눠진 작은 문제들이 서로 중복되는 것을 뜻한다. 즉, 동일한 작은 문제들을 여러 번 구해야 하는 구조다. 이 경우에는 실제로 여러 번 구하지 않고 한 번만 구한 뒤, 이후에 이를 반복적으로 사용한다.

 

추가로 알고리즘 이름 때문에 동적 메모리 할당(dynamic memory allocation)과 같은 것을 생각할 수 있는데 사실 이름은 큰 의미없이 붙여졌다고 한다. 해당 알고리즘을 고안한 리차드 벨만에 따르면 그냥 멋있어서 붙인 이름이라고. 오우 놀 줄 아는 놈인가?

 

 

 

예시

---

우선 본격적으로 예시를 시작하기 전에 알아야 할 한가지 개념이 있다. 바로 '메모이제이션(memoization)'이다. 앞서 얘기했 듯, 다이나믹 프로그래밍은 중복 하위 구조를 가진 문제에 사용된다. 즉, 같은 값이 여러 번 나오는 경우에 사용한다. 이때 같은 값을 가지게 되는 작은 문제들을 매번 연산하는 것이 아니라 한번 연산 후, 이를 저장하고 이 값을 반복적으로 사용한다. 이를 '메모이제이션'이라고 한다. 쉽게 생각해 메모해두고 꺼내 쓴다는 뜻이다.

 

다이나믹 프로그래밍을 설명할 때 사용되는 가장 대표적인 예시가 바로 피보나치 수열이다. 피보나치 수열을 통해 설명을 진행하도록 하겠다. 피보나치 수열을 모르는 사람들을 위해 간단히 설명해보자면 첫 두 항이 1이고 그 이후 나오는 모든 항부터는 앞선 두 개의 항을 더한 값인 수열이다. 즉, [1, 1, 2, 3, 5, 8, 13, 21...] 이런 식으로 진행되는 수열이다. 아래 그림을 살펴보자.

 

첫번째 그림은 피보나치 수열의 원리를 나타낸 그림이다. 두 번째는 해당 그림을 토대로 여섯 번째 항까지 직접 구해본 것이다. 이제 그 특징이 조금 보이는가? 세 번째 항인 2를 만들기 위해선 첫 번째, 두 번째 항을 더해야 한다. 다섯 번째 항을 구하기 위해선 세 번째 항과 네 번째 항을 더해야 한다. 세 번째 항은 첫 번째 항과 두 번째 항의 합, 네 번째 항은 세 번째 항과 두 번째 항의 합인데, 여기서 또 세 번째 항은 첫 번째 항과 두 번째 항의 합이다. 여기서 알 수 있듯, 같은 계산이 계속 반복된다.

 

그렇다면 계산을 수행할 때마다 값을 저장해두고 해당 계산을 수행해야 할 때, 실제 계산을 수행하는 것이 아니라 해당 값을 꺼내 쓰면 연산이 훨씬 줄지 않겠는가? 즉, 다이나믹 프로그래밍을 이용하면 계산을 훨씬 줄일 수 있다는 말이다. 그렇다면 다이나믹 프로그래밍을 이용해 이를 구해보도록 하자.

# 구하고 싶은 항 입력
testNum = int(input())

# 메모이제이션 수행 배열
memoization = [0 for i in range(testNum+1)]
# 피보나치 수열의 첫번째 항과 두번째 항 값 입력
memoization[1], memoization[2] = 1, 1

# 피보나치 수열 구하기
for i in range(3, testNum+1):
    memoization[i] = (memoization[i-1] + memoization[i-2])

# 구하고 싶은 항의 값 출력
print(memoization[testNum])

굉장히 간단한 코드이기 때문에 큰 설명 없이도 금방 그 원리를 이해할 수 있을 것이다. 여기서 중요한 것은 메모이제이션 역할을 수행하는 배열과 피보나치 수열 구하는 for문이다. 각 항들을 미리 저장해 두고 그때그때 불러와서 중복된 연산 수행을 막아줬다. 만일 이를 다이나믹 프로그래밍이 아니라 재귀 함수를 통해 구했다면 이런 형태였을 것이다.

def fibonacci(subNum):
    if subNum == 1 or subNum == 2:
        return 1
    else:
        return (fibonacci(subNum-1) + fibonacci(subNum-2))

print(fibonacci(int(input())))

위 코드대로라면 각 숫자를 구할 때마다 fibonacci라는 함수를 반복적으로 호출해야 한다. 즉, 중복된 연산이 반복적으로 이루어진다는 것을 알 수 있다. 이를 통해 다이나믹 프로그램은 반복되는 연산을 줄여주어 효율적으로 결과를 도출할 수 있는 알고리즘이라는 것을 확인해볼 수 있다.

 

 

 

Top-Down과 Bottom-Up

---

다이나믹 프로그래밍은 두 가지 방법을 통해 구현할 수 있다. 바로 Top-Down 방식과 Bottom-Up 방식이다. 이름 그대로 상향식 방법과 하향식 방법인데, 조금 더 자세히 살펴보도록 하자

 

Top-Down

---

하향식 방법이라고도 한다. 큰 문제를 해결하려 했을 때, 작은 문제가 해결되어있지 않다면 그때 작은 문제를 해결하러 가는 방식이다.

def fibonacci(memoization, subNum):
    if memoization[subNum] == 0:
        if subNum == 1 or subNum == 2:
            memoization[subNum] = 1
        else:
            memoization[subNum] = (fibonacci(memoization, subNum-1) + fibonacci(memoization, subNum-2))
        return memoization[subNum]

    else:
        return memoization[subNum]

testNum = int(input())
memoization = [0 for i in range(testNum+1)]
print(fibonacci(memoization, testNum))

얼추 보면 위의 재귀방식과 비슷할 수 있다. 실제로도 재귀 함수가 쓰이고 있기도 하고. 하지만 메모이제이션을 통해 아직 구하지 않은 값이 있다면 함수를 호출해 연산하고, 값이 있다면 바로 값을 리턴해 불필요한 연산을 줄였다는 큰 차이점을 확인할 수 있다.

 

Bottom-Up

---

상향식 방법이라고도 한다. 작은 문제들을 먼저 해결하고 이를 기반으로 큰 문제를 해결하는 방법을 의미한다. 앞서 다이나믹 프로그래밍을 설명하며 구현했던 피보나치 수열 코드가 바텀업 방식이기 때문에 코드는 생략하도록 하겠다.

 

 

 

예시 문제

---

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

 

 

참고

---

https://devsub.tistory.com/2

동적 프로그래밍 (Dynamic Programming)

https://velog.io/@kimdukbae/다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

https://galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?