프로그래머스 12945번 문제인 "피보나치 수" Lv.2을 파이썬으로 풀어보도록 하겠습니다.
[프로그래머스] 피보나치 수 Lv.2 - [파이썬/python]
💻 문제 설명
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 반환(return)하는 함수, solution을 완성해 주세요.
🚨 제한사항
- n은 2 이상 100,000 이하인 자연수입니다.
!!!정답 주의!!!
🌟 소스 코드
def solution(n):
pre = 0 # 이전 피보나치 수를 저장하는 변수
current = 1 # 현재 피보나치 수를 저장하는 변수
# 2부터 n까지 순회
for i in range(2, n+1):
# 현재 피보나치 수는 이전 두 피보나치 수의 합
# 이전 피보나치 수는 갱신하기 전의 현재 피보나치 수
current, pre = current + pre, current
# n번째 피보나치 수를 1234567로 나눈 나머지를 반환
return current % 1234567
⏱ 시간복잡도
위 코드의 시간 복잡도는 O(n)입니다.
피보나치 수 계산하기: for i in range(2, n+1)
코드는 2부터 n까지의 범위를 순회하며 각 단계에서 피보나치 수를 계산합니다. 이 과정은 O(n)의 시간이 소요됩니다.
변수 갱신하기: current, pre = current + pre, current
각 단계에서 이전 피보나치 수와 현재 피보나치 수를 갱신하는 데는 상수 시간, 즉 O(1)의 시간이 소요됩니다.
따라서, 이 코드는 입력된 자연수를 한 번만 순회하고, 각 숫자에 대해 상수 시간의 연산을 수행하므로, 전체 시간 복잡도는 O(n)입니다. 이는 입력 크기에 선형적으로 비례하는 시간 복잡도를 의미합니다.
🏳🌈 테스트 결과
728x90
'코딩테스트' 카테고리의 다른 글
| [프로그래머스] 괄호 회전하기 - Lv.2 (49) | 2023.10.30 |
|---|---|
| [프로그래머스] 영어 끝말잇기 - Lv.2 (53) | 2023.10.29 |
| [프로그래머스] 짝지어 제거하기 - Lv.2 (55) | 2023.10.27 |
| [프로그래머스] 이진 변환 반복하기 - Lv.2 (53) | 2023.10.26 |
| [프로그래머스] 주사위 게임 3 - Lv.0 (52) | 2023.10.25 |