[알고리즘] DP(Dynamic Programming: 동적 계획법) 알고리즘

DP (동적 계획법)
하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고
그 결과를 이용하여 다시 큰 문제를 해결할 때 사용하는 것

 

DP가 적용되기 위해선

1.  겹치는 부분이 존재해야한다.

    문제를 작은 문제로 나누고 그 결과값을 저장한다. 저장한 값을 재활용하여 전체의 답을 구할 수 있을 때 사용한다. 

    즉, 겹치는 부분이 존재하지 않는다면 결과값을 저장해도 쓸모가 없기 때문에 dp를 사용할 수 없다.

 

2.  최적 부분 구조

    작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야한다.

    문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성된 문제 구조를 말한다.

 

 

DP 적용 방법

DP는 점화식의 연속이다. 점화식을 진행하는 방식에는 2가지가 있다.

1. Top-Down 방법

: 위에서 아래로 접근하는 방법으로, 큰 문제에서 부분 문제로 쪼개가면서 문제를 풀어가는 방식 => 재귀 사용

int fiboData[100] = {0,};

int fibo(int n)
{
  if (n<=2) 
    return 1;
  if (fiboData[n]==0)
    fiboData[n] = fibo(n-1) + fibo(n-2);
  return fiboData[n];
}

n을 구하기 위해 n-1식을 호출하고 계속해서 작은 값들로 쪼개지는 방식이다.

위 코드에서는 최근 값을 저장해두고 그 값을 이용하여 계속해서 계산하는 메모이제이션을 사용하여 진행되었다.

fibo[n] = fibo(n-1) + fibo(n-2) , fibo(n-1)과 fibo(n-2) 호출됨, fibo(n-1) = fibo(n-2) + fibo(n-3) .... 이런식으로 점점 쪼개짐

fibo(n)을 구하기 위해선 fibo(n-1)와 fibo(n-2)의 값을 알아야한다. 

또한 fibo(n)의 값을 중복계산하지 않기 위해서 fiboDate[] 배열에 계산값을 저장해둔다. <메모이제이션>

 

2. Bottom-Up 방법

: 아래서 위로 접근하는 방법으로, 부분 문제에서부터 문제를 해결하여 점차 큰 문제를 풀어가는 방식 => 반복문 사용

int fibo(int n)
{
  fibodata[0] = 0;
  fiboData[1] = 1;
  for (int i=2; i<=n; i++)
    fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
  return fiboData[n];
}

0에서 부터 시작하여 각 값을 저장하고 n에 도달하는 방식

즉 fibo[0], fibo[1] 구하고 이를 이용해 fibo[2] 구함 , 1,2로 fibo[3] 구함 ... n까지 계산

 

 

+참고하면 좋을 문제

https://hihajin.tistory.com/34#toc14

백준 1003번 : 피보나치 함수 | 메모이제이션, dp 알고리즘 [C++]

#메모이제이션 #dp 알고리즘 #피보나치 

 

+ 추천 문제

11726번: 2×n 타일링 (acmicpc.net)