1. 동적 프로그래밍

동적 프로그래밍(이하 동프) 이라는 말이 직관적이지는 않다. 동프가 도대체 뭘까? 영어 설명을 살펴보자.

WTF is Dynamic programming

• A method for solving complex problem by breaking it down into a collection of simpler subproblems , solving each of those subproblems just once, and storing their solutions. So it is commonly involved in recursion.

복잡한 문제를 간단한 단위로 나누어서 단위별로 문제를 해결하는것을 뜻한다. 주로 나뉜 조각들중에 같은 조각들이 많아서 하위 문제의 답을 저장한다음에 나중에 같은 하위문제가 나왔을때 다시 계산하지 않고 저장한것을 그대로 사용한다. 주로 하위문제가 겹치는 경우와 그 하위문제의 해답이 합쳐져서 최종 답안이 나오는 경우에 동프를 사용한다.

• It only works on problems with overlapping subproblems & optimal substructure.

• Overlapping subproblems

• A problem is said to have overlapping subproblems if it can be broken down into subproblems which are reused several times. ex) Fibonacci sequence.

  • So we need to use past knowledge to make solving future problem easier. So we store the result of subproblems and take it out to solve the same subproblems! Remember it and apply it!

• Optimal substructure

  • A problem is said to have optimal substurcture if an optimal solution can be constructed from optimal solutions of its subproblems. ex) shortest path from A to D is combined shortest path from A to C and A to B. So in this case optimal structure is shortest path can be presented as A to B to C to D.

동프를 사용하기 좋은 예시로 피보나치 수열이 있다. 한 번 살펴보자

2. 피보나치 수열을 동적프로그래밍으로 개선!

예전에 피보나치수열을 만들어 본적이 있다. 아래와 같다.

// BIG O = O(2 to power of n) super slow!
function fibonacci(num) {
  if (num <= 2) return BigInt(1);
  return fibonacci(num - 1) + fibonacci(num - 2);
}

트리 처럼 잘게 나눠서 아래로 흩뿌려지는 구조를 띈다. 그러나 수가 커지면 매우 느려진다. 진짜 심각하게 느려진다.
그래서 계산을 해나가면서 결과값을 저장하고 똑같은 값을 계산해야한다면 그 값을 꺼내서 그냥 쓰면된다. 예를 들어서 fib(6) 을 계산한다고 했을때, fib(4)가 두번 계산된다 이때 두번째 fib(4)는 계산할 필요가 없다.

그럼 개선된 방법을 사용해보자.

// improved using dynamic programming. soooooooooooooooooo proud of myself!!!!!!!!!!!!!!!

function improvedFib(num) {
  let memory = {};

  function helper(number) {
    if (number <= 2) {
      // memory[number] = 1;
      return 1;
    }
    if (memory[number]) {
      // console.log(memory[number]);
      return memory[number];
    } else {
      return (memory[number] = helper(number - 1) + helper(number - 2));
    }
  }

  return `result:${helper(num)}`;
}

memory에 저장하고 값이 있다면 그걸 return 한다. 획기적으로 빨라졌다. 진짜 획기적으로 말이다. BIG O NOTATION을 비교해보면 O(2 to power of N) VS O(N)이다. ㅋㅋㅋ

하지만 숫자가 10000을 넘어가면 stackoverflow error가 뜬다. space complexity 가 발목을 잡는다. 따라서 이것까지 해결하는 방법을 배워보려고 한다.

바로 tabulation이라는 방법인데 table(주로 array)에 저장해두고 꺼내서 사용하는 방법이다. 이건 recursive가 아닌 for loop을 이용하기 때문에 stackoverflow가 발생하지 않는다.

function tableMemo(n) {
  if (n <= 2) return 1;
  var fibNums = [0, 1, 1];
  for (var i = 3; i <= n; i++) {
    fibNums[i] = fibNums[i - 1] + fibNums[i - 2];
  }
  return fibNums[n];
}

짜잔! 이렇게 계속 발전시켜나갈 수 있다. 생각하자 생각!

마지막으로 코드를 작성하다가 발견해낸 지식인데 정리해보려고 한다. 바로 선언(Statement)과 표현(Expression)의 차이이다.

improvedFib()를 보면 return (memory[number] = helper(number - 1) + helper(number - 2))인데 return 되는 대상은 value assigned 이다. 이게 왜 이렇게 되는지 알아보자.

4. Statement VS Expression

먼저 영어로 해보았다.

Storing and return right hand side in assignment at the same time.. wonderful!

If you return assignement, after assigning , then return the assigned value.

Why is that?

It is because it is an expression not a statement.

Then what is the difference between them? refers to the explanation below.

Explanation

Think of both word literally. statement is act of decleration. so it shouldn't return anything. otherwise things get complicated.

Expression is act of expressing certain message using statment you made in advance. like 'apple'. this word means certain object. round-shape juicy red fruit. so you express the object by using the statment the word 'apple'!

The word 'apple' yields us the object.

The statement is just declarion

In this case above, it doesn't declare new thing from the scratch.

It is just act of expressing something with what i already knew and stated.

Therefore, it is an expression and returns value assigned.

It is not intuitive though.

reference

Statement는 말그대로 처음 선언하는 것을 의미한다. 함수,변수 그리고 while,for 같은 구문을 뜻한다.
반면 Expression은 이미 선언했던것을 사용하는 코드를 의미하는 것으로 보았다. 글자 그대로 생각해보면 된다.
그래서 var x = 1 // undefined 이지만 x + 2 // 3이 된다. 3이 리턴된다. 결과 값이 return 되는 것이다. 따라서 stated 된 모든 함수는 사실 어떤 값으로 수렴되면서 return된다고 생각할 수 도 있다.

그럼 이로써 알고리즘 코스를 다 배웠다. 연습문제로 autocomplete 가 있는데 practice 카테고리에 정리해놓겠다.

그리고 다시 말하지만 이 코스와 관련된 모든 설명과 코드는 깃허브에 private으로 저장해놓았으니 참고바란다.