알고리즘 설계 - 동적계획법 (Dynamic Programming)

제목은 거창하게 '설계법'이라 했습니다만~ 자세한 내용은 책을 읽어보시길 바래요!

 

문제를 동적계획해서 푼다는게 무슨 소리일까요?

 

예를 들어서 A라는 문제를 해결하는데 그 과정을 B, C, D, E, F, G 사건으로 세분화해서 표현할 수 있다고 가정하고 각 관계가 다음 그래프와 같다고 할게요.

 

그럼 이 문제를 컴퓨터로 코딩하기 위해 반복문을 쓸지 재귀를 쓸지 결정할 수 있습니다.

 

반복문을 수행하려니 for문에 for문을 계속 넣어야할것이고...?

 

for문 밖으로 연산이 벗어나면 한번 사용하고 말 변수를 아주 많이 선언해야합니다. 비효율적이죠!

 

재귀를 수행하려니 E를 수행하기위해 C와 D를 수행할것이고 F를 수행하기위해 마찬가지로 C와 D를 수행해야하고 

 

G를 수행하기위해 E와 F를 한번씩 더 수행해야합니다..

 

재귀는 호출할때마다 스택을 이용하기 때문에 오버헤드가 발생합니다. 그리고 위의 경우는 같은 작업을 여러번 반복해서 수행해야하는 치명적인 단점이 있습니다.

 

이렇게 어떤 문제를 각 사건으로 세분화했을때 사건들끼리 연관관계가 존재하고 특히 같은 사건이 중첩될 경우 메모리를 활용해야 계산이 복잡해지는 과정을 회피할 수 있습니다.

 

이 기법을 동적계획법이라고 합니다.

 

가장 좋은 방법은 B, C, D, E, F를 각각 해결한 다음 그 결과를 배열에 저장해두면 

 

E 사건과 F 사건을 해결할때 C사건과 D사건을 다시 호출하지 않고, 배열에 저장해둔 결과를 활용해서 빠르게 처리할 수 있습니다. 

 

이를 위해 D와 P 배열을 활용합니다. 

 

D는 다음 연산에 미칠 값을 저장하고, P는 어떤 사건이 현재 사건에 영향을 미쳤는지 기록합니다. Parent 예요 ^^;

 

동적계획법에는 또 다른 주요한 규칙이 있습니다.

 

바로 최적화 원리인데요.

 

동적계획법은 문제를 사건으로 잘게 쪼개는 기법을 사용하고 있습니다.

 

잘게 쪼갠 사건들을 하나씩 해결하고, 전부 해결하면 답이 나오는 구조인 것이죠..!!

 

이때 잘게 쪼갠 사건들 또한 답을 갖고 있습니다.

 

전체 문제에 대한 답이 A라고 한다면, 작은 사건들에 대한 답 또한 sub A1, sub A2.. 로 표현할 수 있습니다.

 

동적 계획법은 반드시 A라는 답이 최적의 답이라면, sub A1과 sub A2 또한 최적의 답이 되어야합니다.

 

설계를 하고 코딩을 할때 하위 사건이 최적화된 답을 내놓지 못한다면

 

그 문제에 대해서 동적 계획법은 적절하지 못한 방법일 수 있어요 >-< ;;;

 

이만 마칩니다~