1. Learn
    2. /
  2. Courses
    3. /
  3. Python으로 배우는 자료구조와 알고리즘
Connected

Exercise

피보나치 수열

이번 연습 문제에서는 자연에서 흔히 볼 수 있는 피보나치 수열을 구현해 보겠습니다. 수열은 "0, 1, 1, 2, 3, 5, 8…"처럼 진행돼요. 이 수열을 생성하는 알고리즘을 재귀로 구현할 것입니다.

처음 두 수는 0과 1이며, 그다음 수들은 바로 앞의 두 수를 더한 값입니다.

이 수열은 재귀적으로 다음과 같이 정의할 수 있습니다: \(fib(n)=fib(n-1)+fib(n-2)\), 단 \(fib(0)=0\), $fib(1)=1$이고, 여기서 $n$은 수열의 $n$번째 위치를 뜻합니다.

첫 단계에서는 재귀를 사용해 피보나치를 코딩합니다. 두 번째 단계에서는 동적 계획법을 사용해 개선하고, 하위 문제의 해를 cache 변수에 저장하세요.

Instructions 1/2

undefined XP
  • 1
    • 기본 사례를 정의하세요.
    • fibonacci() 함수를 재귀적으로 호출하세요.
  • 2
    • cache에 값이 있는지 확인하세요.
    • 나중에 다시 계산하지 않도록 결과를 cache에 저장하세요.