알고리즘 - 동적계획법 (Dynamic Programming)

본 게시물은 경희대학교 한치근 교수님의 '알고리즘분석' 강의를 듣고 노트한 내용입니다. 원래는 multistage decision processes라고 불렸으나 정부기관의 관료에게 그럴듯하게 보이기 위해 dynamic으로 명명함 분할정복식은 하향식 해결법 (top-down approach), 서로 상관관계가 없는 문제를 해결하는 데에 적합 그러나, 피보나치 알고리즘은 같은 항이 여러번 호출됨 -> 비효율적 동적계획법 상향식 해결법 (bottom-up approach) 문제를 나눈 후에 작은 문제들을 먼저 푼다. 이항계수 구하기 계산량이 많은 n!과 k!를 계산하지않고 이를 부분으로 나눈다. 1) 분할정복식 *재귀호출을 할 때 같은 계산을 반복해서 수행하게됨. -> 비효율성 증대 2) 동적계획식 2차원 배..