동적 계획법(Dynamic Programming)

동적계획법이란, 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결하는 것이다. 

즉, '나'를 해결함으로써 더 큰 '나'를 해결하는 것 => '나'가 두 번 나오는 것으로 봐서 딱 떠오르는게 있다면?!! 바로 재귀호출!

 

즉, 동적계획법은 재귀호출을 사용한다. 

 

동적계획법이 어떤 식으로 활용 될 수 있는지 예제 문제를 통해 살펴보자. 

예) 피보나치 수 구하기 - 피보나치 수열의 n번째 수를 구하시오

풀이 1. 먼저 피보나치 수열의 특성 상 '재귀만 사용하여' 풀 수 있다. 

def getFibo(n):
    if n < 2 :
    	return n
    else:
    	return getFibo(n-1) + getFibo(n-2)

그런데 이 해결법이 가장 효과적일까? 아니다.  이 방법은 이전에 한 번 계산한 적이 있던 것이 다시 반복되서 계산 된다는 문제점이 있다. 

가령 getFibo(3)을 계산 할 때 getFibo(2)+getFibo(1) 에서 이미 계산 된 getFibo(1), getFibo(2)이 getFibo(4)를 계산 할 때 getFibo(3)+getFibo(2) = getFibo(1)+getFibo(2)+getFibo(2) 에서 또 계산 되어야 한다. 

 

이렇게 작은 '나(getFibo)'를 계속 써 먹으니까, getFibo(n)을 구하기 전에 getFibo(n-1) ~ getFibo(1)을 구한 것을 저장해두면 다시 또 계산 할 필요없이 가져다 쓰면 될 것이다! 즉, 나보다 작은 모든 풀이를 먼저 구하고, 이를 이용하자! 는 컨셉이 동적계획법이다. 

 

 

풀이 2. 동적 계획법

※ 동적계획법의 문제 풀이 순서

1. 부분 문제를 정의한다. (무슨 값을 구할지 함수를 정의한다.)

2. 점화식을 구한다. (즉, 부분 문제로 전체 문제를 어떻게 푸는지 나타내는 식을 구한다.)

3. 문제를 해결한다. (코드를 적는다.)

def getFibo(n):
    val = [0, 1]
    if n < 2:
    	return val[n]
    else:
    	for i in range(2, n+1):
        	val.append(val[i-1] + val[i-2])
        return val[n]
     

 

 

 

※ 알고리즘의 문제에 따라 다르겠지만, 저장공간 역시 재활용할 수 있는 문제라면 그렇게 푸는 것이 좋을 것이다. 

이를 슬라이딩 윈도 기법이라고 한다. (참고: 피보나치 수열(Fibonacci numbers)와 동적 계획법(dynamic programming))

def getFibo(n):
    if n < 2:
    	return n
    v0, v1 = 0, 1
    for _ in range(n-1):
    	v0, v1 = v1, v1+v0
    return v1

 

지금까지 buttom up 방식으로 동작하는 동적계획법 알고리즘 풀이방식에 대해서 정리해 보았다. 

 

이를 활용하는 몇 가지 알고리즘 문제를 보자. (문제는 <더보기> 클릭)

1. 직사각형 배치의 경우의 수

문제

---

2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다.

 

입력

---

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 )  

출력

---

가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

 

예제 입력

3

예제 출력

3

 

예제 입력

8

예제 출력

34

 

예제 입력

37

예제 출력

87896

풀이)

코드)

n = int(input())
T = list()
R = 1000007
T[0] = 0
T[1] = 1
T[2] = 2

for i in range(3, n+1):
	T[i] = (T[i-2]%R + T[i-1]%R)%R

print(T[n])

2. 카드 놀이

문제

---

N개의 카드가 주어지고, 각각은 자연수의 점수를 가진다. 철수는 이제 이 카드를 가져감으로써 카드에 적혀있는 수 만큼의 점수를 얻는다. 단, 카드를 가져갈 때 한가지 규칙이 있는데, 이는 연속하여 3개의 카드는 가져갈 수 없다는 것이다. 예를 들어, 6개의 카드 “1 3 5 2 7 3”가 주어질 경우, 3+5+7+3 = 18 만큼의 점수를 얻는 것이 최대이다. N개의 카드가 주어질 때, 얻을 수 있는 점수의 최댓값을 출력하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄에 N개의 숫자가 주어지며, 이는 각 카드의 점수를 나타낸다.  

출력

---

얻을 수 있는 점수의 최댓값을 출력한다.

 

예제 입력

6 1 3 5 2 7 3

예제 출력

18

코드) 

n = int(input())
arr = list(map(int, input().split()))
T = list()

T[0] = arr[0];
T[1] = arr[0]+arr[1];
T[2] = max(arr[0]+arr[1], max(arr[1]+arr[2], arr[0]+arr[2]));

for i in range(3, n):
    T[i] = max(T[i-1], max(T[i-2]+arr[i], T[i-3]+arr[i-1]+arr[i]));
    
print(T[n-1])