동적 프로그램과 분할정복의 차이

 동적 프로그래밍 해결 방법은 분할 정복과 유사

• 분할 정복에서는 분할되는 소문제가 소로 독립적이어서 소문제를 다시 순환적으로 풀어 그 결과를 합치면 된다.
• 동적 프로그래밍에서는 소문제가 독립적이지 않아서, 다시 말해서 분할된 소문제간에 중복되는 부분이 있어서 이를 분할 정복 방법으로 풀면 똑같은 소문제를 여러 번 반복해서 풀어야 하는 경우가 발생
• (예) 피보나치 수 fn = fn-1 + fn-2, n >= 2의 계산에 분할 정복 방법을 적용한다면
  f10 계산시에 f9와 f8을 계산해야 하는데 f9 계산시에 다시 f8을 구해야 하므로 f8은 중복해서 계산된다. 동적 프로그래밍에서는 소문제의 해를 표에 저장해 놓으므로 f8은 한 번만 계산하여 그 결과를 표에 저장해 놓고 필요할 때 이 표에서 그 값을 꺼내오면 된다.

동적계획법

Contents

1 정의

2 구현

2.1 접근

2.2 메모이제이션

2.2.1 위 문제에 대한 메모이제이션 적용 예

[edit]

1 정의 ¶

동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.

동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 일반적으로 전산학에서 이용하는 프로그래밍이라는 단어와는 큰 연관이 없다.[1]

[edit]

2 구현 ¶

[edit]

2.1 접근 ¶

동적 계획법의 개념과 구현에 대해 정확하게 짚고 넘어가기 위해 동적 계획법을 적용시킬 수 있는 예에 대해 알아보자.

• f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )
• f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1
  

위와 같이 정의된 함수에서 주어진 임의의 a,b에 대해 f(a,b)의 값을 효율적으로 구하고자 할 때 동적 계획법을 적용시킬 수 있다.

예를 들어 f(2,2)을 계산한다고 해보자. 이 경우 아래 그림과 같은 참조를 거치게 된다.

[PNG external image]

순서대로 계산횟수를 구해보면 f(2,2)를 구하기 위해 총 6번의 연산을 거쳐야한다. 이 때 중복되는 부분 문제[2]에 대한 답을 미리 계산해놓고 연산한다고 가정했을 때 계산횟수를 구해보면 f(2,2)를 구하기 위해 5번의 연산을 거쳐야한다. 이 경우 간단한 예라 중복되는 부분 문제가 f(1,1) 하나 뿐이기 때문에 큰 속도의 이득을 볼 수 없지만 a,b의 값이 커질 수록 속도 면에서 엄청난 이득을 볼 수 있다. 몇 가지 a,b 값에 대해 f(a,b)를 구하기 위한 연산 횟수를 나타낸 아래 표를 참조해보자.

(a,b)	그냥 계산시 연산 횟수	동적 계획법 이용시 연산 횟수
(2,2)	6	5
(4,4)	70	17
(6,8)	3003	49
(10,10)	184756	101

이 정도면 아마 대충 동적 계획법의 효율이 느껴질 것이다. 실제로 a,b가 1증가할 때마다 연산 횟수는 기하급수적으로 증가하며, 이 때 중복되는 부분 문제를 적절히 처리해줌으로써 높은 계산효율을 얻을 수 있는 것이다.

[edit]

2.2 메모이제이션 ¶

위에서 언급한 것과 같이 주어진 함수의 결과를 저장하는 장소를 마련해둔 후[3] 이 값을 재활용하는 최적화 기법을 메모이제이션(memoization)이라고 한다.

메모이제이션은 동적계획법에서 빈번하게 사용되므로 동적 계획법에 대해 제대로 배우고 싶다면 필수적으로 배워두워야할 테크닉이다.

https://mirror.enha.kr/wiki/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95

http://ds.xway.kr/algorithm/a354.html