[알고리즘] DP(Dynamic Programming) 동적 계획법 이해하기

 

 

 

 

 

동적 계획법 Dynamic Programming

DP라고 불리는 동적 계획법은 이름대로 동적인 알고리즘이 아니다. 이름과 관련이 없으니 DP는 그냥 외워야 한다.

 

DP는 큰 문제를 작은 문제로 나누어 재사용하는 방법을 사용한다.
여기서 포인트는 '작은 것으로 나눈다'가 아니라 '재사용한다'를 주목해야 한다.

 

알고리즘을 처음 공부할 때는 DP에 대해 정확히 이해하지 못했다. 작은 문제로 나눈다는 것에만 집중해 분할정복법(Divide&Conquer)과 비슷한 방법이구나 라고만 알고있었다. 하지만 분할정복과 접근 방식만 같을 뿐, 계산 결과를 재사용한다는 점에서 큰 차이점이 있다.

 

 

분할 정복 Divide and Conquer

말 그대로 주어진 문제를 분할하여 작은 문제로 나누고, 작은 문제부터 해결해 병합하여 전체 문제를 해결하는 알고리즘이다.

 

분할 정복은 큰 문제를 작게 나누어 풀어야 하기 때문에 분할을 사용한다. 문제를 풀기 위한 방법 자체가 분할하여 푸는 방식으로 접근해야 하는 것이다. 

이 분할정복을 사용했을 때 오는 문제점 중 하나는 부분 문제 중복이다. 

 

 

부분 문제 중복 Overlapping subproblems

분할해서 계산하는 문제가 여러번 중복되면, 같은 계산을 반복하게 돼서 오히려 효율이 저하된다.
이 문제를 overlapping subproblems이라고 하는데, 문제가 중복되는 점은 DP 알고리즘을 사용할 수 있는 조건으로 요구된다.

'작은 문제로 나눈다'보다는 '재사용'에 포인트를 주었던 이유가 여기서 나온다. 계산 결과를 저장하여 재사용하기 때문에 오히려 문제의 중복은 DP를 사용하는 목적에 알맞다.

 

 

---

 

 

DP 적용 조건

1. 부분 문제 중복 Overlapping subproblems

2. 최적 부분 구조 Optimal substructure

 

 

부분 문제 중복은 위에서 설명한 것처럼 메모리에 저장해둔 계산 결과를 재사용하기 위해 요구된다.
작게 나눈 문제가 중복되는 것이 없고, 다 다른 계산을 해야 하면 굳이 결과를 메모리에 저장해둔 의미가 없을 것이다.
결과를 메모리에 저장해두고, 계산 결과가 중복되면 메모리에서 값을 가져온다.
배열에 넣어두고 빼오는 방법을 주로 사용한다.

 

 

최적 부분 구조는 부분의 최적해로 전체 최적을 구할 수 있다는 것이다.

부분의 최적을 구한다는 것은 Greedy와 동일하다. 하지만 Greedy는 순간마다 최적을 구하는 점에서 DP와 차이가 있다. Greedy는 다음 연산을 고려하지 않고, 지금 주어진 문제에서 최적해를 구한다. 다음을 고려하지 않기 때문에 지역적으로 최적(Local Optimal)이지만, 전체적으로 최적을 보장하지 못한다는 것이 큰 특징이다.

 

 

DP는 부분 최적을 통해서 전체 최적(Global Optimal)을 구한다.

Greedy도 전체 최적을 구할 수 있지만, 무조건 구한다는 보장이 없기 때문에 결과적으로 봤을 때는 DP가 더 좋은 알고리즘으로 보일 수 있다. 하지만 DP는 Greedy보다 연산이 많아 더 오랜 시간이 걸려 상황에 따라서 맞는 알고리즘을 선택해야 한다.

 

만약 DP와 Greedy 두 방법 모두 전체 최적을 구할 수 있다면, 순간의 최적으로 전체 최적을 구하는 Greedy가 더 효율적이다.
(Greedy로 전체 최적을 구할 수 있다는 조건이 성립했을 경우)

 

 

---

 

 

Memoization

계산 결과를 메모리에 미리 저장하는 것을 메모이제이션이라고 한다. 동일한 연산이 반복될 때 과거에 계산한 결과를 메모하고 나중에 사용한다. DP에서 결과를 메모리에 저장해두었다가 사용할  때, 이 메모이제이션이 적용된다.

결과를 미리 저장해 중복되는 연산을 줄인다.

 

DP와 분할 정복의 차이점을 한마디로 정리하면, 메모이제이션 사용이다.

 

 

---

 

 

DP 구현 방법

1. 하향식 접근법 Top-down

큰 문제부터 시작해 작은 문제로 내려가면서 계산하는 것. 위(Top)에서 내려간다(Down)는 의미로 Top-down이라고 한다. 주로 재귀를 통해 해결한다.

 

큰 문제를 해결하기 위해 작은 문제로 내려가고, 그 문제를 해결하기 위해 더 작은 문제로 내려간다.
결국 연산 실행은 작은 문제부터 계산하는데 왜 큰 것부터 시작하는 걸까?
문제가 풀리는 것보다 문제를 해결하려고 하는 관점에서 봐야한다.

큰 문제를 해결하기 위해서 작은 문제로 내려간다. 만약 큰 문제만 보고도 풀어낼 수 있으면, 작은 문제로 내려가지 않아도 될 것이다. 처음 문제 해결을 위해 진입하는 것이 상위 문제, 상위 문제를 위해서 하위 문제로 가기 때문에 top-down

 

 

2. 상향식 접근법 Bottom-up

