[알고리즘,개념] DP(Dynamic Programming)

DP(Dynamic Programming)

• Dynamic Programming , 컴퓨터에서 이야기하는 Static/Dynamic할 때, 정적/동적의 개념이 아니다.
• 일반적이지 않게 풀기, 멋있는 방법으로 풀기라고 생각해서, Dynamic Programming이라고 지었다고 한다.
• 개념은, 문제의 Scale(size)가 너무 커서, 작은 문제의 답을 구하고, 그 답을 통해서, 최종적인 답을 구할 수 있게 되는 형태의 문제들을 DP문제라고 한다.
• 부분 문제 반복(Overlapping subproblem)과 최적 부분 구조(Optimal Substrcture)를 가지고 있다.

DP는 말로 정의내리기가 참 애매한거 같다. 그래서, 난 DP가 나오게된 배경을 알아봤고, 도움이 된 부분이 있어서 , DP의 등장배경도 적어보려고 한다. (결국, 공부는 얼마나 나한테 와닿냐가 중요하다고 생각한다)

DP 등장배경

DP는 피보나치 수열을 컴퓨터를 이용해서 푸는 과정에서, 이미 했던 연산이 반복되는 결점을 보완하기 위해서, DP가 등장했다고 합니다.

fib의 진행과정을 보면, fib(3),fib(4),fib(2),fib(1) 등, 이미 진행했던 연산임에도, 재귀되며 반복적으로 연산 하는 것을 볼 수 있다. 부분 반복 문제는 항상 새로운 Subproblem을 생성하기보단, 계속해서 같은 Subproblem이 발생되면서, 이 Subproblem이 재활용되거나, 재귀 알고리즘을 통해 해결되는 문제는 DP를 통해 최적화를 시킬 수 있습니다.

 

계속해서 같은 Subproblem 이 부분이 정말 중요한 포인트다.

같은 로직을 계속 쓰는 관계, 수학으로 생각하면, 어떠한 식(점화식)으로 로직이 표현된다는 거다. 그래서, 점화식으로 DP를 많이 풀게 되는거다. 그리고,  Subproblem의 답으로, 결국은 Problem을 Solve할 수있어야, DP를 적용시킬 수 있다. 

 

정리

 

Overlapping Subproblem : 계속해서 같은 로직을 가진 , 작은 문제가 발생.

Optimal Substructure : 같은 로직을 가진 ,작은 문제를 풀고, 그 작은 문제의 답을 통해서 결국 문제를 풀 수 있다.

 

그래서, 이 DP라는 개념으로 다양한 기법들이 나오기 시작했다.

메모이제이션(Memoization)

말 그대로, 메모해놓는 기법이다. 좀 멋있게 보이긴하는데, 우리가 무언가를 기억하기 위해 포스트잇에 잠시 적어놓는거나, 수첩에 뭔가를 기록하는거랑 같다.

 

메모이제이션은 컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써, 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.- by wikipedia

 

운영체제에서는 이걸 Caching 이라고도 하고 , caching hit율이 높을 수록 최적화가 빠르게 되는걸로 생각하면 될듯. cache memory에 우리가 예전에 방문한 사이트나, 작업task가 있다면, 그걸 가져와서 쓰면 엄청 빠르겠죠. 이걸 하나의 단일 프로그램에도 적용시킨게 메모이제이션인듯합니다.

DP의 구현

DP는 Subproblem들이 Problem에 영향을 끼치며, subproblem들을 구하다보면, 자연스럽게 Problem이 Solving된다.

그럼, 어떻게 구현될 수 있을까 .

1. 재귀 (Top → bottoom)
   • 가장 큰 문제 -> 작은문제로 답을 찾는 방식.
   • 재귀 호출을 이용한다. (메모리낭비와 시간이 오래걸릴 수 있다.)
   • 로직을 알아내기 좋다. ( 보통, 점화식 형태로 구현되기 때문)

   • def Fibo(n):
     	if n==0:
         	return 0
         if n==1:
         	return 1
         if dp[n] != -1: 
         	return dp[n]
         
         dp[n] = Fino(n-1) + Fibo(n-2)
         return dp[n]

2. 배열에 어떤 값들을 담고, 반복한다.(Bottom →Top) 
   • 가장 작은 문제 -> 가장 큰 문제로 답을 찾는 방식.
   • 반복문을 이용하게 된다.
   • 코드 구현이 생각보다 까다로울 수 있다.
   • 메모리낭비와 시간을 절약할 수 있다. 

   • def fibo(n):
     	DP[0] = 0, DP[1] = 1
     	for i in range(2,n+1):
         		DP[n] = DP[n-1] +DP[n-2]
         return DP[n]

Summary

1. 문제를 봤을 때, 한번에 답이 도출이 안된다 ? 근데, 그 과정속에 반복적/규칙이 뭔가 있는거 같다 ? ⇒DP 혹은 , Greedy를 생각해 볼 수 있음.
2. 근데, Subproblem을 구하면, 당연하게 Problem을 푸는과정으로 흘러간다 ? ⇒ DP임.
3. DP문제는 완탐을 막기 위해서,경우의수가 엄청 많거나 , 입력이 엄청 큰 경우가 많음.
4. F(N)을 잘 정의해서, F(N-1),F(N-2) 등을 이용해서, 다음 항을 구하는 방법 을 찾아내서, 점화식을 세우는게 포인트임.
5. F(N-1), F(N-2)를 더하던지, 둘 중에서 최댓값을 찾던지, 최솟값을 찾던지, 곱하던지, N이 나오던지 , 등등의 관계를 밝히는게 우리가 할 일임.

* 분할정복vs DP

• 분할정복 : 작은 문제1+작은문제2+작은문제3 = 원래 문제
• DP : 제일작은문제의답 -> 2번째로 작은문제의답 ....-> 결국 최종문제의 답이다.
• 사실, 이렇게 명확하게 나눠지지 않는 경우가 많다고 한다