알고리즘 공부하기 (Step 3, Dynamic Programming 이론)

 지난 알고리즘 공부하기 Step1(뭘 공부해야 하지?)와 Step2(입출력 30문제 풀며 이해하기)에 이어서 Dynamic Programming 공부를 하려 한다. 

[공부 방법]

- 지적 호기심이 충분한 사람이나, 도전정신이 강한 사람이라면 이론 공부 후에 바로 문제에 도전 할 수 있을 것이다. 하지만 개인적으로는 강의 영상을 통해 동적 프로그래밍이 무엇이고 어떤 예제들이 있는지, 예제들을 어떻게 접근해서 어떻게 구현(코딩)해 나가는지 몇가지 예시를 보고 깊게 학습하는 것이 흥미를 잃지 않고 '지속 가능한' 학습 방법으로는 좋은 것 같다. 나는 아래의 나동빈님의 영상을 통해 동적 프로그래밍이 무엇인지 감을 잡았다.

- 위의 영상 1번을 시청하고, 2번은 시청하면서 잠시 멈추고 스스로 문제를 풀어보고 풀이를 보고 이해하고 이런 방식으로 하면 좋은 것 같다.

1번 : https://www.youtube.com/watch?v=YHZiWaL49HY

DP 개념 설명 및 예제 풀이 - 1

2번 : https://www.youtube.com/watch?v=kYoKLm8BZtI

DP 예제풀이 - 2

[동적 계획법]

- 수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 적은 시간 내에 풀 때 사용한다. (위키피디아)

 

[동적 계획법을 이해하기 위한 가장 좋은 예시 문제는?]

- 피보나치 수열 계산을 재귀적으로 했을 경우 VS 동적 계획법을 활용 할 경우를 비교하면 정확히 동적 계획법이 무엇인지 알 수 있다.
* 피보나치 수열 (An = An-1 + An-2)

1. 재귀함수로 문제를 해결할 경우.

function 피보나치(i){
    
    if(i == 1 || i == 2) return 1;
    else return  피보나치(i-1) + 피보나치(i-2);
 
}

피보나치(5) 를 계산하기 위해서는?
-> 피보나치(4)와 피보나치(3)을 계산해야 함.

피보나치(3)을 계산하기 위해서는?
-> 피보나치(2)와 피보나치(1)을 계산해야 함.

피보나치(4)를 계산하기 위해서는?
-> 피보나치(3)과 피보나치(2)를 계산해야 함

....
이렇게 나아가다 보면, 피보나치 (4), 피보나치(3), 피보나치(2), 피보나치(1)을 반복 계산하게 되고 이는 계산에 심각한 낭비를 가져온다.
예를들면 피보나치(50)을 계산하기 위해서 49,48를 계산하고 49를 위해서 48,47을 계산하는데 이는 트리구조로 아래로 내려갈 수록 2배의 계산이 필요하다. 총 피보나치(N)을 계산하기 위해 2^50을 계산해야 한다.

"그럼 중복을 기억해서 줄이면 되지 않나?" 이 생각이 바로 동적 계획법이다.

2. 피보나치 수열을 동적 계획법으로 계산할 경우.

int 기억장소[N];
 
function 피보나치(i){
    
    if(i == 1 || i == 2) return 1;
    else if (기억장소[i] != 0) return 기억장소[i];
    else return 기억장소[i] = 피보나치(i-1) + 피보나치(i-2);
 
}

 위와 같이 피보나치 수열 계산을 동적 계획법을 활용하면, '기억장소'를 활용하여 memorize 시키고 이미 푼 문제의 답을 다시 활용한다.
이런식으로 코드를 짜면 각각 한 번만 계산하면 되니 총 N번의 실질적 계산이 이뤄질 뿐이다.