작은 문제부터 시작해 하나씩 계산해 나가는 것. 하위 문제(Bottom)에서 상위 문제로 올라간다(Up)는 의미로 bottom-up이다. 이 역시 문제를 해결하기 위해 접근하는 관점에서 바라보고 있다. 상향식 접근법은 주로 반복문을 이용한다. 

 

 

 

재귀를 이용하는 하향식 접근법의 경우, 문제를 해결하기 위해 상위 문제 → 하위문제로 재귀 호출이 이루어진다. 재귀문이 계속 반복되다가 최하위까지 다다르고, 그 문제를 해결하고 함수에서 빠져나오면서 하위 문제 → 호출했던 상위 문제로 다시 반환 된다. 

함수 안으로 계속 들어가 문제를 해결하는 과정이 점점 아래로 내려가는 모양으로 볼 수 있다. = 하향식

 

 

반대로 반복문을 이용하는 상향식 접근법에서 데이터가 움직이는 모습을 상상해보자. 반복문의 특징 중 하나는 반복을 할 때 사용하는 반복변수. 반복변수값으로 루프를 제어하고, 얼마나 반복할지 결정하기도 한다. 작은 연산부터 시작해 문제가 해결이 될 때까지 → 반복문의 흐름이 제어될 때까지 연산한다. 

계산이 반복문 속에서 계속 연산되는 모습은 점점 문제가 해결되면서 쌓이는 모양으로 볼 수 있다. = 상향식

 

 

---

 

 

피보나치 수열 DP로 구현하기

코드를 제대로 확인하고 싶어 백준에서 문제를 찾았다. [백준 10826번: 피보나치 수 4]

 

 

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

 

---

 

 

1. Top-Down 방법으로 문제 풀이

import sys

# RecursionError 해결을 위해 재귀 깊이 조절
sys.setrecursionlimit(10**4)


# 전체를 풀기 위해서 아래로 내려가는 방식 = 재귀호출
def fibonacci_topDown(n):
    if n < 2:
        return n
        
    # memo가 0이 아닐 때 True → 모든 인덱스가 채워진 상태
    if memo[n]:
        return memo[n]
	
    # 재귀 호출을 통해 앞의 두 수를 더하고 memo에 저장
    memo[n] = fibonacci_topDown(n-2) + fibonacci_topDown(n-1)
    return memo[n]


# 입력 조건
n = int(sys.stdin.readline())

# 모든 요소 0으로 초기화 → "앞의 두 수"를 더해야 하기 위해 크기는 n+1
memo = [0 for i in range(n+1)]

print(fibonacci_topDown(n))

 

백준에 제출하다보니 RecursionError가 떠서 sys.setrecursionlimit(10**4)를 넣어주었다.
그냥 코드만 테스트할 때는 굳이 사용하지 않아도 된다.

 

 

재귀호출을 이용한 하향식 접근법

피보나치수열은 주어진 수의 앞에 있는 두 수의 합을 구하는 문제로 function(n-1) + function(n-2) 한번의 연산에 함수를 두번 호출한다. 시간복잡도가 $O(2^n)$이 나오는 좋지 못한 알고리즘

 

하향식 접근법과 상향식 접근법을 같은 파일에서 함수로 만들어 호출했는데, n에 큰 값을 넣자 하향식 접근법은 내 컴퓨터에서 결과조차 나오지 않았다. 아마 계속 재귀하면서 연산중이었을 것이다....

 

 

---

 

 

2. Bottom-up 방법으로 문제 풀이

import sys

# 입력 조건
n = int(sys.stdin.readline())

memo = [0 for i in range(n+1)]
memo[0] = 0

# 입력 범위 (o <= n <= 10,000)로 인한 조건문
# 0을 입력받으면 memo[1]에는 값을 주지 않는다
if n > 0:
    memo[1] = 1

# 작은 수(2)로 시작해 n까지 반복하며 계산
for i in range(2, n+1):
    memo[i] = memo[i-1] + memo[i-2]

print(memo[n])

 

여기도 백준에서 주어진 입력 조건으로 if n>0: memo[1] = 1을 추가했다. 
문제에서 "0과 1로 시작한다"고 나와있어 memo[1]=1을 했다가 계속 IndexError가 떴다.

다시보니 입력에 자연수 0부터 입력이 된다고 적혀있었다.
문제+조건까지 잘 읽어볼 것!!!

 

 

반복문을 이용한 상향식 접근법

제일 아래 인덱스부터 시작해 값을 더해주고, 다음 덧셈값을 구하는 방법으로 배열에 저장했다.  재귀호출을 했던 방법과 다르게 반복문을 이용한 방법은 시간복잡도 $O(n)$이 나온다.

같은 DP 알고리즘을 사용했어도 어떻게 구현하는가에 따라서 알고리즘 성능이 크게 차이가 나는 걸 볼 수 있었다.

 

 

---

 

 

위에서 작성한 피보나치 수 계산은 DP 알고리즘의 방식이 적용되었다.

 

 

큰 문제를 작은 문제로 나누어 계산

• 전체적으로 봤을 때는 $0+1+1+2+…+987=1597$이지만, 두개의 수를 먼저 더해가며 계산

 

계산 결과를 저장해두고 나중에 재사용

구현 방법	재사용 값	코드
top-down	함수에서 반환되는 return	memo[n] = fibonacci_topDown(n-1) + fibonacci_topDown(n-2)
bottom-up	이전 반복에서 저장한 index	memo[i] = memo[i-1] + memo[i-2]

 

큰 문제를 작은 문제로 나누어서 그 결과를 저장해두었다가 재사용하는 동적계획법(dynamic programming)은 두 조건을 생각하여 풀어내야 한다.