알고리즘 : 동적 계획법 (Dynamic Programming, DP)

동적 계획법은 메모리를 추가로 사용하여 속도를 향상시키는 일종의 테크닉이다. 

 

동적 계획법(이하 DP)은 코딩 테스트 등의 알고리즘 문제를 풀 때 강한 위력을 보이는데 사실 DP 개념은 단지 알고리즘 문제에 국한되지 않는다. 일상생활에서도 우리는 DP를 하고 있다. 계산 중간결과를 적어두거나, 검색해둔 정보를 다시 찾을 필요 없도록 메모장에 모아두는 행위도 DP의 개념이 일부 들어간 행동이라고 할 수 있다.

---

DP의 대표적 예시는 N번째 피보나치수열의 값을 구하거나, N! (N 팩토리얼)의 값을 구하는 것 등이 있다. 이중 N 팩토리얼을 구하는 문제를 통해 DP의 동작을 보이려고 한다.

DP의 아이디어는 "반복해서 연산을 해야하는 부분을 어딘가에 저장해 두고 재사용하자!"이다.

위의 예시에서 5 팩토리얼을 구할 때, 1 팩토리얼부터 2, 3, 4, 5 팩토리얼의 값을 모두 구해 배열에 저장해두었다.

 

이후 3 팩토리얼의 값을 구할 때엔 다시 곱셈을 하지 않고 이미 구해둔 배열에서 3번 인덱스 (= 3 팩토리얼의 값)을 바로 가져오는 모습을 볼 수 있다.

 

뿐만 아니라 자세히 보면 5 팩토리얼의 값을 배열에 넣는 과정도 5 x 4 x 3 x 2 x 1 순서가 아니라 1 x 2 x 3 x 4 x 5 순으로 넣은 것을 볼 수 있다.

 

이것은 5 팩토리얼을 구하는 과정에서부터 DP를 사용한 것이다. 5 팩토리얼을 구하는 단계부터 DP를 사용한 것이 이해가 안 된다면 아래의 테스트를 해보자.

펜과 종이를 가지고 스스로 5 팩토리얼의 값을 구해보자.

5 팩토리얼의 값을 구했다면, 이번에는 6 팩토리얼의 값을 구해보자.

100% 모두 6 팩토리얼을 구할 때 1부터 새롭게 곱하여 계산한 것이 아니라 5 팩토리얼에 6을 곱했을 것이다. 7 팩토리얼을 구할 때도 마찬가지 로 6 팩토리얼 값에 7을 곱할 것 같다.

여기까지 왔다면, 10 팩토리얼을 구할때도 방금 구한 7 팩토리얼에 8을 곱하고, 9를 곱하고 10을 곱하는 순으로 구할 것이다.

자, 다시 위의 예시에서 5 팩토리얼을 구하는 과정을 보자.
1 팩토리얼부터 2, 3, 4...... 를 곱해가며 N 팩토리얼을 구하는 것이 당연하게 느껴진다면 느낌이 왔다고 볼 수 있다.

 

피보나치나 N 팩토리얼, 또는 하노이탑 정도까지는 DP의 입문 단계 문제라고 할 수 있다.

 

아래의 기본 DP 문제를 풀어 보며 응용력을 키워보자

 

2022.08.10 - [알고리즘 온라인 저지/BOJ] - BOJ 2294번 동전 2

BOJ 2294번 동전 2