🔧변경내용🔨

제목	날짜	내용
발행일	23.04.05

📌들어가기에 앞서

해당 포스트는 Dynamic Programming(DP, 동적 계획법)을 학습한 것을 정리한 내용입니다.

---

🌈 Dynamic Programming(DP, 동적 계획법)

Dynamic Programming(DP, 동적 계획법)은 탐욕 알고리즘(Greedy)과 함께 언급하는 알고리즘으로, 줄임말로 DP라고 한다.

이 알고리즘은, 탐욕 알고리즘과 같이 작은 문제에서 출발한다는 점은 같다.

그러나, 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, DP는 모든 경우의 수를 조합해 최적의 해법을 찾는다.

즉, 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결한다.

하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.

다시 말해, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 다이내믹 프로그래밍이다.

다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있습니다.

Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

---

Overlapping Sub-problems (겹치는 부분 문제)

큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다.

이 가정의 대표적인 예시로 피보나치 수열을 들 수 있다.

피보나치 수열은 첫째와 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합과 같은 수열입니다.

function fib(n) {
	if(n <= 2) {
		return 1;
	};
	return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...

이 함수의 계산 과정을 그림으로 살펴보면, 다음과 같다.

그림에서 본 것을 토대로, 7번째 피보나치 수 fib(7)을 구하는 과정은 다음과 같다.

fib(7) = fib(6) + fib(5)
fib(7) = (fib(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)
...

피보나치 수열은 위 예시처럼 동일한 계산을 반복적으로 수행해야 한다.

fib(5) 는 두 번, fib(4) 는 세 번, fib(3) 은 다섯 번의 동일한 계산을 반복한다.

이렇게, 작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때, 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족한다.

그러나 이 조건을 만족하는지 확인하기 전에, 한 가지 주의해야 할 점이 있다.

주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 한다.

---

Optimal Substructure (최적의 하부 구조)

이 조건에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미한다.

주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 한다.

그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있다.

이 가정의 대표적인 예시로 최단 경로를 찾는 문제를 들 수 있다.

A에서 D로 가는 최단 경로를 찾아야 합니다. 다음과 같이 각 지점이 있고, 한 지점에서 다른 지점으로 갈 수 있는 경로와 해당 경로의 거리는 다음과 같습니다.

A → D로 가는 최단 경로 : A → B → C → D

A → C로 가는 최단 경로 : A → B → C (A → B → E → C 가 아니다.)

A → B로 가는 최단 경로 : A → B

정리해보면 A에서 D로 가는 최단 경로는 그것의 작은 문제인 A에서 C로 가는 최단 경로, 그리고 한 번 더 작은 문제인 A에서 B로 가는 최단 경로의 파악할 수 있다.

이렇게 Dynamic Programming을 적용하기 위해서는, 작은 문제의 최적 해법을 결합하여 최종 문제의 최적 해법을 구할 수 있어야 한다.

---

💻 Dynamic Programming 예시

🥊 Fibonacci

DP를 이용하여 피보나치 수열 문제를 해결하려고 할 때, 크게 두 가지 방식 Recursion + Memoization과 Iteration + Tabulation이 있다.

Recursion + Memoization

다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해놓은 해결책을 이용

이때 결과를 저장하는 방법을 Memoization이라고 합니다.

Memoization?

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거

재귀 함수에 Memorization을 어떻게 적용할지 다음의 예시를 통해 확인하자.

function fibMemo(n, memo = []) {
		// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) {
			return memo[n];
		}
    if(n <= 2) {
			return 1;
		}
		// 없다면 재귀로 결괏값을 도출하여 res에 할당
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo에 저장
    memo[n] = res;

    return memo[n];
}

1. fibMemo 함수의 파라미터로 n과 빈 배열memo를 전달

• 이 빈 배열은 하위 문제의 결괏값을 저장하는 데에 사용

2. memo의 n번째 인덱스가 undefined가 아니라면 :

• 다시 말해 n번째 인덱스에 해당하는 피보나치 값이 저장되어 있다면, 저장된 값을 그대로 사용

3. undefined라면 :

• 즉, 처음 계산하는 수라면 fibMemo(n-1, memo) + fibMemo(n-2, memo)를 이용하여 값을 계산하고, 그 결괏값을 res라는 변수에 할당

4. 마지막으로 리턴하기 전에 memo의 n번째 인덱스에 res 값을 저장

• 이렇게 하면 (n+1)번째의 값을 구하고 싶을 때, n번째 값을 memo에서 확인해 사용할 수 있다.

위의 과정을 이미지로 표현하면 다음과 같다.

• fib(7)을 구하기 위해서는 이전의 작업으로 저장해 놓은 하위 문제의 결괏값을 사용한다.
  n이 커질수록 계산해야 할 과정은 선형으로 늘어나기 때문에 시간 복잡도는 O(N)

Memorization을 사용하지 않고 재귀 함수로만 문제를 풀 경우, n이 커질수록 계산해야 할 과정이 두 배씩 늘어나 시간 복잡도가 O(2n)에 되는 것과 비교하였을 때, 다이내믹 프로그래밍의 강점을 확인할 수 있다.

다이내믹 프로그래밍을 적용한 피보나치 수열에서 fib(7)을 구하기 위해 fib(6)을, fib(6)을 구하기 위해 fib(5)을 호출한다.

이런 풀이 과정이 마치, 위에서 아래로 내려가는 것과 같다. 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식을 Top-down 방식(하향식)이라 부른다.

---

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];
}

