BOJ11726
-
Dynamic ProgrammingAlgorithm 2022. 4. 14. 13:51
정의 우리말로 동적 계획법이라고 번역되어지는 말입니다. 우선 명칭에 대해서 좀 어색할 수 있다. 이는 해당 어원이 오래되었기 때문입니다. 당시에 programming이란 문제 풀이를 위한 planning(계획) 정도로 생각했습니다. 따라서, Dynamic Programming이 의미하는 바는 다단계 처리에 대한 최적화된 계획법 정도로 해석할 수 있습니다. Dynamic Programming을 사용하기 위해서는 해당 문제가 다음과 같은 조건을 만족할 때입니다. Optimal Substructure Overlapping Subproblem Optimal Substructure란 문제의 최적해가 이것의 하위 문제(subproblem)의 최적해에 의해서 정의되어질 수 있어야 한다는 것입니다. 쉽게 말해서 수열의..