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

안녕하세요. yeTi입니다.
오늘은 알고리즘 공부 중 동적계획법 (Dynamic Programming)에 대해 학습한 내용을 공유하려고 합니다.
강의 : 권오흠 교수님의 2015 봄학기 알고리즘

개요

동적계획법 (Dynamic Programming)은 순환식을 기반으로 문제를 해결하는 기법입니다.

Memoization(캐싱)도 동적계획법 (Dynamic Programming)의 일부로 볼 수 있는데요. 두 방식의 차이점은 Memoization(캐싱)은 top-down 방식을 취하며 캐싱되지 않은 subproblem만 풀어나가는 반면, 동적계획법 (Dynamic Programming)은 bottom-up방식으로 필요한 계산을 사전에 해나가는 방식으로 볼 수 있습니다.

동적계획법 (Dynamic Programming)은 recursion을 사용하지 않기 때문에 recursion의 특징인 함수 stack을 쌓지 않아 overhead가 없는 장점이 있습니다.

샘플 코드는 깃헙을 통해 확인하실 수 있습니다.

적용 문제

동적계획법은 순환식이라는 식을 활용하여 문제를 접근하기 때문에 수치적인 값을 구하는 문제에 활용할 수 있습니다.

즉, 최적화 문제(optimisation problem)나 카운팅(counting)문제에 적용할 수 있습니다.

여기서 최적화 문제란 최소값이나 최대값같은 값을 찾는 문제를 의미합니다.

분할정복법

동적계획법은 원래 문제를 작은 부분으로 나눠 문제를 해결한다는 맥락에서 분할정복법과 비슷합니다.

하지만 차이점은 분할정복법은 각 분할된 문제가 서로 독립적인 집합을 이루지만 동적계획법은 분할된 문제를 중복으로 활용한다는 점입니다.

순환식

동적계획법을 사용하기 위해서는 순환식을 만드는것이 매우 중요합니다. 왜냐하면 특정 문제의 optimal substructure를 수학적으로 표현한 것이 순환식이기 때문입니다.

순환식이란, 해당 문제를 subproblem으로 나누고 subproblem의 해를 어떤식으로 조합해서 original problem의 해를 구할 수 있는지를 표현한 것입니다.

Optimal substructure 여부를 확인할 수 있는 방법은 최적해의 일부분이 그부분에 대한 최적해인가? 에 대한 답을 해보는 것입니다.

느낀점

동적계획법 (Dynamic Programming)을 접하고 나서 문제를 수식으로 표현할 수 있다는 부분에서 신기하다 못해 신비롭다는 느낌이 들었습니다.

개인적으로 가지고 있단 직관적인 문제 해결법은 경우의 수를 다 해보고 원하는 결과를 얻는다 였는데, 이를 수식의 관점에서 접근하여 보다 논리적인 해결법을 찾을 수 있다는 것이 재미있게 다가왔던거 같습니다.

물론 연습을 통한 훈련만이 실무에 적용할 수 있는 능력을 가질 수 있지만 개발을 바라보는 관점에서 시야가 확장된거와 같은 느낌이 들어 유익한 시간이었습니다.

효율적인 코딩을 원하는 개발자라면 공부해보시는것을 추천드립니다.

관련 강의

• [알고리즘] 제18-1강 동적계획법 (Dynamic Programming)
• [알고리즘] 제18-2강 동적계획법 (Dynamic Programming)
• [알고리즘] 제18-3강 동적계획법 (Dynamic Programming)
• [알고리즘] 제18-4강 동적계획법 (Dynamic Programming)
• [알고리즘] 제18-5강 동적계획법 (Dynamic Programming)
• [알고리즘] 제18-6강 동적계획법 (Dynamic Programming)

관련 글

• 알고리즘 공부 - 압축
• 알고리즘 공부 - 최단경로
• 알고리즘 공부 - 최소비용신장트리
• 알고리즘 공부 - 그래프
• 알고리즘 공부 - 해싱
• 알고리즘 공부의 필요성
• 알고리즘 공부 - 트리
• 알고리즘 공부 - sort
• 알고리즘 공부 - recursion
• 알고리즘을 공부해야하는 이유