DP

완전검색을 하는데 좀 스마트하게 하는 방법이라고 할 수 있다.

Recursive + Memoization 이라고 할 수 있다.

점화식을 찾으면 된다 .

재귀와 메모이제이션

예제 1. 피보나치 수열

0과 1로 시작하고 이전의 두수 합을 다음 항으로 하는 수열을 피보나치 수열이라고 한다.

0, 1,1, 2, 3, 5, 8, 13...

피보나치 수열의 i번째 값을 계산하는 함수 F를 정의 하면 다음과 같다.
F(0) = 0, F(1) = 1
F(i) = F(i-1)+F(i+1) for i>=2

위의 정의로부터 피보나치 수열의 i 번쨰 항을 반환하는 함수를 재귀함수로 구현할 수 있다.

fibo(n)
	IF n < 2: RETURN n
  ELSE 		: RETURN fibo(n-1) + fibo(n-2)

앞의 예에서 피보나치 수를 구하는 함수를 재귀함수로 구현한 알고리즘은 문제점이 있다.

엄청난 중복 호출이 존재한다는 것.

n번째의 피보나치수를 구하기 위해 알아야 할 값은 fibo(0) ~ fibo(n-1)까지의 값을 알아야한다.

즉 fibo()함수를 n번 호출하여 값을 알면 구할 수 있다.

하지만 ,재귀로 n번째의 피보나치 수를 구할 경우 fibo(n)함수를 호출하게 되면 fibo()함수를 2^(n/2) > n만큼 호출해야한다.

따라서 중복해서 호출하고 있음을 알 수 있다.

메모이제이션

DP의 핵심 기술. 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술.

글자 그대로 해석하면 메모리에 넣기 (to put in memory)라는 의미 이며 기억되어야 할 것 이라는 뜻의 라틴어에서 기원.

피보나치 수를 구하는 알고리즘에서 계산하자마자 저장(memoize), 실행시간을 O(n)으로 줄일 수 있다.

memo를 위한 배열을 할당하고, 모두 0으로 초기화 한다.
memo[0]을 0으로 memo[1]는 1로 초기화 한다.

fibo(n)
	IF N >2 AND memo[n] = 0 
			memo[n] <- fibo(n-1) + fibo(n-2)
	RETURN memo[n]

• 메모이제이션
  • 추가적인 메모리 공간이 필요함.
  • 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우 발생가능

DP(Dynamic Programming)

• 동적계획 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.
• 최적화 문제: 최적(최대값 이나 최소값 같은) 값을 구하는 문제
  • 해당 문제에 여러 해가 있을 수 있다. 특정한 최적해를 구하는 것이 아니라 어떤 최적해를 구하는 것
• DP는 먼저 작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법

DP의 적용 요건

DP를 적용하려는 문제는 필히 다음과 같은 요건을 가지고 있어야 한다.

최적 부분 문제 구조(Optimal substruture)

• 동적 계획법이 최적화에 대한 어느 문제에나 적용될 수 있는것은 아니다. 주어진 문제가 최적화의 원칙을 만족해야만 DP를 효율적으로 적용할 수 있다.
• 최적화의 원칙이란 ?
  • 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것.
  • DP의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해 들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적화의 해들로 구성되지 않는다면 이 문제는 DP를 사용할 수 없다.
• 최적의 원칙이 적용되지 않는 예
  • 최장 경로 문제

중복 부분문제 구조(Overlapping subproblems)

• DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적해를 이용하여 순환적으로 큰 문제ㅡㄹㄹ 해결한다.
  • 순환적인 관계를 명시적으로 표현하기 위해서 DP에서는 일반적으로 점화식을 사용한다.
• DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간에 저장하게 된다.
• 그리고 이렇게 저장된 해들이 다시 필요할때마다 해를 얻기 위해 다시 문제를 재계산하지 않고 table의 참조를 통해서 중복된 계산을 피하게 된다.

분할 정복과 동적 계획법의 비교

• 분할 정복
  • 연관 없는 부분 문제로 분할
  • 부분문제를 재귀적으로 해결
  • 부분문제의 해를 결합
  • 병합 정렬, 퀵 정렬
• DP
  • 부분 문제들이 연관이 없으면 적용 할 수 없음. 즉 부분 문제들은 더 작은 부분 문제들을 공유
  • 모든 부분 문제를 한번만 계산하여 결과를 저장하고 재사용함
  • 분할 정복은 같은 부분 문제가 나타날 경우 재계산함

DP 적용 접근 방법

1. 최적해 구조의 특성 파악하기
   • 문제를 부분 문제로 나눈다
2. 최적해의 값을 재귀적으로 정의하라
   • 부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의한다
3. 상향식 방법으로 최적해의 값을 계산하라
   • 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장
   • 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다(상향식)

예제 피보나치 DP

피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있다,

1. 문제를 부분 문제로 분할
2. 점화식으로 정의
3. 가장 작은 부분 문제부터 해를 구한다. 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

fibo_dp(n)
	f[0] <- 0
	f[1] <- 1
	FOR i in 2 -> n
		f[i] <- f[i-1]+f[i-2]
	RETURN f[n]

예제 동전 거스름 돈 구하기

동전의 종류는 1원,4원,6원 3가지다. 이때 8원을 거슬러주려 한다. 최소 몇 개의 동전을 거슬러 주면 되나?

그리디 : 6 + 1+ 1

최적은 : 4+4

• 1원에 대한 최적해 -> 선택 2원에 대한 최적해 (선택) -> 3원.. 4원....
• C[j] = j원을 거슬러 줄 때의 최적