[알고리즘] 동적 계획법(dynamic programming) - fin.

드디어! 마지막입니다!!

오늘 알려드릴 동적 계획법 테크틱은 반복적 동적 계획법 입니다!

지금까지는 재귀 함수를 이용해서 메모이제이션을 하기 위한 저장 공간을 만드는 것을 많이 보여드렸었죠!

반복적 동적 계획법을 이용하면 좋은점이 몇 가지 있습니다!

첫번째로는, 공간 복잡도를 줄일 수 있다는 것입니다!

재귀 함수를 통해서 메모리를 만들어 놓으면 함수 간에 순서가 명확하지 않기 때문에 처음부터 끝까지 사용할 공간을 미리 만들어 놓고,

지우지 않습니다!

하지만, 반복적 동적 계획법을 이용하면 다릅니다. 대표적으로 유용하게 이를 활용하는 것이 슬라이딩 윈도 테크닉입니다!

예전에 삼각형 위의 최대 경로 알고리즘을 푼 적이 있었죠!

재귀 함수를 이용한 메모이제이션을 이용할 때에는, 삼각형의 높이에 따라서 공간 복잡도가 n^2이 되었습니다.

하지만, 반복적 재귀 함수를 이용하면, 결국 현재 계산하고 있는 높이보다 두 단계 아래에 있는 높이는 결국 사용하지 않기 때문에 실제로는 n의 공간 복잡도를 가지고 문제를 풀 수 있습니다!

다음으로는 행렬 거듭제곱을 이용한 동적 계획법입니다!

슬라이딩 윈도와 비슷하게 적용하면, 아주 한정적인 경우에 아주 효과적인 효과를 얻을 수 있는 동적 계획법을 사용할 수 있습니다.

어떤 한 구간에서 다른 구간으로 이동하기 위한 선형 변환 형태의 점화식을 행렬로 나타낼 수 있을 때가 있습니다!

이렇게 C(i)에서 C(i+1)로 변할 수 있는 행렬 연산을 구할 수 있다면, 행렬 연산을 제곱해서 아래와 같은 식을 얻을 수 있죠!

이렇게 되면! 행렬연산이 log 시간밖에 걸리지 않기 때문에, 생각보다 굉장히 빠른 시간에 문제를 해결할 수 있습니다!

피보나치를 예제로 알려드리겠습니다!

우선! 피보나치에서 행에 영향을 줄 수 있는 부분을 생각해봅니다.

fibo(i+1) = fibo(i) + fibo(i-1)이기 때문에 열벡터 안에 2개의 인자만 있으면 충분하겠군요!

그림에서 볼 수 있듯이 fibo(i) = fibo(i) 그대로이고, fibo(i+1) = fibo(i) + fibo(i-1)이므로 다음 행렬을 구하기 위한 연산은

이 되겠군요!

이를 이용하면, 일반화 시켜서 위처럼 나타낼 수 있습니다! (fibo(1) = 1, fibo(2) = 1, fibo(3) = 2 라고 하겠습니다!)

이렇게 나타내면, fibo(i)는 2 행에 있기 때문에 2 행을 구하기 위한 연산식만을 사용하면 됩니다! 

심지어, fibo(0)이 0이기 때문에, 행렬을 i-1번 제곱한 뒤에 2행 2열에 있는 수만 뽑아내면 fibo(i)가 되겠군요.

행렬의 연산은 정사각행렬의 한 행이 m이라고 한다면 입니다. 

따라서, n 번의 제곱을 해야한다고 하면, 시간복잡도는 이 됩니다.

피보나치의 경우에는 m이 2이기 때문에 이 되겠군요!

드디어.. 기나긴 동적 계획법이 끝났습니다!

갑자기 어제 동적 계획법이 끝내고 싶어서 남아있던 4 문제를 내리 풀어버렸네요 핫핫....

근데 저도 행렬쪽은 정말 이해하기 힘들었어요.. 

결국 책에 있던 행렬 연산을 이용한 지니어스란 문제도 풀지 못했네요!

책의 순서에 따르면, 이제 탐욕법 차례이지만 개인적으로 준비하고 있는게 있어서 어떻게 할지는 고민중입니다!