1. Dynamic Programming 이란?
주어진 문제를 여러 개의 작은 문제로 나누어 풀고, 작은 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 방법
- 하위 문제를 계산한 뒤 그 해결책을 저장
- → 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.
- 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍!
2. 다이내믹 프로그래밍 조건
❗️다이내믹 프로그래밍은 다음 두 가지 가정이 만족할 때 사용한다.
- Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
- Optimal Substructure : 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.
3. 예제
🧩 피보나치수열
1. Recursion + Memoization
- 메모이제이션(memoization)과 재귀로 피보나치수열 문제 풀기
- ⇒ Top-down 방식
function fibMemo(n, memo = []) {
if(mamo[n] !== undefined) return memo[n];
if(n <= 2) return 1;
mamo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
2. Iteration + Tabulation
Tabulation
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 제일 작은 값부터 구해 리스트(도표)에 작성함으로써 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
- 반복문을 이용한 방법은, 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법
- ⇒ Bottom-up 방식
function fibTab(n) {
if(n <= 2) return 1;
// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
let fibNum = [0, 1, 1];
for(let i = 3; i <= n; i++) {
fibNum[i] = fibNum[i-1] + fibNum[i-2];
// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
}
return fibNum[n];
}
🧩 2 × 1 타일링
🌟 문제 개요
세로 길이 2, 가로 길이 n인 2 x n 보드가 있다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 한다.
- 입력값 : n ← number 타입은 1 이상의 정수
- 출력값 : number 타입
🔥 풀이
1. 먼저 입출력 예시를 살펴보자.
2. n = 4인 경우를 생각해보자.
a) 타일을 놓는 방법은 가장 왼쪽부터 세로로 놓거나, 가로로 놓는 것으로 시작한다. 이때 가로로 놓게 되면, 그 바로 아래는 가로로 놓을 수밖에 없다.
b) 위와 같이 시작을 하면 그다음에 채워야 될 나머지 칸의 수는 다음과 같다.
c) 그런데 우리는 이미 나머지 칸을 채우는 경우의 수를 구했다! 바로 각각 n = 3일 때의 경우의 수와, n = 2일 때의 경우의 수이다.
d) 즉, tiling(4) = tiling(3) + tiling(2)인 것이다!
3. 2번을 토대로 base case와 recursive case를 나눠보자. O(2^n)
function tiling(n) {
//base case
//-> n이 0, 1, 2 일때 출력값은 순서대로 0, 1, 2 이다.
if(n <= 2) return n;
//recursive case
return tiling(n - 1) + tiling(n - 2);
}
4. 많이 본 코드이지 않은가? 맞다. 탈출 코드만 살짝 다를 뿐 피보나치와 코드와 같다!
5. 다만, 이 경우는 시간 복잡도가 O(2^n) 이기 때문에 1) 메모이제이션 이나, 2) bottom-up 방법 (1번부터 계산해 n에 도달하는 방법)을 써야 효율적이다. ⇒ O(n)
6. 메모이제이션을 활용한 방법 (dynamic with memoization) O(n)
function tiling(n) {
const memo = [0, 1, 2];
const aux = (n) => {
if(memo[n] !== undefined) return memo[n];
memo[n] = aux(n-1) + aux(n-2);
return memo[n];
}
return aux();
}
7. bottom-up 방법 O(n) 추천
6번의 코드를 보면 이런 의문이 생긴다.
→ 결국 memo 배열에는 1부터 n까지의 경우에 수가 저장되는 것이 아닌가? 그렇다면 굳이 복잡하게 재귀 돌릴 필요 없이 1부터 n까지의 경우의 수를 차례대로 찾아 저장해주면 되겠네.
→ 맞다. 굳이 재귀 필요 없이 for문 돌려서 n이 될 때까지 하나씩 값을 찾아나가면 된다.
function tiling(n) {
const memo = [0, 1, 2];
for(let i = 3; i <= n; i++) {
memo[i] = memo[i-1] + memo[i-2];
}
//어짜피 n <= 2 라면 for 문을 거치지 않으니
//따로 if(n<=2) return memo[n]; 이렇게 조건 쓸 필요 없음
return memo[n];
}
✨ 타일링 문제 연습하기
'자료구조 & 알고리즘' 카테고리의 다른 글
[JS] 백준 11053번 - 가장 긴 증가하는 부분 수열 (1) | 2022.12.17 |
---|