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

안녕하세요. 옆집 컴공생입니다. 오늘은 다이나믹 프로그래밍에 대해 배워 보겠습니다. DP 라고도 부르죠. 다이나믹 프로그램은 알고리즘 문제를 푸는 큰 축인데요. 꼭 익혀놓아야 하는 부분입니다. 컴퓨터적인 사고력을 물어보기에 적합하기 때문에 자주 출제되기 때문이라고 합니다.

 

▶다이나믹 프로그래밍이란 '하나의 문제는 단 한번만 풀도록 하는 알고리즘' 입니다.

 

한번 푼걸 다시 여러번 푸는건 비효율적이겠죠? 이런 알고리즘을 개선시키는 방안입니다. 

 

▷분할 정복 기법(Divide and Conquer)은 동일한 문제를 다시 푼다는 단점을 가지고 있습니다.(정렬과 같은 경우 다시 푸는 경우가 없습니다. 퀵정렬과 병합정렬이 빠른 이유입니다.) 예를 들어 피보나치 수열을 심각한 비효율성을 낳는데요. 피보나치 수열은 특정한 숫자를 구하기 위해 앞에 있는 두 수를 더하는 계산입니다. 

 

1 1 2 3 5 8 13 21 34  ....

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

 

단순히 분할 정복으로 문제를 푼다면 다음과 같은 형식입니다. 15번째를 구한다고 생각해봅시다. D[15]를 구하기 위해서는 뭐가 필요한가요? D[14] 와 D[13] 이죠. 그럼 D[14]는 D[13]과 D[12]입니다. D[13]도 구해야죠. D[12]와 D[11]이 필요합니다. 그냥 단순히 봤는데 벌써 겹치는 원소들이 존재합니다.

피보나치 수열의 그림인데 겹치는 숫자가 상당히 많죠? 이건 메모리상으로나 실행 속도로나 엄청난 비효율을 낳습니다. 심지어 컴퓨터가 한동안 먹통이 되는 상황도 발생하죠. 

 

심지어 이상황은 밑으로 내려갈 수록 계산해야하는 수가 2씩 증가하기 때문에. 계산의 수가 1,2,4,8,16,32 .... 시간 복잡도가 무려 ...무려 O(2^n) 이 됩니다. 즉 50 번째 피보나치 수열을 선택할려면 무려 2^50 의 계산을 진행해야하는데요. 2^10 이 1024이니깐 대략 계산이..1,000,000,000,000,000 정도 되는겁니다. 아무리 컴퓨터라도 이건 너무 많죠. 이처럼 분할 정복 방식은 매우 비효율적인 경우가 많습니다. 이런 경우 우리는 동적 프로그래밍 ,DP 를 사용해야합니다. 

 

▶다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있습니다. 

 

1번. 큰 문제를 작은 문제로 나눌 수 있습니다.

2번. 작은 문제에서 구한 정답을 그것을 포함하는 큰 문제에서도 동일 합니다. 

 

D[13]을 구하는 방식과 D[8]을 구하는 방식은 동일해요(1번가정) 그리고 D[12]를 구하면 이게 D[13]을 푸는데 이용이 됩니다. (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));
    }

d(10)의 경우 출력이 잘 되지만 d(50)을 한 경우  답이 나오지 않습니다. 위에서 말했듯이 어마어마하게 큰 수를 계산하기 너어어어어어어어무 오래 걸리기 때문이죠. 

 

그럼 메모이제이션 기법을 활용해봅시다. 

 

#include <stdio.h>

int d(int x){
	if( x == 1 ) return 1;
    if( x == 2 ) return 1;
    if(d[x] !=0 ) return d[x]; //이미 구한 값
    return d[x] = d[x-1] + d[x-2];
}

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

다음과 같이 이미 구한 값을 배열에 저장해서 구한 값이면 계산하지 않고 바로 꺼내서 쓰기 때문에 시간복잡도가 O(n) 으로 감소되는 기적이! 일어나게 됩니다. 완전 이진 트리에(O(2^N)) 서 왼쪽 자신만 있는 트리를 생각하시면 됩니다. 

 

오늘은 동적 프로그래밍에 대해 배워보았습니다. 여러 문제를 풀면서 감을 익히는 걸 또 포스팅 하겠습니다. 감사합니다.

 

※이 글은 나동빈님의 블로그 글을 보고 포스팅되었습니다.

https://blog.naver.com/ndb796/221233570962

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