다이나믹 프로그래밍 문제 풀이

1. 피보나치 함수( 백준 1003번 )

1003번: 피보나치 함수

 

참고 코드)

 

n=int(input())

def fibo(x):
    if(x==0):
        return 0
    if x==1 or x==2:
        return 1
 
    if d[x] != 0:
    	return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

for i in range(n):
    d=[0]*42
    a=int(input())
    if(a==0):
        print(1,end=' ')
    else:
        print(fibo(a-1), end=' ')
    print(fibo(a))

 

➡️ 처음에는 재귀를 이용하서 피보나치 수열을 구현하였다. 시간 초과가 나서 동적 프로그래밍을 이용해야하는 문제임을 알고 방향을 바꾸었다!
핵심 아이디어) 피보나치 수열의 값과 0, 1의 출력횟수와의 상관관계 파악해야한다.
a가 입력값일 때 0의 출력 횟수는 fibo(a-1), 1의 출력 횟수는 fibo(a) 값과 동일하다.  * 이렇게 수를 출력하는 문제의 경우 상관관계를 이용해야할 수도 있다는 점 기억하자.

 

 

2. 알고리즘 수업 - 피보나치 수 1 (백준 24416번 )

24416번: 알고리즘 수업 - 피보나치 수 1

- 직접 작성한 코드

def fib(n) :
    
    if n == 1 or n == 2:
     
        return 1  # 코드1
    else :
        return fib(n - 1) + fib(n - 2)


def fibonacci(n) :
    f=[0]*(n+1)
    count=0
    
    f[1] = f[2] = 1
    
    for i in range(3,n+1):
        
        count+=1
        f[i] = f[i-1] + f[i-2]
    return count



n=int(input())



print(fib(n),fibonacci(n))

* 시간 초과 오류가 나올 땐 pypy3 사용해보자

 

3. 신나는 함수 실행 (백준 9184번)

9184번: 신나는 함수 실행

 

- 참고 코드 

 

import sys
input = sys.stdin.readline

def w(a, b, c):
    if a <= 0 or b<= 0 or c<=0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    
    # 이 코드가 정말 중요! 
    if dp[a][b][c]:
        return dp[a][b][c]
    if a<b<c:
        dp[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a, b-1, c)
        return dp[a][b][c]
    dp[a][b][c] = w(a-1, b, c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)
    return dp[a][b][c]

dp = [[[0]*(21) for _ in range(21)] for _ in range(21)]


while 1:
    a, b, c = map(int, input().split())
    if a==-1 and b==-1 and c==-1:
        break
    print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

* if dp[a][b][c]: 
           return dp[a][b][c]
 ➡️ 이 코드로 dp가 이미 계산을 한 경우, 아닌 경우를 구별을 할 수 있다.

* 문자열 포맷

1. 문자열 맨 앞에(따옴표앞) f
2. 사용하고 싶은 변수, 값을 중괄호 안에 넣는다.