모든 챌린지
쉬움 3명 해결 정답률 100.0%

피보나치 수

n번째 피보나치 수를 반환하세요.

배우게 될 내용

  • 이전 항으로 수열 생성하기
  • 두 변수를 동시에 갱신하기
  • 단순 재귀가 느린 이유 알기

문제

원문 보기 (영어)

피보나치 수열은 0, 1로 시작하며, 이후의 각 수는 이전 두 수의 합입니다: 0, 1, 1, 2, 3, 5, 8, …. F(0) = 0이고 F(1) = 1입니다.

fibonacci(n)을 구현하세요.

입력

n: 수열에서의 위치입니다.

출력

F(n)을 반환하세요.

제약 조건

0 ≤ n ≤ 90

예시

예시 1
입력:
n = 10

예상 출력:
expected = 55
입력:
long long n = 10;

예상 출력:
long long expected = 55;
입력:
long n = 10;

예상 출력:
long expected = 55;

설명

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55입니다.

예시 2
입력:
n = 0

예상 출력:
expected = 0
입력:
long long n = 0;

예상 출력:
long long expected = 0;
입력:
long n = 0;

예상 출력:
long expected = 0;

설명

정의에 따라 F(0) = 0입니다.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

처음 두 값은 정해져 있으니 base case부터 시작하세요.

힌트 2

재귀로 다시 계산하지 말고, 이전 두 값으로 다음 값을 만드세요.

힌트 3

반복문으로 구현해 중복 계산과 깊은 재귀를 피하세요.

예상 복잡도

시간 O(n), 추가 공간 O(1)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 HJhettory Jurash Python 774 ms - 4/5 코드 보기
2 KKKaneki Ken Python 858 ms - 5/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 2개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.