URL : https://programmers.co.kr/learn/courses/30/lessons/12945
문제 설명
- 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
1 2 3 4
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은 1이상, 100000이하인 자연수입니다.
문제풀이
- 처음 생각한대로 재귀 함수를 사용하려 했으나, 이는 메모리 관리측면에서 효율적이지 않음 (1번 런타임에러)
- list에 fibo로 계산된 수를 넣고 n번째전과 그 이전 (b과 a)를 더하는 방식으로 만듬 (2번 list로 만든 솔루션)
- 하지만 for문으로 a, b를 생성하여 계속 a, b = b, b +a 로 피보나치 수를 업데이트하여 list를 만들지 않음. (3번 다른사람의 풀이)
(1) 재귀함수를 사용함. 런타임 에러
1
2
3
4
5
def solution(n):
if n <= 1:
return n
else:
return (solution(n-1) + solution(n-2)) % 1234567
1
2
n = 5
solution(n)
1
5
- 재귀 함수를 사용한 피보나치 수, 런타임 에러가 뜸
- 재귀 함수를 쓰지 말라는 뜻인듯
(2) list를 활용
1
2
3
4
5
def solution(n):
fibo = [0, 1]
for i in range(2, n+1):
fibo.append(fibo[i-1] + fibo[i-2])
return fibo[n] % 1234567
1
2
n = 5
solution(n)
1
5
- 재귀를 하지않고 fibo의 값을 리스트에 저장하는 방법으로 풀면 런타임 에러가 나지않고 해결
(3) a, b값을 update 하며 해결(다른 사람의 풀이)
1
2
3
4
5
6
7
8
def solution(n):
a, b = 0, 1
for i in range(n):
# 앞의 2개의 숫자의 합이 뒷 숫자의 값이 됨, n번 만큼 for문으로 반복
a, b = b, a+b
# 123456로 나눈 나머지를 정답으로 리턴
answer = a % 1234567
return answer
1
2
n = 5
solution(n)
1
5
- 다른사람의 풀이로 a, b = b, a + b가 핵심
- a = b,
- b = a + b로 두줄을 하게 되면 윗줄부터 실행되어 a가 b로 바뀌어 다른 값이 나오게 됨.
- a, b = b, a + b는 한번에 실행되므로, a가 변경되지 않음