동적 프로그래밍

분할정복법

문제를 작은 사례로 나누고 각각의 작은 문제들을 해결하여 정복하는 방법이다. 분할정복법은 하향식 접근 방법으로 최상위 사례의 해답은 아래로 내려가면서 작은 사례에 대한 해답을 구함으로써 구한다. 

 

분할정복법 설계전략

1. 문제 사례를 하나 이상의 작은 사례로 분할한다.

2. 작은 사례들을 각각 정복한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다.

3. 필요하다면, 작은 사례에 대한 해답을 통합하여 원래 사례의 해답을 구한다.

 

분할정복법 사례

이진 검색, 합병 정렬, 퀵 정렬, 최대값 찾기 등

 

분할정복법 장점

문제를 나눔으로써 어려운 문제를 해결할 수 있다는 점이다. 그리고 문제를 나누어 해결한다는 특징 상 병렬적으로 문제를 해결하는 데 큰 장점이 있다.

 

분할정복법 단점

함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점이다.

 

동적 프로그래밍

알고리즘을 짤 때 분할정복법을 사용하는 경우가 많은데, 작은 문제들을 반복해서 풀 경우에 나오는 값들을 저장(memoization)하고 재사용하는 기법이 동적 프로그래밍이다. 반복해서 동일한 결과값이 나오는 연산을 하지 않으므로 효율적이다.

 

동적 프로그래밍 가정

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

타일링 문제

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

 

출처

 

https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182

(Algorithm) 동적 프로그래밍(Dynamic programming) - 배낭 문제, LCS 문제, 막대기 문제

https://blog.naver.com/ndb796/221233570962

20. 다이나믹 프로그래밍(Dynamic Programming)