🔎 문제설명
피보나치 수는 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으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
✅ 제한사항
- n은 2 이상 100,000 이하인 자연수입니다.
💡 풀이 아이디어
** 우선 피보나치 수열은 DP를 사용하는 대표적인 문제이므로 Bottom-up DP를 사용하여 문제를 해결했다.
1) 제한사항에서n은 2이상 100,000이하인 자연수이다.라고 했기 때문에, DP 테이블의 칸 수를 넉넉하게 100,001로 잡는다.
2) 문제설명에 나온F(0) = 0, F(1) = 1를 미리 지정한다.
3) 보텀업 dp(반복문 사용)를 사용해서 피보나치 함수를 작성한다.
4) 1234567로 나눈 값을 리턴한다.
## 내 풀이
def solution(n):
d = [0] * 100001 # dp table : 앞서 계산된 결과를 저장
d[0] = 0
d[1] = 1
# bottom-up dp
for i in range(2, n+1):
d[i] = d[i-1] + d[i-2]
return d[n] % 1234567
print(solution(3))2
직관적이고 간단하게 해결한 풀이를 발견했다. (내가 알아보기 편하도록 변수명만 바꾸었다.)
## 다른 사람 풀이
def solution(n):
f0, f1 = 0, 1
for i in range(n):
f0, f1 = f1, (f0+f1) % 1234567
return f0
print(solution(3))2
처음에는 f1 = (f0+f1) % 1234567의 연산에서 f0은 f0 = f1로 할당되기 전의 값인지, 할당된 이후의 값 인지 헷갈렸다. 하지만 파이썬에서는 2개 이상의 복수 변수를 동시에 상호 할당할 수 있다는 특징을 알고있다면 f0 f0 = f1로 할당되기 전의 값이라는 것을 쉽게 파악할 수 있다.
좀 더 이해하기 쉽도록 아래 그림에서 살펴보자.
위의 풀이법의 최대 장점은 메모리를 훨씬 적게 사용할 수 있다는 것이다.
