본문 바로가기

알고리즘

피보나치 수열

Basic 100 · 92번Lv. 1재귀

피보나치 수열

문제 설명

피보나치 수열은 다음과 같이 정의됩니다.

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) (n ≥ 2)

즉, 피보나치 수열의 첫 두 항은 0과 1이며, 그 이후의 항은 바로 앞 두 항의 합으로 정의됩니다. 예를 들어, 피보나치 수열의 처음 10개 항은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34입니다.

0 이상의 정수 n이 주어졌을 때, n번째 피보나치 수를 반환하는 함수를 작성해주세요. 재귀 방식으로 구현해 보세요.


제한 사항

  • n은 0 이상 30 이하의 정수입니다.
  • 연습 안내: 재귀 함수로 풀어 보세요. 채점은 반환한 결과만 확인합니다.

입출력 예

입력반환값
00
11
21
713
1055
15610

입출력 설명

  • F(0)은 0입니다.
  • F(1)은 1입니다.
  • F(2)는 F(1) + F(0) = 1 + 0 = 1입니다.
  • F(7)은 F(6) + F(5) = 8 + 5 = 13입니다.
  • F(10)은 F(9) + F(8) = 34 + 21 = 55입니다.
  • F(15)는 F(14) + F(13) = 377 + 233 = 610입니다.

예시 테스트

#입력기대값
100
211
321

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.