Dynamic 해보자.

Greedy

탐욕법(Greedy)는 일단 ~ 우선 가장 빨리 해결할 수 있는 문제를 해결하기 위한 방법을 시행하는 방법이다.

예를들어 생각해보자.

우리가 15kg의 양만 가방에 담을 수 있는데 우리가 담아야 하는 물건들이 각각 12kg, 3kg, 4kg, 2kg, 1kg가 있다. 우리는 이 물건들 중 가능한한 많은 양을 가방에 담아야 한다고 해보자. 이 경우 어떻게 하는 것이 가장 효율적일까?

위에 대한 예제를 해결하기 위해서는 어떻게 하는 것이 좋을까? 가장 무거운 것을 먼저 가방에 담는 것이 좋을까? 아니면 가장 적은 무게의 물건들을 담는 것을 좋을까? 제한된 크기의 가방에 가장 많은 양을 담기 위해서는 가장 적은 양의 무게부터 담기 시작해야 할 것이다.

위와 같이 목적을 달성하기 위한 조건에 대해서 최적의 선택을 내리는 것을 탐욕법(Greedy)라고 한다.

위에서 설명한 탐욕법과 Dynamic programming을 묶어서 설명하는 이유는 무엇일까? Dynamic programming은 갑자기 짠! 하고 나타나는 것이 아니다. 그렇기 때문에 점진적으로 접근하는 방법이 필요한데 이를 위해서 탐욕법으로 시작하는 것이 좋기 때문에 묶어서 설명 되는 것이다.

1. fibonachi

초기에 다이나믹 프로그래밍이 무엇인지 설명하기에 피보나치 수만큼 적합한 것도 없을 것이다. 피보나치는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두항의 합인 수열을 뜻한다.

function fibonachi(number) {
  if (n <= 1) {
    return 0;
  }
  return fibonachi(number - 1) + fibonachi(number - 2);
}

피보나치는 위와 같이 전개된다. 위의 방법은 본래 구현하고자하는 피보나치 수열을 잘 표현하며 잘 작동한다. 하지만 큰 문제가 있는데 이는 작은 숫자에만 해당한다는 것이다.

위의 함수는 fibonachi(1000)에 대한 값은 계산하지 못한다. 이유가 무엇일까? 너무나 큰 시간 복잡도를 가진다. 이에 대해서 계산해보면 아래와 같다.

$$T(n) = 2T(n - 1) + 1 => O(2^n)$$ 시간 복잡도를 계산할 때 정확하게 n 타임을 계산하여 작성하지 않는다. 예를 들어 O(N^3 + 50N + 17) 의 경우 O(n^3) 으로 표기한다. 왜냐하면 이미 n^3 은 이미 그 자체로도 너무나도 큰 값이기 때문에 세밀하게 나타낼 필요가 없다. 얼마만큼의 시간 복잡도를 가질 것인지에 대한 정확한 값이 필요하지 않기 때문에 큰 틀의 값으로 간단하게 표기하는 것이 좋다.

시간 복잡도에대한 표기 규칙

O(1) < O(logN) < O(N) < O(NlogN) < O(n^2) < O(2^n) < O(N!)

반복을 줄이기 위한 방법

1. Top-down( Recursion )

const memo = new Map();

function fibo(number) {
  if (memo.has(number)) {
    return memo.get(number);
  }
  if (n <= 1) {
    return n;
  }
  memo.set(number, fibo(number - 2) + fibo(number - 1));
  return memo.get(number);
}

위의 방법이 Top-down 방식을 사용하여 문제를 해결한 방법이다. 위의 방법은 메모이제이션(Memoization) 을 사용하여 문제를 해결한 것입니다.

잠깐! Memorization이 아니라 Memoization인가요? 이는 오타가 아닙니다! Memoization은 알고리즘을 최적화 하는 기법으로써의 용어이고 계산 결과를 저장하는 기법인 반면 Memorization 은 기억하거나 암기하는 일반적인 과정을 의미합니다!

이 방법은 꼭대기에서 부터 시작하여 아래로 내려가고 재귀 방식을 사용하여 문제를 해결하지만 그 이전의 정보를 저장하여 연산을 줄이고 기존에 O(2^n)이던 시간 복잡도를 O(n) 까지 줄일 수 있기 때문에 효과적입니다.

2. Bottom-up( iteration )

function fibo(number) {
  if (number <= 1) {
    return n;
  }

  const memo = [];
  [memo[0], memo[1]] = [0, 1];

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

위의 방법은 표 작성(Tabulation) 방법으로 문제를 해결한 것입니다. 왜 표 작성이라고 불릴까요? 아래의 과정을 잠깐 봐보죠.

[0, 1, -1, -1, -1]
[0, 1, ,1, -1, -1]
[0, 1, 1, 2, -1]
[0, 1, 1, 2, 3]

문제를 해결하는 방법을 보면 아래에서부터 하나 하나 표를 채워가는 것처럼 보이기 때문에 Tabulation이라고 불립니다.

3. 두 방법 중 뭐가 더 좋은 가요?

모든 DP 알고리즘은 두 가지 방법 중 하나로 구현될 수 있습니다. 하지만 두 가지 방법에는 차이가 있습니다.

상향식(iteration) 방법은 하향식(recursion)보다 일반적으로 빠른 런타임을 갖는다.
하향식 구현은 일반적으로 쓰기가 훨씬 쉽습니다. 재귀에서는 하위 문제의 순서가 중요하지 않은 반면, 표를 사용하면 하위 문제를 해결하는 논리적 순서를 거쳐야 하기 때문입니다.

2. Framework

프레임 워크에 대해서 자세히 알아보기 전에 우리는 상태 변수(State variables)** 에 대해서 알아야 한다. 물론 상태가 무엇인지 알고 있겠지만 DP에서 사용하는 의미에 대해서 알아야 한다는 이야기이다.

DP에서의 상태(State) = 문제의 시나리오를 충분히 설명할 수 있는 변수의 집합이다.

모든 상태에 대해 문제에 대한 답을 계산 / 포함하는 함수 또는 데이터 구조가 있어야 한다.
상태간의 변화와 관련된 재발 관계에 대해서 알아야 한다.
예를들어 현재의 상태에 대한 값을 반환하는 dp()함수가 있을 경우 이 값의 현재 값이 어떻게 만들어지는지에 대한 것을 알아야 한다. dp(i) = dp(i - 1) + dp(i - 2) 와 같이 현재의 상태 변수가 어떻게 변화되는 지에 대한 관게에 대해서 알아야 한다.
베이스 케이스가 있어야 한다. 반복을 계속해서 진행하였을 경우 도착할 수 있는 도착점이 있어야 한다.

Dynamic 해보자.

Greedy

Dynamic Programming

1. fibonachi

반복을 줄이기 위한 방법

2. Framework