동적 프로그래밍(Dynamic Programming)이란?

동적 프로그래밍(Dynamic Programming)

주어진 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 해결하는 알고리즘

특징

• 메모리 공간을 약간 더 사용하여 연삭 속도를 비약적으로 증가
• 하위문제들의 수가 기하급수적으로 늘어날 경우 유리한 알고리즘

문제조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
3.  메모라이제이션(Memorization)을 사용하여 작은 문제에서 구한 정답을 저장

 

 

동적 프로그래밍 vs 분할 정복

공통점

• 문제를 잘게 쪼게어 작은 단위로 분할

차이점

• 동적 프로그래밍
  • SubProblem는 중복되어 상위 문제 해결시 사용
  • Memorization 사용
  • 상향식 접근(bottom up)
• 분할 정복
  • SubProblem은 중복되지 않음
  • 하향식 접근(top down)

 

ex) 피보나치수열

 

1. 분할 정복(Divide & conquer)

분할 정복을 이용한 풀이

<출처 : https://stevenschmatz.github.io/blog/2017/12/06/introduction-to-dynamic-programming/>

분할 정복에서 이용한 풀이에서 불필요한 중복된 연산을 계속 수행하여 실행시간이 오래 걸리는 것을 알 수 있다.

 

 

코드

# 분할 정복
def fibo(n):
    if n <= 1:
        return n
    return fibo(n-1) + fibo(n-2)

 

 

 

2. 동적 프로그래밍(Dynamic Programming)

dp를 활용한 피보나치 풀이

<출처 : https://stevenschmatz.github.io/blog/2017/12/06/introduction-to-dynamic-programming/>

메모라이제이션을 이용하여 불필요한 중복된 연산을 수행하지 않는 것을 확인할 수 있다.

 

 

코드

# 동적 프로그래밍(dp)
def fibo(n):
    dp = [0 for _ in range(n+1)]
    dp[0] = 0
    dp[1] = 1
    for i in range(2,n+1):
    	dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

​

 

 

Reference

• https://yusang.tistory.com/120
• https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

​

관련문제 풀이 포스팅

[백준] 12865번 평범한 배낭(python 파이썬)

 

[백준]11049번 행렬 곱셈 순서(python 파이썬)

출처

 

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

잘못된 내용이 있으면 피드백 부탁드립니다!

궁금한 내용이 있으면 언제든지 물어보세요!!!