1. fibTab 함수의 파라미터는 n 하나뿐다. 만약, n 이 2와 같거나, 그 이하라면 1을 반환한다.

• 피보나치 수열의 첫 번째와 두 번째는 1, 1이라는 것을 기억

2. fibNum이라는 변수에 n 이 1 & 2일 때의 값을 배열을 사용해 저장해 놓는다.

• 피보나치 수열은 1부터 시작하지만 인덱스는 0부터 시작하기 때문에 0번째 인덱스를 채워 줄 dummy data로 0을 삽입한다.

3. 2의 다음인 3부터 n까지 피보나치 수를 구하고, fibNum배열에 저장한다.

4. fibNum의 n 번째 인덱스 값을 반환

피보나치 수열을 총 세 가지 방법(재귀, 탑다운, 바텀업)으로 구현했다.

이렇게 구현한 3가지 방법이 시간 복잡도를 얼마나 효과적으로 개선하였는지 눈으로 직접 확인해야 한다.

세 가지 코드를 크롬 개발자 도구에 복사한 뒤 동일한 수를 입력하였을 때 결괏값을 얻기까지 과연 얼마의 시간이 소요되는지 확인해보자.

시간을 측정하는 방법은 크롬 개발자 도구에서 함수 실행 시간 측정 방법을 참고

크롬 개발자 도구에서 함수 실행 시간 측정 방법

함수의 실행 시간을 측정하는 방법은 여러 가지가 있다. 그중에서 다음의 방법으로 간단하게 함수의 실행 시간을 확인할 수 있다. 실행 환경에 따라 결과가 다르므로 측정 결과는 학습 용도로만 사용하자.

let t0 = performance.now();
함수명(인자); // 여기에서 함수 실행을 시켜주세요
let t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')

재귀 함수

Top-down 방식(하향식)

Bottom-up 방식(상향식)

상향식과 하향식에서의 속도 차이가 발생하는 이유를 생각해보면, 상향식의 경우 작은 하위 문제부터 시작해서 상위 문제를 해결해 나가는 식으로 같은 계산을 반복하지 않고 따로 호출을 할 필요가 없이, 필요한 계산만을 하므로 하향식에 비해 빠르게 나타난게 아닌가 생각된다.

하향식의 경우 하위 문제들을 호출하는 과정이 있기 떄문?

---

🥊 2x1 타일링

[ 문제 ]

2xn 크기의 타일이 주어진다면, 2x1과 1x2 크기의 타일로 채울 수 있는 경우의 수를 모두 구해야 합니다.

n = 1일 땐 경우의 수는 1 : 세로 타일 1개
n = 2일 땐 경우의 수는 2 : 세로 타일 2개 or 가로 타일 2개
n = 3일 땐 경우의 수는 3 : 세로 타일 3개 or 왼쪽 세로 타일 1개 + 가로 타일 2개 or 가로 타일 2개 + 오른쪽 세로 타일 1개

2개의 타일로 빈 곳을 어떻게 채우든 상관없이, 맨 마지막 타일은 세로 타일 1개이거나 가로 타일 2개인, 2가지 경우밖에 없다.

맨 마지막 타일의 경우의 수를 제외했을 때 남는 공간의 마지막 타일도 세로 타일 1개, 혹은 가로 타일 2개인 2가지 경우밖에 없다.

이렇게, DP 문제는 문제 속의 규칙성을 찾는 것이 키 포인트다.

n = 4일 땐 경우의 수는 5 : 세로 타일 1개를 뺀 n = 3과, 가로 타일 2개를 뺀 n = 2일 때의 경우의 수를 더했습니다.

즉, 세로와 가로의 마지막 타일을 제외한 나머지 공간을 채우는 경우의 수와 답이 같습니다.

function tiling2x1(n) {
  let memo = [0, 1, 2];

  for (let i = 3; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2];
  }

  return memo[n];
};

---

📚 레퍼런스

Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges

동적 계획법