[알고리즘] Dynamic programming(동적 계획법) 이란?

Dynamic programming(동적 계획법)이란? 수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제(sub problem) 반복과 최적 부분 구조(optimal sub structure)를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 앞선 설명과 같이 Dynamic programming, 줄여서 DP 기법은 어떠한 문제를 풀 때, 해당 문제를 더 작은 부분 문제로 쪼갤 수 있는 경우, 그리고 최적 부분 구조의 형태를 갖는 경우에 문제를 더욱 효율적으로 해결할 수 있는 방법입니다. 부분 문제와 최적 부분 구조에 대한 조금 자세한 설명은 아래에서 하도록 하겠습니다. Dynamic programming의 핵심 아이디어 문제를 더 작은 문제로 쪼개는 과정에서 중복되는 부분 문제들이 등장하게 되는데, 이를 매번 계산하는 것이 아니라 처음 계산할 당시에 메...

원문링크 : [알고리즘] Dynamic programming(동적 계획법) 이란?