동적 프로그래밍[Dynamic Programming]

Concept
1. 문제를 더 작은 조각으로 나눈다.
2. 앞에 위치한 조각을 기억한다.
3. 기억하고 있는 조각을 통해서 작업의 양을 줄인다.

 

언제 이것을 사용할 수 있을까?

다음 2가지를 통해서 DP 알고리즘 사용 여부를 알 수 있다.

- 최적화를 할 수 있는 부분 구조의 존재여부 [Optimal Substructure]

- 반복되는 하위 로직의 존재여부 [Overlapping subproblems]

 

최적화를 할 수 있는 부분 구조의 존재여부 [Optimal Substructure]

체크포인트

- 하위 문제의 최적 해답으로 상위 문제의 최적 해답을 구할 수 있는지?

 

A -> ... -> Z로 가는 최적 경로를 구하는 알고리즘과 같은 경우에, 위 사항을 체크해보아야 한다.

A부터 Z까지 도달하는 데에 경로는 무수히 많을 수 있기 때문에 각 단계별로의 최적 경로를 찾아 합할 수 있는지가 중요하다.

사실 체감은 잘 안되기는 한다..

반복되는 하위 로직의 존재여부 [Overlapping subproblems]

체크포인트

- 작은 문제로 나뉠 수 있는지?

- 재활용 될 수 있는지?

 

작은 문제로 나뉠 수 있고, 재활용될 수 있다면?

-> 재활용 가능한 함수 형태로 작은 문제들을 구하고, 그 값을 기억하여 다음 연산에 사용한다.

 

예시

피보나치 수열을 예로 들어보자.

피보나치수열은 앞의 2개 숫자를 더한 값이 그다음 숫자로 나오는 수의 나열이다.

1, 1, 2, 3, 5, 8, 13, ....와 같은 방식으로!

 

이러한 방식은 단순 합의 나열 뿐만 아니라, 함수로의 나열 형태 또한 나타날 수 있다.

즉 앞의 2개의 함수의 연산값이 그 다음 함수의 연산값인 것으로 생각해 볼 수 있다.

함수 트리로 표현해보면,

피보나치수열 예시
                                         fn(5)
                 fn(4)                  +                   fn(3)          
      fn(3)      +       fn(2)               fn(2)      +       fn(1)
fn(2) +  fn(1)

위와 같이 fn(3), fn(2), fn(1)의 연산값이 반복되어 나타나고 있다.

 

값을 저장하는 방식

위 2가지 조건 모두, 하위 문제에 대한 연산값을 기억해야 최적화하고 재활용할 수 있다는 공통점이 있다.

값을 재활용하기 위해서는 계산한 값을 저장해야 한다.

 

피보나치 예시를 활용하여 아래와 같은 코드로 작성해 볼 수 있다.

function fn(n, memo = []) {
  if (memo[n] !== undefined) return memo[n]
  const res = fn(n-1, memo) + fn(n-2, memo)
  memo[n] = res
  return res
}

위와 같이 값을 저장하게 되면, 시간 복잡도는 O(2^n)에서 O(n) 수준으로 급격하게 빨라진다.

거의 수직으로 올라가는 O(2^n)에서 완만한 O(n)으로..

 

위에서 설명한 저장 방식은 위에서 아래로 내려오는 Top-Down 방식이었다.

아래로 내려가면서 하나씩 값을 구하고, 위에서 전부 더해주는 방식이 이전 방식이다.

 

하지만 Bottom-Up 방식도 존재한다. 그것이 바로 타뷸레이션이다.

동적 프로그래밍은 결국 2가지 방식으로 나뉜다.
- 하향식 (Top-Down)
- 타뷸레이션 (Bottom-Up)

 

타불레이션(Tabulation)

타뷸레이션은 보통 루프와 같이 순환을 통해 작업한다.

순환 방식만 있는 것은 아니지만, 공간 복잡도가 더 낮기 때문에 주로 순환 방식을 사용한다고 한다.

 

아래 코드를 통해 방식을 확인해 보겠다.

function fn(n) {
  if (n <= 2) return 1
  const nums = [0, 1, 1] // 피보나치에서 0번째 - 0 / 1번째 - 1 / 2번째 - 1
  for (let i = 3; i <= n; i++) {
  	nums[i] = nums[i - 1] + nums[i - 2]
  }
  
  return nums[n]
}

 

하향식과 타뷸레이션 방식의 차이

하향식은 재귀 방식이기 때문에, 콜스택에 하위 함수들이 대기하고 있다.

하지만 타뷸레이션은 함수를 한번만 호출하기 때문에 하위 함수들이 없다.

 

따라서 n이 증가할수록 하향식은 콜스택 초과 에러가 발생할 수 있는 반면에, 타뷸레이션은 에러가 발생하지 않는다.