알고리즘 :: 계단 오르기, 피보나치, 메모이제이션

알고리즘 공부하며 배운내용

 

 

계단 오르기

계단을 한 칸씩 or 두 칸씩 올라간다.

계단을 오르는 경우의 수를 구하는 문제

 

 

입력

계단의 높이 N이 입력된다.

예) 4

 

 

출력

N까지 경우의 수 출력

예) 5

 

 

계단 높이 4의 경우의 수는 이렇게 되겠다

• 1칸 - 1칸 - 1칸 - 1칸
• 1칸 - 1칸 - 2칸
• 1칸 - 2칸 - 1칸
• 2칸 - 1칸 - 1칸
• 2칸 - 2칸

 

 

풀이 방법

문제를 보고 이해가 안되는 알고리즘은,

작은 숫자를 대입해보고, 규칙을 찾으려고 해봐야 되는 것 같다.

밑에 풀이 방법을 적어놨지만,

어떻게 이런 방법으로 계단 오르는 방법의 수가 나오는지 이해는 안가고 놀랍기만 하다.

 

그럼 규칙을 찾아보자

계단의 높이가 1일 때 올라갈 방법은 1

2일 때 올라갈 방법은 1칸 1칸 그리고 한번에 2칸 그래서 2

3일 때 올라갈 방법은 1칸 1칸 1칸 / 1칸 2칸 / 2칸 1칸 그래서 3

4일 때 올라갈 방법은 1칸 1칸 1칸 1칸 / 1칸 1칸 2칸 / 1칸 2칸 1칸 / 2칸 1칸 1칸 이렇게 4

표에 넣어봤다 잘 보이게

계단의 높이 N	경우의 수
1	1
2	2
3	3
4	5
5	8
6	13

경우의 수를 보면 무슨 규칙이 보인다.

경우의 수만 써보자

1 2 3 5 8 13

N이 3인경우 N(2)의 경우의 수 + N(1)의 경우의 수 2 + 1 = 3 이네?

N이 4인경우 N(3)의 경웅의 수 + N(2)의 경우의 수 3 + 2 = 5 다!

즉 앞의 두 녀석(N-1) (N-2)의 합이 N의 경우의 수라는 규칙이 보인다.

 

이런 수열(수의 열)을 피보나치 수열이라고 한다네

피보나치 수열 => 구글 검색 링크

 

정리해보면 

N까지 올라가는 방법은 (N - 1)까지 올라갈 방법과 (N - 2)까지 올라갈 방법을 더한 값이라는 말이네

수식으로 표현해보면

N = (N - 1) + (N - 2) 로 나온다.

 

 

코드 without 메모이제이션

피보나치 수열은 우선 재귀함수로 나타낼 수 있다.

// VSCode에서 JavaScript 테스트 하기위한 코드
// 메모장에 테스트 케이스 넣고 stairs.txt로 저장했다.
let fs = require('fs')
const input = +fs.readFileSync('stairs.txt')

// 피보나치 재귀함수
function stairs(n) {
    if(n <= 1) {
        return 1
    }
    else {
        return stairs(n - 1) + stairs(n - 2)
    }
}

console.log(stairs(input));

하지만 이 방법은 엄청 느린 방법이라고 한다.

그 이유를 알아보면

 

계단 높이 N에 5가 들어오면 N(4)와 N(3)이 실행되는데,

N(4)은 다시 N(3) + N(2) 으로 분해가 되고 N(3) + N(2) + N(3)

N(3)은 N(2) + N(1)로 분해가 되고 N(2) + N(1) + N(2) + N(3)

N(2)은 N(1) + N(0)으로 분해가 되어 드디어 2가 되어(return) N(1) + N(0) + N(1) + N(2) + N(3)

 

이제 N(2)를 분해 해보면 밑에 처럼 되고

N(1) + N(0) + N(1) + N(1) + N(0) + N(3)

 

마지막으로 N(3)를 분해하면

N(2) + N(1)

N(1) + N(0) + N(1)

이 된다.

전부 써보면

N(1) + N(0) + N(1) + N(1) + N(0) + N(1) + N(0) + N(1)

코드에서 1이하는 1이라고 적어놨으니

1 + 1 + 1 + 1 + 1 + 1 + 1 +1 = 8이 된다.

 

좀 정리해보면 이런 느낌으로 계속 반복 되는거다 N이 1이 이하가 될 때까지

N(5) = N(4) + N(3)

N(4) = N(3) + N(2)

N(3) = N(2) + N(1)

N(2) = N(1) + N(0)

 

근데 만약! What If!!

N(2)의 값을 저장한다면?

그럼 N(3)는 N(2)를 분해할 필요가 없다.

 

N(3)의 값을 저장한다면?

N(4)는 N(3)을 분해할 필요 없이 값을 가져다 쓰고, 앞에서 저장된 N(2)도 분해할 필요가 없다.

 

이 방법을 메모이제이션(Memoization)이라고 부른다고 한다.

 

 

메모이제이션 적용 코드

재귀함수를 for문으로 바꿨다

// VSCode에서 JavaScript 테스트 하기위한 코드
// 메모장에 테스트 케이스 넣고 stairs.txt로 저장했다.
let fs = require('fs')
const input = +fs.readFileSync('stairs.txt')

// 기본 값들을 넣어주고
let cases = {
    "0": 1,
    "1": 1
}

function stairs(n) {
    if(n <= 1) {
        return 1
    }
    
    // 2부터 n까지 전 값, 전전값을 넣어준다.
    for(let i = 2; i <= n; i++) {
        cases[i] = cases[i - 1] + cases[i - 2]
    }
    return cases[n]
}

console.log(stairs(input));

 

 

참조: Solving Leetcode 70 - Climbing Stairs (JavaScript) (Fibonacci sequence) by Paul Coroneos