다이나믹 프로그래밍
동적계획법(Dynamic Programming)
복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법
하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용
DP를 쓰는 이유
일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다.
큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다.
예를 들어 피보나치 수열을 살펴보자. 피보나치 수열은 아래와 같다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 …
피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 어떻게 될까? 단순하다. return f(n) = f(n-1) + f(n-2)
그런데 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수 적으로 증가한다.
왜냐하면, f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문이다. 아래의 그림처럼 반복되는 계산을 또 하게 된다.
그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 어떨까? 앞에서 계산된 값을 다시 반복할 필요가 없이 약 200회 내에 계산이 가능해진다.
DP의 사용 조건
다이나믹 프로그래밍은 일반적으로 아래의 두 조건을 만족할 때 사용할 수 있다.
1. 최적 부분 구조(optimal substructure)
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다.
그래서 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다.
만약,** A - B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 할 때, 중간에 X가 있을 때, A - X / X - B가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A - X - B가 정답이 된다.
위의 그림에서 A - X 사이의 최단 거리는 AX2이고 X - B는 BX2이다. 전체 최단 경로는 AX2 - BX2이다. 다른 경로를 택한다고 해서 전체 최단 경로가 변할 수는 없다.
이와 같이, 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있게 된다.
피보나치 수열도 동일하게 이전의 계산 값을 그대로 사용하여 전체 답을 구할 수 있어 최적 부분 구조를 갖고 있다.
2. 반복되는 부분 문제(overlapping sub-problem)
DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다.
그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
위에서 보면 f(3), f(2), f(1)과 같이 동일한 부분 문제가 중복되어 나타난다. 그러므로 우리는 1회 계산했을 때, 저장된 값을 재활용할 수 있게 되는 것이다.
DP의 문제 해결 과정
1. DP로 풀 수 있는 문제인지 확인
우선 DP의 조건 부분에서 써내렸듯이, 현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단해야 한다.
즉, 위에서 쓴 조건들이 충족되는 문제인지를 한 번 체크해보는 것이 좋다.
보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.
2. 점화식 찾아내기 → 일반적으로 가장 핵심적인 부분이다.
점화식: 인접한 항으로 현재 값을 결정하는 관계식을 의미하며 일반적으로 최적 부분 구조를 만족한다는 특징이 있다.
예를 들어 피보나치 수열에서는 점화식은 f(n) = f(n-1) + f(n-2)이다.
점화식의 기본적인 구성 요소
- 초기항
- 인접한 항과의 관계
점화식은 재귀 함수로 표현할 수 있다.
재귀 함수는 종료 조건이 있어야 하는데, 이것이 점화식의 초기항과 같은 역할을 수행한다.
점화식을 코드로 구현하는 방법
- 점화식을 초기항은 종료 조건과 같은 역할을 수행한다.
- 점화식의 내용은 𝑓(𝑥) 의 반환 값에 들어간다.
피보나치 수열에서의 점화식 코드 구현
1
2
3
4
5
6
7
8
9
// 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
function fibo(x) {
// 종료 조건이 없으면 무한 루프
if (x == 1 || x == 2) {
return 1;
}
return fibo(x - 1) + fibo(x - 2); // 실질적인 점화식 부분
}
console.log(fibo(4));
3. 메모하기
변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 한다. 이것을 메모한다고 하여 Memoization이라고 부른다.
변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.
이 결과 값을 저장할 때는 보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다.
피보나치 수열에서의 메모
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
let d = new Array(100).fill(0); // 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
function fibo(x) {
// 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
if (x == 1 || x == 2) {
// 종료 조건(1 혹은 2일 때 1을 반환)
return 1;
}
// 이미 계산한 적 있는 문제라면 그대로 반환
if (d[x] != 0) {
return d[x];
}
// 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
console.log(fibo(99));
4. 구현 방식(상향식/하향식) 결정하기
개념과 DP를 사용하는 조건, DP 문제를 해결하는 과정도 익혔으니 실제로 어떻게 사용할 수 있는지를 알아보고자 한다. DP는 2가지 방식으로 구현할 수 있다.
1. Bottom-Up (상향식 방식)
반복문을 이용해 초기 항부터 계산한다.
아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식
2. Top-Down (하향식 방식)
재귀 함수로 큰 항을 구하기 위해 작은(이전) 항을 호출하는 방식이다
dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
5. 점화식을 실제 코드로 구현하기
1. Bottom-Up (상향식 방식) - 피보나치 수열
1
2
3
4
5
6
7
8
9
10
11
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = new Array(100).fill(0);
// 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1;
d[2] = 1;
n = 99;
// 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for (let i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
console.log(d[n]);
2. Top-Down (하향식 방식) - 피보나치 수열
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = new Array(100).fill(0);
// 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
function fibo(x) {
// 종료 조건(1 혹은 2일 때 1을 반환)
if (x == 1 || x == 2) {
return 1;
}
// 이미 계산한 적 있는 문제라면 그대로 반환
if (d[x] != 0) {
return d[x];
}
// 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
console.log(fibo(99));
DP 문제 예제
예제) 창고 털기
💡 문제 확인
𝑁개의 창고가 있을 때, 얻을 수 있는 식량의 최댓값을 계산해 보자.
이때, 최소한 한 칸 이상 떨어진 창고들만 선택하여 털 수 있다
- 현재 예시에서는 두 번째 창고와 네 번째 창고를 선택했을 때 최댓값인 8을 얻을 수 있다.
💡 창고 털기 문제의 해법
각 위치까지의 최적의 해를 일종의 수열에서의 각 항으로 볼 수 있다. 왼쪽부터 하나씩 창고를 본다고 가정하자.
𝑓(1) : 1번 창고까지 처리했을 때, 최대 식량 값(optimal solution)
…
𝑓(𝑁) : 𝑁개의 창고까지 모두 처리했을 때, 최대 식량 값(optimal solution)
💡 창고 털기 문제 해결 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 정수 N을 입력 받기
n = 4;
// 모든 식량 정보 입력받기
array = [1, 3, 1, 5];
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = new Array(100).fill(0);
// 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0];
d[1] = Math.max(array[0], array[1]);
for (let i = 2; i < n; i++) {
d[i] = Math.max(d[i - 1], d[i - 2] + array[i]);
}
// 계산된 결과 출력
console.log(d[n - 1]);
📑 참고 자료