[문과 코린이의 IT 기록장] C++ 알고리즘 - 동적 계획법(Dynamic Programming)

[문과 코린이의 IT 기록장] C++ 알고리즘 - 동적 계획법(Dynamic Programming)

[문과 코린이의 IT 기록장] C++ 알고리즘 - 동적 계획법(Dynamic Programming)

 

---

[ Dynamic Programming (동적 계획법) ]

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

< 큰 문제를 작은 문제로 나눠서 푸는 알고리즘의 종류 2개 > 1) Dynamic Programming (DP) - 큰 문제들을 나누었을 때, 작은 문제들이 중복될 수 있다. - 따라서 중복을 효율적으로 처리하는 방법을 파악하는 것이, 문제로 발생함 2) 분할정복 (Divde & Counqer) - 큰 문제들을 나누었을 때, 작은 문제들이 중복될 수 없다.

 

다이나믹 프로그래밍 vs 분할정복

 

---

- 두 가지 속성을 만족해야, 다이나믹 프로그래밍으로 문제를 풀 수 있다.

1) Overlapping Subproblem : 겹치는 작은 문제들

2) Optimal Substructure : 최적부분구조 (문제의 정답을, 작은 문제의 정답들을 통해 구할 수 있다.)

 

---

- 큰 문제를 작은 문제로 쪼갤 수 있으며, 그 작은 문제 또한 다시 상대적으로 큰 문제가 되어 작은 문제를 쪼갤 수 있다.

 

ex. 피보나치수를 구하는 문제

 * 0 / 1 / 2 / 3 / 5 / 8 / 13 / 21 / 34 / 55 ...

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2 (n>=2)

1) 

- 문제 : N번째 피보나치 수를 구하는 문제

- 작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

2)

- 문제 : N-1번째 피보나치 수를 구하는 문제

- 작은 문제 : N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제

.

.

( 이와 같이 문제를 계속 쪼갤 수 있음 )

# 또한, 문제의 정답은 작은 문제의 정답을 합하는 것으로 구할 수 있음.

 

---

- Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

: 따라서 정답을 한 번 구현했다면, 그 정답을 어딘가에 메모해놓는다. (Memoization)

: 이런 메모하는 것을 코드의 구현에서는, 배열에 저장하는 것으로 할 수 있다.

 

---

ex 1 ) 피보나치 수를 구하는 함수

int Fibonacci(int n){
	if(n<=1){
    	return n;
    }
    else{
    	return Fibonacci(n-1) + Fibonacci(n-2);
        // 피보나치 수열이 Fn = Fn-1 + Fn-2로 이루어져 있기 때문
    }
 }

ex 2 ) 중복 호출에 대한 값 저장 

int memo[100]; // 0으로 저장되어 있음
int Fibonacci(int n){
	if(n<=1){
    	return n;
    }
    else{
    	memo[n] = Fibonacci(n-1) + Fibonacci(n-2);
        // memo[n]을 통해, 계산된 n값 저장
        return memo[n];
    }
 }

ex 3 ) memo[n]의 값이 이미 존재할 경우

int memo[100]; // 0으로 저장되어 있음
int Fibonacci(int n){
	if(n<=1){
    	return n;
    }
    else{
    	if(memo[n]>0){ return memo[n]; } 
        // memo[n]이 이미 구해진 값이라면, 그 값을 반환한다.
    	memo[n] = Fibonacci(n-1) + Fibonacci(n-2);
        return memo[n];
    }
 }

 

* 이 함수의 시간복잡도  

= 문제의 개수 x 문제 1개를 푸는 시간

= N x O(1)

= O(N)

---

- 다이나믹의 구현 방식 2가지

1) Top-Down : 큰문제부터 문제를 쪼개가면서 작은 문제를 만들고, 다시 합쳐가면서 원래 문제를 만들어나가는 방식

 ex. 재귀방식

 

2) Bottom-up : 작은 문제들을 모아서 큰 문제를 만들고, 쌓아가는 방식 

 ex. 반복문

int d[100];
int Fibonacci(int n){
	d[0] = 0;
    d[1] = 1;
    for(int i=2; i<=n ; i++){
    	d[i] = d[i-1] + d[i-2];
    }
    return d[n];
}

 

---

* 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :)