Skip to content

Latest commit

 

History

History
90 lines (56 loc) · 6 KB

memoized-fibonacci.md

File metadata and controls

90 lines (56 loc) · 6 KB

Memoized Fibonacci

memoization(메모이제이션)을 나는 이렇게 이해했다. 단순하게 메모하다라는 의미로 생각하면 이 말의 원 뜻을 이해하기 쉬운 것 같다.😅

메모이제이션에 대한 위키에서의 정의이다. 컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 결과값을 메모리에 저장함으로써 동일한 계산을 반복하는 것을 제거하여 프로그램 실행속도를 높이는 기술을 뜻한다. 이는 동적계획법(다이다믹 프로그래밍)의 핵심 개념이다.

WIL(What I Learned this problem)

memoized-fibonacci 구현하기 앞서 알아야 할 것이 있다. 기존에 구현했던 피보나치(문제 18번) 해결방법에 대해 생각해보겠다.

40까지의 피보나치 수열을 구할 때의 실행시간

fibonacci1 time: 1359.498ms : 재귀 이용
fibonacci2 time: 0.154ms    : 반복문 이용

이를 보면 재귀와 반복문의 차이가 어마어마한 것을 알 수 있다. 재귀를 이용하는 경우 50일 때의 경우는 한참을 기다려야했다.

실행속도에 차이가 있으나 각각의 풀이에는 장단점이 존재한다.

✅ 재귀를 이용한 풀이

  • 장점

    • 가독성이 좋다.

  • 단점

    • 구조적으로 연산과정에서 중복되는 부분이 많이 발생한다. 숫자가 커지는 경우(연산이 많아지는 경우) stack overflow 같은 에러가 발생하기 쉽다.

      fibonacci

      위 이미지는 n이 7일때 피보나치수를 구하는 과정을 표현한 것이다. 같은 과정이 얼마만큼 반복되는지를 살펴보자

    • 중복되는 과정 속에서 비싼 작업인 함수를 지속적으로 호출하고 있다.

✅ 반복을 이용한 풀이

  • 장점
    • 재귀보다 효율적이다. 단순하게 걸리는 시간만을 비교해봐도 확연히 차이가 난다. 시간복잡도는 O(n)이다.
  • 단점
    • 이 역시 n이 커지면 효율이 떨어진다.

위의 두 풀이의 공통된 단점은 무엇일까? 어쨌든 n이 커지면 커질수록 효율이 굉장히 떨어진다는 점이다. 그래서 이러한 단점을 보완하기 위해서 맨 위에서 설명한 메모이제이션이라는 방법을 사용해서 중복을 제거하여 연산 할 수 있다.

메모이제이션 방법을 사용하기 위해선 저장 공간을 마련하면 된다. 나의 풀이에는 배열을 만들었지만, 객체를 사용할 수도 있다. 배열의 인덱스에 해당하는 number에 대한 피보나치 수의 결과값을 저장한다. 그리고 피보나치 함수를 호출할지 말지를 배열 안에 결과값이 있는지 없는지를 확인한 후에 결정하면 된다.

const memo = [0, 1];

function memoFibonacci(number) {
    if (!memo[number]) {
        //재귀함수를 호출한다.
    }
}

위 코드는 내가 했던 실수이다. memo[number] 값의 유무로 조건을 걸어주게 되면 memo[number] 이 0인 경우도 역시 조건문 안으로 들어와서 재귀함수를 호출한다. 즉 재귀를 끝낼 수 있는 조건이 제대로 동작하지 않게 된다. 그렇기 때문에 stack overflow 에러를 마주하게 되었다.😭

일반 재귀와 메모이제이션 재귀를 비교해보았다. n은 10을 기준으로 함수를 몇 번 호출하는지 여부를 체크해봤다. 일반 재귀 풀이는 177번의 함수 호출이 있었다. 반면 메모이제이션을 이용한 재귀 풀이는 단, 19번의 함수 호출을 하였다. 이것만 비교해봐도 효율의 차이가 느껴진다.😵

40까지의 피보나치 수열을 구할 때의 실행시간

fibonacci1 time: 1359.498ms : 재귀 이용
memoFib: 5.964ms            : 메모이제이션 재귀 이용

fibonacci2 time: 0.154ms    : 반복문 이용

위 실행시간를 비교해보면 어마어마하다는 것을 느낄 수 있을 것이다.

결론

위의 결론을 보면 사실상 재귀를 사용하면 복잡도가 올라가서 별로 효율적이지 못한 코드가 된다는 것을 느낄 수 있었다. 또한 재귀를 어떤 식으로 사용하는지에 따라서(메모이제이션을 어떻게 활용하는지에 따라서) 좋은 재귀를 만들 수 있을 것이라고 생각한다. 어쨌든 재귀라는 것은 효율성, 최적화라는 측면에서 부담스러운 것은 사실이다. 그럼에도 재귀는 많이 사용되고 있다. 그 이유는 이러하다.

재귀를 사용하면 코드가 짧아지고 코드 이해도가 높아지며 유지보수에도 이점이 있습니다. 
모든 곳에서 메모리 최적화를 신경 써서 코드를 작성해야 하는 것은 아닙니다. 
우리가 필요한 것은 좋은 코드입니다. 이런 이유 때문에 재귀를 사용합니다.

모던 자바스크립트 재귀와 스택 이렇게 표현 되어있다.

내가 재귀의 의도를 가지고 구현해 본적이 그렇게 많지 않다. 가장 기억에 남는 것은 지뢰찾기게임을 만들 때 였다. 아직 경험이 미흡하기에 저기 써져있는 말이 와닿지는 않았다. 하지만 한가지 확실한 것은 재귀를 사용하면 코드의 가독성 측면에서 좋아진다는 것을 확실한 것 같다. 앞으로 무엇인가 만들때 한 번쯤 재귀를 사용할 수 있을까에 대한 의문을 가져보자. 그 의문이 재귀를 좀 더 깊이있게 이해할 수 있는 새싹이 될 것이다.

Ref