<aside> 🔥 리트코드 509번 문제

</aside>

<aside> 🔥 문제 정리

입력값 n을 토대로 피보나치 수열을 출력해라.

</aside>

<aside> 🔥 접근 방법

피보나치 수는 다이나믹 프로그래밍의 전형적인 예시로, 꼭 알아두면 좋다고 한다.

굉장히 많은 방법으로 풀 수 있다고 하니 하나씩 알아보았다.

추가적으로 오늘 시험 2번 문제가 피보나치 수 문제였다고 한다.. 전혀 몰랐다. 그냥 규칙을 찾아서

풀었는데 자세한 모르고 푼 방법도 어쨋든 성공적으로 제출 되었다. 시험 2번 링크

다이나믹 프로그래밍으로 생각하면 tabulation 방법에 가까운것 같다.

점화식

n번째 피보나치 = n - 1 값 + n - 2 값

</aside>

<aside> 🔥 재귀 구조 브루트 포스

내생각엔 브루트 포스가 제일 간단해보인다.

하지만 메모이제이션이 되질 않아 값이 커지면 계산이 끝나질 않는다.

def brute(self, n):
        if n <= 1:
            return n
        return self.brute(n - 1) + self.brute(n - 2)

</aside>

<aside> 🔥 하향식 Memoization

위에서부터 아래로 값을 찾아내는 방식이다.

def memoization(self, n):
    dp = collections.defaultdict(int)

    def memo_wrapper(n):
        if n <= 1:
            return n

        if dp[n]:
            return dp[n]

        dp[n] = memo_wrapper(n - 1) + memo_wrapper(n - 2)
        return dp[n]

    return memo_wrapper(n)

</aside>

<aside> 🔥 상향식 Tabulation

아래에서부터 값을 계산해 위에있는 값을 찾아내는 방식이다.

def tabulation(self, n):
    dp = collections.defaultdict(int)

    def tab_wrapper(n):
        dp[0] = 0
        dp[1] = 1

        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

    return tab_wrapper(n)

</aside>

<aside> 🔥 변수를 두개만 사용해 공간을 아끼는 방법

이 방법도 상향식이랑 비슷한거같은데 메모를 쓰지 않고 변수 두개만 사용해서 공간을 최적화했다.

def two_varient(self, n):
        x, y = 0, 1
        for i in range(0, n):
            x, y = y, x + y
        return x

</aside>