[Algorithm] DP(Dynamic Programming) 동적계획법

 

 

동적계획법(DP) 이란?

• 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할때 사용하는 것
• 계산한 값을 저장해두는 메모리 장소 캐쉬(cache)에 저장하고, 답을 여러번 계산(중복)하는 대신 한번 만 계산해서 계산결과를 재활용함으로써 속도 향상을 꾀할 수 있는 알고리즘이다

* 그럼 분할 정복이랑 뭐가 다른건가요?

• 동적계획법과 분할 정복이 차이가 발생하는 부분은 문제를 나누는 방식이다
  • 분할 정복은 단지 큰문제를 작은 문제로 나누어 푸는 것으로 중복된 것이 없다
  • 동적 계획법은 어떤 부분 문제는 두개 이상의 문제를 푸는 데(반복이 일어남) 사용될 수 있기 때문에, 답을 여러번 계산 하는 대신 한번만 계산한다(중복된 것 활용)

 

* 그럼 다른 dfs등 과 같은 재귀함수 쓰는 알고리즘과 뭐가 달라요?

•  일반 재귀로 풀면 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이된다. 즉, 너무 오래걸리고 비효율적이라는 것!!!
  •  n=10만 일경우 , n^2 로 돌경우 시간 복잡도가 어어어어엄청 나게 증가하게 된다…
• DP 는 그에 반해 답을 저장하는 캐시배열인 메모이제이션을 활용하여 중복 횟수를 줄여주어 시간 복잡도가 감소한다. (빠름)
  • 예) dfs 로 시간 제한 걸릴 경우 사용 

 

메모이제이션 (Memoization)

• 함수의 결과를 저장하는 장소를 마련해두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 기법
• 메모이제이션을 활용하여 함수 호출 횟수가 엄청나게 감소될 수 있다
• 이와 같이 두 번이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도 향상을 꾀하는 알고리즘 이다.

 

 * 피보나치 수열 (fibonacci)

• 대표적으로 피보나치 수열을 보면 동적 계획법을 알 수 있다

  dy[i] = dy[i-2]+dy[i-1] 

 

dy[1]=1 ←기본값 셋팅
dy[2]=2 ←기본값 셋팅
dy[3]= dy[1]+dy[2]
dy[4]= dy[2]+dy[3]
…
dy[n]=n ←답

다음 수열값은 이전 수열 과 두 단계 전 수열의 합으로 구성되어 지고, 계속 값을 저장하여 최종해를 구한다. 

function fib(n)
 if n = 0
  return 0
 else if n=1
  return 1
 else
  return fib(n-1) + fib(n-2)

코드로 짜보자면 이러한 함수로 만들 수 있다

 

 

* 그럼 DP는 언제 사용하는 건가요?

• 작은 문제들이 반복될 경우 (규칙 발견)
• 같은 문제들을 구할 때 마다 정답이 같을 경우

 

 

* 동적 계획법 알고리즘 구현 단계 방법?

1. 주어잔 문제를 완전 탐색을 이용해 해결한다
2. 중복된 부분 문제를 한번만 계산하도록 메모이제이션을 적용한다
3. 최적해를 찾는다

 

 

DP 의 종류

• LIS (최대부분증가수열)
• 밸만-포드 알고리즘
• 다익스트라 알고리즘 등등

 

 

출처 

- 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 구종만

- 위키백과, DP