피보나치 수열은 프로그래밍을 배울 때 가장 먼저 접하는 고전적인 문제 중 하나입니다. 이 글에서는 숫자 n이 주어졌을 때 n번째 피보나치 항을 구하는 방법을 단계별로 알아보겠습니다.
피보나치 수열이란?
피보나치 수열은 각 항이 바로 앞의 두 항의 합으로 정의되는 수열입니다. 즉, i번째 피보나치 항은 다음과 같은 점화식으로 표현됩니다.
f(i) = f(i-1) + f(i-2)
수열의 첫 두 항은 각각 0과 1로 시작합니다. 따라서 전체 수열은 다음과 같습니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
문제 예시
예를 들어 입력값이 15라면, 15번째 피보나치 항인 610이 출력되어야 합니다.
해결 방법: 반복문 활용
가장 효율적이고 직관적인 방법은 반복문을 사용하는 것입니다. 알고리즘의 동작 과정은 다음과 같습니다.
- 첫 번째 항(first)을 0으로, 두 번째 항(second)을 1로 초기화합니다.
- 2부터 n까지 반복하면서 다음 작업을 수행합니다.
- temp에 first와 second의 합을 저장합니다.
- first에 second 값을 대입합니다.
- second에 temp 값을 대입합니다.
- 반복이 끝나면 second 값을 반환합니다.
이 방식은 시간 복잡도가 O(n)으로, 재귀 호출 방식(지수 시간 복잡도)보다 훨씬 빠르고 메모리도 일정하게 유지됩니다.
파이썬 코드 구현
class Solution:
def solve(self, n):
first = 0
second = 1
for _ in range(2, n + 1):
temp = first + second
first = second
second = temp
return second
ob = Solution()
print(ob.solve(15))실행 결과
입력:
15
출력:
610
코드 설명
코드의 핵심 로직을 살펴보면 다음과 같습니다.
- first와 second 변수: 현재 계산에 필요한 두 개의 연속된 피보나치 항을 저장합니다.
- range(2, n+1): 첫 두 항은 이미 초기화되어 있으므로, 세 번째 항(n=2)부터 n번째 항까지 총 n-1번 반복합니다.
- temp 변수: 새로운 피보나치 항을 임시로 저장하여, first와 second를 한 칸씩 앞으로 이동시키는 역할을 합니다.
마무리
이처럼 반복문과 두 개의 변수만 있으면 추가적인 배열 없이도 n번째 피보나치 수를 O(n) 시간 안에 효율적으로 구할 수 있습니다. 공간 복잡도는 O(1)로 매우 경제적이며, 큰 n 값에서도 안정적으로 동작합니다. 코딩 테스트나 면접에서 자주 등장하는 기본 문제이므로, 원리를 확실히 이해하고 넘어가시기 바랍니다.