[BOJ 10826][백준 10826번] 피보나치 수 4 (파이썬 풀이)

https://www.acmicpc.net/problem/10826

10826번: 피보나치 수 4

 

🤔 문제 설명 및 입출력

---

 

 

 

 

 

✍ 접근 방법

---

 

피보나치 수열을 구하는 방법은 여러가지가 있는데, 그 중 가장 대표적인 방법이 재귀 함수로 구현하는 방법과 메모이제이션을 활용한 풀이이다. 나는 DP를 이용해서 풀어봤다. 점화식에 따라, n번째 피보나치 수를 구하기 위해 n-1번째 수와 n-2를 더하는데, n-1번째 수와 n-2를 매번 계산하는 것이 아니라, 저장된 어딘가 (이번 풀이에서는 memo)에서 가져오기로 하였다.

 

피보나치 수열의 점화식

 

n이 10,000 이하로 제한 되므로, 사실 어떤 방식으로 풀어도 관계없긴 한데, 그래도 피보나치 수열 문제에서 재귀로 푸는건 조금 스마트 하지 않다고 생각된다.

 

👨‍💻 소스 코드

---

• 파이썬

N = int(input())
# N의 값에 따라 memo 리스트의 크기 조절, N이 0이라도 리스트가 생성되게 구성하였다.
memo = [0] + [0]* (N)
if N > 0:
    memo[1] = 1
    # for문을 이행하면서 memo[n]의 값이 0에서 n번째 피보나치 수로 바뀌어간다. 
    for n in range(2,N+1):
        memo[n] = memo[n-1] + memo[n-2]

# 구하고 싶은 값은  N번째 피보나치 숫자이다.
#  memo 리스트의 마지막 값이 N번째 피보나치 숫자이므로, 이에 맞게 출력
print(memo[-1])

 

 

• 파이썬 (다른 풀이)

n=int(input())
if n<2:
    print(n)
else:
    x,y=0,1
    for i in range(2,n+1):
        x,y=y,x+y
    print(y)

코드 출처 : https://cantcoding.tistory.com/28 

 

구글링하다가 우연히 발견한 코드를 첨부한다.

 

굉장히 깔끔하다. (특히 x,y = y, x+y 부분이 정말 파이썬답다고 생각한다.)

 

 

점화식을 그대로 옮긴 것은 똑같은데, 리스트를 만들지 않고 y라는 값을 계속 갱신함으로서 n번째 피보나치 수만 저장하여 출력하여 쓸데없이 메모리 공간을 낭비하지 않는다.

 

리스트를 생성하지 않음으로 생기는 또 다른 장점은 입력으로 0이 들어왔을때 값을 출력하기 위해

memo = [0] + [0]* (N)

이런 처절한 몸부림을 치지 않아도 된다.

 

코드의 효율성에 대해서 조금만 더 생각하고, 여러가지 방향으로 접근해봤으면 나도 이런 코드를 만들 수 있었을꺼라는 생각이 들어 묘하게 마음 한 켠이 아프다 😂😂😂 

 

🔥 강평

---

피보나치 수열을 구현하는 방법은 너무나도 다양해서, 고수들은 새로운 언어를 배울 때 피보나치 수열을 구현해보는것 부터 시작한다고 한다. 아쉽게도 나는 그런 의도로 이 문제를 푼 건 아니고 , 다음에 풀 "피보나치 수 6" 을 위한 빌드업으로 한번 가볍게 풀어봤다. 

 

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

 

 

...벌써부터 걱정이 앞서는건 왜일까?