Posts 피보나치 수 [Python]
Post
Cancel

피보나치 수 [Python]

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가 변경되지 않음
This post is licensed under CC BY 4.0 by the author.

H-Index [Python]

신규 아이디 추천 [Python]

Comments powered by Disqus.