다이나믹 프로그래밍

 

동적프로그래밍이란 동적계획법이라고도 부르는데 문제를 풀기위해 필요한 알고리즘이라기보다 문제를 푸는 방식을 말한다.

 

 

동적프로그래밍은 아래와 같은 특성이 있다. 

• 복잡한 문제(complex problem)를 작은 문제(subproblems)로 나눈다.
• 작은 문제의 해는 복잡한 문제를 풀기위한 부분 해가 된다.
• 복잡한 문제를 풀기위한 작은 문제들은 자주 등장하기(중복) 때문에 작은 문제가 나타날때 마다 계산할 필요 없이 해를 저장해놨다가 동일한 문제가 나오면 재 활용하여 시간을 절약한다.

 

그럼 어떤 알고리즘 문제가 나왔을때 이것을 재귀(recursion)로 풀어야할지, 분할 & 정복(divide & conquer)으로 풀어야할지, 그리디 알고리즘(greey algorithm)으로 풀어야할지 아니면 동적프로그래밍으로 풀어야할지 감이 잡혀야 하는데 동적프로그래밍으로 풀어야하는 문제는 다음과 같은 2가지 특성을 가진다. 이 특성을 만족하면 dp방식으로 풀 수 있다. 

• Overlapping Subproblems
• Optimal Substructure

 

Overlapping Subproblems 

분할 & 정복(Divide and Conquer) 처럼  동적프로그래밍(Dynamic Programming)은 하위 문제에 대한 솔루션을 사용(결합, 조합)하는데  동적 프로그래밍은 주로 동일한 하위 문제의 솔루션이 반복 (again and again)해서 필요할 때 사용한다. 
동적 프로그래밍에서 하위 문제가 이미 계산 되었다면 다시 계산할 필요가 없도록 테이블(ex. 룩업테이블)에 저장했다가 나중에 다시 사용한다고 하였다. 따라서 동적 프로그래밍은 공통적인 (겹치는) 하위 문제가 없다면 동적프로그래밍으로 풀면 안된다.

왜냐하면 솔루션이 다시 필요하지 않은데  솔루션을 저장하는 것은 이점이 없기 때문이다. 

 

동적 프로그래밍에서는 다음 두 가지 방법으로 하위문제들(subproblem)의 해를 저장해 놨다가 다시 재활용하게 되는데  바로

Memoization 과 Tabulation이다.

• Memoization (Top Down)
• Tabulation (Bottom Up)

Memoization (Top Down)

위키백과를 보면 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

 

여기까지는 사실 bottom up 방식도 동일하기 때문에 차이가 없다. 단, bottom up 방식과 차이점은 하위 문제에 대한 해결책이 필요할 때마다 먼저 조회 테이블(해를 저장한 테이블)을 조사하고 사전 계산 된 값이 있으면 그 값을 반환하고 그렇지 않으면 값을 계산하고 결과를 나중에 다시 사용할 수 있도록 조회 테이블에 저장하기 때문에 룩업테이블의 모든 엔트리에 값을 저장하지 않는다.

 

Tabulation (Bottom Up)

bottom up 방식은 메모이제이션과 다르게 하위 문제의 모든 해를 조회 테이블에 저장하게 된다. 

메모이제이션에서는 하위문제의 수요에 따라 계산되어 저장된다면 테뷸레이션에서는 첫 번째 항목부터 시작하여 모든 항목이 하나씩 지는 것이다.다음 코드를 보면   모든 f[n]을 계산하는것 같지만 자세히 보면 f[n]을 계산하기위해 이전에 미리 계산한 값 (f[0], f[1])을 사용하기 때문에 계산에 필요한 오버헤드가 전혀 없다. 

 

 

메모이제이션과 테뷸레이션둘다 순환식의 값을 계산하는 기법들이 둘 다 동적계획법의 일종으로 보기도 하는데 차이점은 
메모이제이션은 top-down방식이며, 실제로 필요한 subproblem만을 푸는 반면 테뷸레이션은 bottom-up 방식이며, recursion에 수반되는 overhead가 없다.

 

 

 

Optimal Substructure

두번째 특성은 optimal substructure 이다.

최적 하부 구조란 ? 컴퓨터 과학에서,문제의 최적 해가 그 하위 문제의 최적 해로부터 얻을 수 있다면 최적 하부 구조를 갖는다고 말한다.
이 속성은 문제에 대한 동적 프로그래밍 및 욕심 알고리즘의 유용성을 결정하는 데 사용되는데 예를 들어, 최단 경로 문제(shortest path problem) 는 다음과 같은 최적 하부 구조 속성가진다. 노드 x가 소스 노드 u에서 목적지 노드 v까지의 최단 경로에 놓이는 경우 u에서 v까지의 최단 경로는 u에서 x까지의 최단 경로와 x에서 v까지의 최단 경로의 조합이 된다.

Floyd-Warshall 및 Bellman-Ford 와 같은 최단경로 알고리즘이  동적 프로그래밍의 전형적인 예이다.

 

 

개념을 알았으니 이제  아래와 같은 동적프로그래밍 문제(Dynamic Programming Problem) 들을 살펴보면서 감을 익히도록하자.

• longest Common Subsequence.
• Shortest Common Supersequence.
• Longest Increasing Subsequence problem.
• The Levenshtein distance (Edit distance) problem.
• Matrix Chain Multiplication.
• 0–1 Knapsack problem.
• Partition problem.
• Rod Cutting.

 

 

 

출처 jackpot53.tistory.com/89

동적프로그래밍(Dynamic Programming)이란?

alg.pknu.ac.kr/t/topic/576

[2018 봄학기 알고리즘]

어쩌다 위 강의 사이트를 알게됐는데 디피 자료가 좋다!