동적프로그래밍 (Dynamic Programming)에 대하여
❓ 동적 프로그래밍이란
- 동적 프로그래밍(이하 DP)는 컴퓨터 프로그래밍이 아니라 테이블을 만드는 것이다.
- 또한 전혀 다이나믹하지 않아 기억하기 프로그래밍이라고도 불린다.
- 반복적으로 계산되는 것들을 저장해두었다가 사용하는 메모이제이션 방법이 DP의 한 방법이다.
- 알고리즘을 짤 때 Divide and Conquer 방법을 많이 사용하는데 이 때 한 문제를 여러 개의 작은 문제로 나누어 풀게되어 같은 문제를 반복해서 푸는 경우가 발생한다. 이를 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 DP이다.
- 즉, 작은 문제들은 한 번만 풀어서 계산한 값을 저장해두어야한다. (Memoization)
📌 Bottom Up & Top Down
- Bottom Up : 작은 문제부터 하나하나 해결해나가는 방법.
def fibo_bottom_up(n) : if n <= 1: return n fir = 0 sec = 1 for i in range(0, n - 1) : next = fir + sec fir = sec sec = next return next
- Top Down : 재귀함수로 대부분 구현, 큰 문제를 풀 때 작은 문제가 풀리지 않았다면 그제서야 해결하게된다.
def fibo_top_down(n) : if memo[n] > 0 : return memo[n] if n <= 1: memo[n] = n return memo[n] else : memo[n] = fibo_top_down(n - 1) + fibo_top_down(n - 2) return memo[n]
🙋♂️ 정리
- 큰 문제를 풀 때 작은 문제부터 하나하나 해결하다보면 규칙을 발견할 수 있게된다.
- dp[0], dp[1], dp[2], dp[3]를 해결하다보면 규칙을 발견하고 dp[4]를 해결할 때 쯤 이전에 구해놓은 작은 문제들로부터 점화식을 구할 수 있게된다.
👀 출처
Author And Source
이 문제에 관하여(동적프로그래밍 (Dynamic Programming)에 대하여), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@moonpiderman/동적프로그래밍-Dynamic-Programming에-대하여저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)