백준 10870 [파이썬] 피보나치 수5

 

[Python] 백준 알고리즘 온라인 저지 10870번 피보나치 수 5

 

Python3 코드

1) 재귀 함수 코드

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

n = int(input())
print(fibonacci(n))

 

2) for문 코드

n = int(input())

fibonacci = [0, 1]
for i in range(2, n+1):
    num = fibonacci[i-1] + fibonacci[i-2]
    fibonacci.append(num)
print(fibonacci[n])

 

 

Python3 코드 풀이

 

1. 문제를 풀었던 내용을 전체적으로 정리

이번 문제는 임의의 수가 주어지면 피보나치 값을 출력하는 문제이다. 백준 온라인 저지 단계별 문제풀이에서 재귀 함수 부분에 포함된 문제이기 때문에 재귀 함수로 문제를 풀었고 같은 식을 반복하는 코드를 이용해서 for문으로도 작성해보았다. 피보나치수열과 재귀 함수에 대해 정의한 내용은 아래와 같다.

 

1-1. 피보나치수열

처음 두 수를 0과 1로 하고 그다음부턴 자기 앞에 두 수를 더한 수의 나열이다. 문제를 풀 때는 피보나치수열의 특성을 그대로 코드로 작성했다. 0과 1은 그대로 출력하고 이후부턴 앞의 두 수를 더한 수가 출력되도록 함수를 작성하였다.

 

1-2. 재귀 함수

자기 자신을 호출하는 함수이다. 이번 문제는 0과 1을 제외하고 이후의 수를 생성 할 때 재귀 함수를 이용하여 코드를 작성하였다.

 

2. 재귀 함수를 이용한 코드를 풀이해본다.

2-1. 코드 상단 쪽, 먼저 함수를 생성한다.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

함수 생성을 위해선 def 예약어를 이용한다. 피보나치수열을 구하는 문제이므로 함수 이름은fibonacci로 지어보았고 임의의 수 n이 주어졌을 때 n번째 피보나치수를 구하는 함수를 생성하기 위해 fibonacci(n)으로 입력받는 값은 n 한 개만 지정하였다. 

 

if조건식을 이용해서 입력받는 수 n이 1보다 작은 경우, 즉 0과 1인 경우는 그대로 n을 return 하고 0과 1이 아닌 경우에는 앞의 두 수를 더한 값을 return 하도록 하였다. 이때, 앞의 두 수를 불러낼 때 함수 자기 자신을 불러오는 재귀 함수를 이용해서 코들를 작성하였다. 앞의 두 수는 각각 (n-1)과 (n-2)로 나타낼 수 있다.

 

2-2. 코드 하단, 위쪽에서 생성한 함수를 활용한다.

n = int(input())
print(fibonacci(n))

임의의 수 n을 input 함수로 입력받는다. 입력받는 값은 문자열이므로 숫자로 사용하기 위해 int 타입으로 변환한다. 이후에 위에서 생성한 finobacci 함수를 활용해서 입력받은 수로 return 받는 피보나치수를 출력하도록 한다. 

 

3 for문으로 작성한 코드를 풀이해본다.

fibonacci = [0, 1]
for i in range(2, n+1):
    num = fibonacci[i-1] + fibonacci[i-2]
    fibonacci.append(num)

피보나치수열의 특성을 그대로 코드로 작성하였다. 우선 fibonacci라는 숫자 리스트로 이루어진 변수를 선언한다. 먼저 리스트에는 0과 1을 요소로 지정한다. range함수를 이용해서 2부터 입력받는 수 n까지의 숫자 범위를 생성한다. 이 숫자는 fibonacci 리스트의 인덱스로 사용된다. 

 

이후 for문에서 range 함수로 생성된 숫자 변수 i를 이용해서 fibonacci 리스트의 마지막 두 수의 위치를 구한다. fibonacci [i-1]과 fibonacci [i-2]는 각각 리스트의 끝에 위치한 두 개의 수를 반환한다. 이렇게 반환된 두 수는 합해서 append 함수로 fibonacci 리스트에 추가한다.