sm 기술 블로그
125. 24416(알고리즘 수업 - 피보나치 수 1) 본문
본 코드는 pypy3로 제출해야합니다.
n = int(input())
cntFib = 0
cntFib2 = 0
memo = [0 for i in range(100)]
def fib(n):
global cntFib
if n == 1 or n == 2:
cntFib += 1
return 1
else:
return fib(n-1)+fib(n-2)
def fibonacci(n):
global cntFib2
if memo[n] > 0:
cntFib2 += 1
return memo[n]
if n <= 1:
memo[n] = n
return memo[n]
else:
memo[n] = fibonacci(n-1) + fibonacci(n-2)
return memo[n]
fib(n)
fibonacci(n)
print(cntFib, cntFib2)
문제요약
재귀함수와 동적프로그래밍을 이용하여 호출횟수를 출력하라.
설명
동적프로그래밍의 개념은 아래를 참고하자.
https://smhope.tistory.com/328?category=1056187
주의점
Down - Top 방식을 사용하면 Top - Down 보다 cnt를 한번 더 증가 시킴.
n = int(input())
cntFib = 0
cntFib2 = -1
def fib(n):
global cntFib
if n == 1 or n == 2:
cntFib += 1
return 1
else:
return fib(n-1)+fib(n-2)
def fibonacci(n):
global cntFib2
if n <= 1:
return n
first = 0
second = 1
for _ in range(0, n-1):
tmp = first + second
first = second
second = tmp
cntFib2 += 1
return tmp
fib(n)
fibonacci(n)
print(cntFib, cntFib2)
'문제 > 백준_파이썬' 카테고리의 다른 글
127. 1904 (01타일) (0) | 2022.07.03 |
---|---|
126. 9184 (신나는 함수 실행) (0) | 2022.07.02 |
124. 14889(스타트와 링크) (0) | 2022.07.01 |
123. 14888(연산자 끼워놓기) (0) | 2022.07.01 |
122. 2580(스도쿠) (0) | 2022.06.30 |
Comments