메모이제이션 (피보나치, 타일링)

메모이제이션은 변수로 미리 배열의 값을 저장해두고 다음 인덱스의 배열을 만들때 사용할 수 있는 방법이다.

동일한 계산을 반복할때 이전에 계산한 값을 메모리에 저장해두어 불필요한 계산을 없애고 실행속도를 빠르게 한다.

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
출처 - 위키피디아

 

가장 흔히 사용되는 피보나치 수열을 구하는 함수를 살펴보자.

let memo = [0,1]
function fibonacci(n) {
  if(memo[n] === undefined){
    memo[n] = fibonacci(n-2)+fibonacci(n-1)
  }return memo[n]
}

0	1	2	3	4	5	6
0	1	1	2	3	4	5

0번째와 1번째 값이 주어지고 그 뒤로는 앞의 두 값의 합이된다.

그러므로 0,1번째 값만 있으면 2번째 값부터는 0,1번째 값을 활용하여 만들어낼 수 있다.

const memo = [0,1]
//2번째 요소
memo[2] = memo[0] + memo[1]
// memo = [0,1,2]

//3번째 요소
memo[3] = memo[1]+memo[2]
//memo = [0,1,2,3]

---

다른 비슷한 문제로 타일링 문제가 있다.

 

가로세로 2 x n 인 보드에 2x1인 타일을 가지고 보드를 채우는 경우의 수를 구할경우

피보나치 수열과 비슷한 패턴을 보인다.

 

이부분은 외워야 좋은건가?

보통 고등학교때 수학문제처럼 등비,등차수열이 나올법한 느낌을 찾아야겠다!

0	1	2	3	4	5	6
0	1	2	3	5	8	13

 

하지만

2번째 !== 0+1

이므로

 

3번째 부터

1번째(1) + 2번째(2) = 3

 

4번째

2번째(2) + 3번째(3) = 5

 

5번째

3번째(3) + 4번째(5) = 8

 

그래서 메모이제이션을 사용할 때에도 0번째부터 2번째 까지 저장해주어야

뒤의 값을 만들어줄 수 있다.

const memo = [0,1,2]
let tiling = function (n) {
  // TODO: 여기에 코드를 작성합니다.
  // n=1/1 n=2/2 n=3/3 n=4/5 n=5/8
  //메모이제이션
  if(memo[n]===undefined){
    memo[n]= tiling(n-2)+tiling(n-1)
  }return memo[n]
};

 

처음에 n이 1이면 n-2 부분에서 1-2가되어 -1이 되면 어쩌지 ?!했는데

if문에서 이미 걸러지기 때문에 걱정할 필요가 없었다. 

코드를 내가 적어놓고 그런걱정을 하다니!!!