백준 2748번 문제(피보나치 수 2) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

2748번: 피보나치 수 2

 

정답 코드는 아래와 같습니다.

def solve():
  n = int(input())
  arr = [0, 1]
  for i in range(2, n+1):
    value = arr[i-1] + arr[i-2]
    arr.append(value)
  print(arr[n])
 
solve()
 

 

보통 프로그래밍 언어를 학습하면서 함수를 배우고, 재귀(recursive) 함수를 배울 때 가장 자주 사용되는 예시가 바로 피보나치 수열입니다.

그리고 학년이 조금 오르고 알고리즘에 대해서 공부하다보면 dynamic programming(DP) 을 배울 때 가장 자주 사용되는 예시가 또 피보나치 수열입니다.

두 가지 모두 매우 중요하기 때문에 각각 정확히 이해하시기 바랍니다. 간단하게만 설명하고 넘어가자면,

 

728x90

 

<재귀 함수>

어떤 함수가 스스로를 호출하도록 되어 있으면 재귀 함수라고 합니다.

스스로 계속 호출을 하게 되면 종료되지 않을 수 있기 때문에 종료 조건이 반드시 들어가야 합니다.

대부분의 경우(또는 언제나) 재귀 함수로 만들어진 로직은 반복문을 이용해서 구현할 수 있고,

성능(공간, 시간)도 반복문을 이용한 경우가 대체적으로 더 우수하지만,

재귀 함수로 구현하면 상대적으로 코드 가독성이 더 좋기 때문에 특별히 성능에 민감하지 않다면 재귀함수로 구현하는 것도 나쁘지 않습니다.

 

<DP, Dynamic Programming, 동적 계획법>

DP는 이전에 계산한 결과를 저장하여, 다시 계산이 필요한 경우에 기존에 계산된 값을 이용하여 다시 계산하지 않음으로써 실행 시간을 줄이는 기법을 말합니다.

크게 bottom up 방식과 top down 방식으로 나눌 수 있는데요.

Top down 방식은 보통 재귀 함수를 이용하는 경우에 사용하고,

Bottom up 방식은 보통 반복문을 이용하는 경우에 사용합니다.

Python에서는 재귀호출 가능 횟수가 다른 언어에 비하여 제한적이므로 저는 보통 bottom up 방식을 이용하여 문제를 풉니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=wUbMj3cNv4k 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)