다이나믹 프로그래밍 ( Dynamic Programming )

다이나믹 프로그래밍 문제는 종류가 굉장히 많으며 컴퓨터적인 사고력을 물어보기에 적합하다는 점에서 자주
출제되는 문제이다. 

다이나믹 프로그래밍

• 하나의 문제는 단 한 번만 풀도록 하는 알고리즘
  => 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법
• dp같은 경우 문제에서 규칙성을 찾아서 점화식을 세우는 게 가장 중요하다.

 

다이나믹 프로그래밍을 쓰는 이유

• 일반적으로 상당수의 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다.
  ( 단, 퀵 정렬이나 병합 정렬은 동일한 문제를 다시 푸는 단점이 없다. 그러므로 매우 빠르다. )

 

단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시

   ' 피보나치 수열 '

   피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합을 구해야 한다.

     피보나치 수열의 점화식 : D[i] = D[i - 1] + D[i - 2]

 

  위 공식에 따라서 1, 1, 2, 3, 5, 8, 13, 21, 34 ,55, ... 와 같이 나아간다. 만약 단순하게 분할 정복 기법을 이용해
  15번째 피보나치 수열을 구한다고 가정해보자. 그러면 아래와 같이 그래프의 형태로 진행 상황을 확인할 수 있다.
  D[15]를 구하려면 D[14]와 D[13]을 알아야 한다. 다만 D[14]를 알려면 D[13]과 D[12]를 알아야만 한다. 이런 식으로
  진행이 된다.

 

  따라서 이런 경우 병합 정렬을 할 때처럼 단순한 분할 정복 기법을 사용하면 안 된다. 왜냐하면 이미 해결한 문제를
  다시 반복적으로 해결하여 비효율적이기 때문이다. 위 예제를 보면  D[12]가 벌써 3번이나 반복적으로 계산되었다.
  => 이럴 경우에 동적 프로그래밍 기법을 사용해야 한다!!

 

다이나믹 프로그래밍의 사용 조건

1.  큰 문제를 작은 문제로 나눌 수 있다.
2.  작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

   쉽게 말해 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 후에 처리하여 나중에 전체의 답을 
   구하는 것이다. 다만 이 과정에서 '메모이제이션(Memoization)'이 사용된다는 점이 분할 정복과 다르다.
   메모이제이션이란 이미 계산한 결과를 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을
   단순히 반환하기만 하면 되도록 해주는 것이다. 

 

   피보나치 수열을 예로 들어 문제를 확인해보자.

#include <stdio.h>

int d(int x){
    if(x == 1) return 1;
    if(x == 2) return 1;
    return d(x - 1) + d(x - 2);
}

int main(){
	printf("%d", d(10));
}

  위 경우 답이 55로 잘 출력된다. 하지만 50번째 피보나치 수열을 구하려고 하면 어떻게 될까?

#include <stdio.h>

int d(int x){
    if(x == 1) return 1;
    if(x == 2) return 1;
    return d(x - 1) + d(x - 2);
}

int main(){
	printf("%d", d(50));
}

  실행해보면 아래와 같이 실행은 되지 않고 계속 CPU만 돌아가는 것을 알 수 있다.

 

  그래서 위와 같은 문제를 해결하기 위해 메모이제이션 기법을 활용하면 된다.

#include <stdio.h>

int d[100];

int fibonacci(int x){
	if(x == 1) return 1;
	if(x == 2) return 1;
	if(d[x] != 0) return d[x];
	return d[x] = fibonacci(x - 1) + fibonacci(x - 2);
}

int main(){
	printf("%d", fibonacci(30));
}

위와 같이 해주면 이미 계산된 결과는 배열 d에 저장되기 때문에 한 번 구한 값을 다시 구하는 일은 발생하지 않는다.
이렇게 작업하면 순식간에 계산된 결과가 출력되는 것을 확인할 수 있다. 다이나믹 프로그래밍의 개념을 이해한 뒤에는
많은 문제를 접하여 감을 잡는게 중요하다.