[개념정리]동적 계획법_nabi

동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. -위키백과-

 

분할 정복과의 차이점

분할 정복은 큰 문제를 해결하기 어렵기에 작은 문제로 나누어 푸는 방법이다. 하지만 이 작은 문제가 포함된 큰 문제에서 이를 다시 풀어야 한다. 이러한 문제를 해결한 것이 동적 계획법이라고 할 수 있다. 동적 계획법은 큰 문제를 작은 문제로 나누어 푼다는 점에서 분할 정복과 유사하지만 작은 문제를 단 한번만 푼다는 점에서 차이점이 있다고 할 수 있다.

 

동적 계획법 풀이

한번만 푼 모든 작은 문제의 답을 어딘가(배열 같은 곳)에 기록해 놓는다. 이러한 작은 문제보다 큰 문제를 풀 경우 앞에서 푼 작은 문제가 다시 나타나면 그 결과값을 불러와 이용하는 방식으로 작동한다. 

 

동적 계획법을 사용할 수 있는 조건

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다. (작은 문제가 반복되는 경우)

2. 작은 문제에 대한 정답이 바뀌어서는 안된다.

 

동적 계획법의 두가지 구현 방법

1. Top-down 방식 : 위에서부터 아래로 내려가는 방식으로 큰 문제에서 작은 문제로 내려가 푼다고 생각하면 된다. (대부분 재귀로 구현된다, 작은 문제를 만났을 경우 이미 계산된 적이 있다면 값을 불러오고 아니라면 새롭게 계산하는 방식으로 작동한다.)

2. Bottom-up 방식 : 아래서부터 위로 올라가는 방식으로 작은 문제에서 큰 문제로 올라가 푼다고 생각하면 된다. (for문과 같은 반복문으로 작은 문제의 값을 구할 때마다 값을 저장하는 방식)

 

동적 계획법의 두가지 구현 방법에 대한 가각의 장단점

Top-down 방식을 사용한다면 재귀 함수를 이용하기에 가독성이 향상된다는 장점이 있다. 하지만 구현에 난이도가 있고 재귀의 단점을 가져올 수 있다는 단점도 가지고 있다.

Bottom-up 방식을 사용한다면 주로 for문을 이용하기에 직관적으로 보이는 구현을 하면 되는 장점이 있다. 하지만 코드가 길어지고 복잡해질 경우 가독성에 문제가 생길 수 있다는 단점도 가지고 있다.