반응형
피보나치 수
- 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
※ 편의상 0번째 항을 0으로 두기도 함.
예시)

1) 반복문을 통한 팩토리얼의 구현
# 반복문을 통한 피보나치 수 구현
# 입력부
n = int(input())
# 0번째, 1번째 피보나치 수를 포함하는 배열 생성
answer_arr = [0, 1]
# 반복문을 통해 n을 입력받았을 때, 기존 배열에 n번째 피보나치 수까지 추가
for i in range(n-1):
answer_arr.append(answer_arr[1+i] + answer_arr[i])
# 입력받은 n번째 피보나치 수 출력
print(answer_arr[n])

반응형
2) 재귀함수를 통한 팩토리얼의 구현
# 재귀함수를 통한 피보나치 수 구현
def Fibonacci(n):
# 0번째 피보나치 수는 0임을 밝힘과 동시에 재귀함수 탈출의 기능
if n == 0:
return 0
# 1번째 피보나치 수는 1임을 밝힘과 동시에 재귀함수 탈출의 기능
elif n == 1:
return 1
else:
value = Fibonacci(n-1) + Fibonacci(n-2)
return value
# 입력부
n = int(input())
# 입력받은 n번째 피보나치 수 출력
answer = Fibonacci(n)
print('{0}번째 피보나치 수는 {1} 입니다.'.format(n, answer))


피보나치 수 구현의 경우, 반복문을 사용함으로써 구현 가능하지만,
재귀함수로 피보나치 수를 구현해봄으로써, 재귀함수의 작동에 대해서 공부할 수 있습니다.
재귀함수의 경우에 자연과학 연구, 특정 문제의 모든 경우의 수를 효율적으로 확인하는 백트래킹 메서드(back tracking method), 코딩 테스트 등, 다방면에서 사용되니 작동방법을 명확히 아는 것이 중요하겠습니다.
반응형
'Algorithm' 카테고리의 다른 글
[파이썬] 재귀함수를 통한 팩토리얼의 구현 (17) | 2022.08.24 |
---|---|
[파이썬] 소수 판별/소수로 구성된 배열 생성 알고리즘 (24) | 2022.08.14 |
[파이썬] 백준 9020번 '골드바흐의 추측' 알고리즘 -2 (0) | 2022.08.06 |
[파이썬] 백준 9020번 '골드바흐의 추측' 알고리즘 -1 (0) | 2022.08.04 |
[파이썬] 백준 1024번 '수열의 합' 알고리즘 (0) | 2022.08.01 |
댓글