Dynamic Programming이란?

다이나믹 프로그래밍이랑 

동적으로 프로그램을 수행 시키는 것으로 써 

현재 수행한 프로그래밍의 결과를 저장하고 

후에 수행될 프로그래밍의 결과를 저장 하는것 같습니다. 

 

장점으로는 

이전에 계산했던 결과를 가지고 수행하기에 더 빠른 처리가 가능 할것 같습니다. 

단점으로는 

결과를 저장하기 위한 메모리가 필요합니다. 

N = int(input())
D = [0, 1]

for i in range(2, N + 1):
    D.append(D[i-2] + D[i-1])

print(D[N])

 

**동적 프로그래밍(Dynamic Programming)**은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법입니다1. 이 방법은 주어진 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것입니다2. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있습니다2.

동적 프로그래밍의 장점은 다음과 같습니다3:

• 최적의 결과: 필요한 모든 가능성을 고려하여 구현하므로 항상 최적의 결과를 얻을 수 있습니다3.
• 빠른 속도: 메모리에 저장된 값을 사용하므로 빠른 속도로 최적의 해를 찾아낼 수 있습니다3.

그러나 동적 프로그래밍에는 단점도 있습니다. 모든 가능성을 고려하지 못하면 최적의 결과를 보장할 수 없으며, 다른 알고리즘에 비해 많은 메모리 공간을 요구합니다3. 이러한 이유로, 동적 프로그래밍은 문제의 특성과 요구 사항에 따라 적절하게 사용해야 합니다.

피보나치 수열은 다음과 같이 정의됩니다1:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n >= 2)

이를 재귀적 방법과 동적 프로그래밍(DP) 방법으로 구현할 수 있습니다.

1. 재귀적 방법: 재귀적 방법은 피보나치 수열을 직관적이고 간단하게 구현할 수 있지만, 많은 중복 계산이 발생하므로 비효율적입니다1. 예를 들어, F(n)을 계산하기 위해 F(n-1)과 F(n-2)를 계산하고, F(n-1)을 계산하기 위해 다시 F(n-2)와 F(n-3)을 계산하는 등 같은 계산이 반복됩니다1.

Python

 

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

AI가 생성한 코드입니다. 신중하게 검토하고 사용하세요. FAQ의 자세한 정보.

1. 동적 프로그래밍(DP): 동적 프로그래밍은 이러한 중복 계산 문제를 해결하기 위한 방법입니다2. DP는 이미 계산한 값을 저장해두고, 필요할 때마다 불러와 사용함으로써 중복 계산을 방지합니다2. 이렇게 하면, 각 숫자는 한 번씩만 계산되므로 효율적입니다2.

Python

 

def fibonacci_dp(n):
    fib = [0, 1] + [0]*(n-1)
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

AI가 생성한 코드입니다. 신중하게 검토하고 사용하세요. FAQ의 자세한 정보.

따라서, 피보나치 수열과 같이 중복 계산이 많이 발생하는 문제에서는 동적 프로그래밍 방법이 효율적입니다2.