[DP] BJ_24416, 알고리즘 수업

<문제의 접근>

 의사코드를 보고 코드로 풀어낼 수 있으냐를 체크하는 문제. 사실 피보나치 수열의 경우는 Dynamic Programming을 설명하는데 있어서 고전이라고 부를 수 있을 정도로 많이 인용되는 문제다. 한번이라도 들어 보았다면 위의 의사코드를 작성하는 부분은 크게 어렵지 않다고 생각한다.

<문제의 구성>

 의사코드를 구현한다. 다만, 한가지 주의해야 할 부분은 함수 호출 부분을 코드의 어디에 위치 시키느냐 인데, 동적 프로그래밍의 경우는 for 문 안에 넣어주면 되고, recursive하게 구하는 경우는 n==1 or n==2의 경우에 리턴되는 경우를 세어주면 된다. 

 

def recur(n):
    global cnt1
    if (n ==1) or (n==2):
        cnt1 += 1
        return 1
    else:
        return recur(n-1) + recur(n-2)

def recur_dp(n):
    global cnt2
    f = [1]*(n+1)
    for i in range(3, n+1):
        cnt2 += 1
        f[i] = f[i-1] + f[i-2]
    return f[n]

 

 재귀 호출 부분으로 인해서 실행시간이 생각보다 길다. 

 

<Python> 

https://github.com/Koo82/Algotirhm/blob/main/%5BDP%5DBJ_24416.py

GitHub - Koo82/Algotirhm