동적계획법 #DP #동적프로그래밍 #그리디 #탐욕알고리즘 #알고리즘 #알고리즘전략
-
DP 동적 계획법Algorithm 2020. 7. 2. 17:35
1. 큰 문제를 작은 문제들로 나누어 해결한다 2. 작은 문제들은 결과값을 저장하여 다시 사용할 수 있도록 한다 ( 메모이제이션 ) 주로 greedy(그리디, 탐욕)알고리즘과 자주 비교된다. (공통) 둘다 전체 문제를 작은 문제단위부터 해결하여 최적점에 도달한다는 전략을 취하지만, (차이) greedy는 작은 문제단위에서 최선의 선택이 큰 문제에서의 최선의 선택과 일치되는 경우에 사용 가능하고, dp는 작은 문제단위에서 best선택을 하더라도 큰 문제에서 best가 보장되지 않을 때 사용하면 된다. 1. Top-Down 방식 : 초기의 큰 문제단위에서 작은 문제단위로 접근하며 : 재귀함수를 이용해 구현한다 1) 작은 문제들의 결과값을 저장할 변수를 만들고 모두 worst상태로 초기화한다 2) functi..