코딩
-
알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)study/알고리즘 2020. 2. 10. 17:03
알고리즘 풀이를 하다보면 많은 문제가 다이나믹 프로그래밍(DP)를 이용해 풀이가 가능합니다. 그렇기 때문에 알고리즘을 공부하기 위해서는 꼭 알아가야 하는 파트입니다. 다이나믹 프로그래밍은 동적 계획법으로도 불리는데, 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어지면 각 단계의 부분 문제에 대한 답을 기반으로 하여 전체 문제의 답을 구하는 방법 입니다. 정리하자면 큰 문제를 작은 문제들로 쪼개어 푸는 알고리즘이라 생각하면 됩니다. TMI - 다이나믹 프로그래밍의 이름은 알고리즘의 고안자인 리차드 벨만이 Dynamic이란 말이 멋있어서 붙였다고 합니다. 문제를 다이나믹 프로그래밍을 사용하여 풀기 위해서는 2가지 속성을 만족해야합니다. Overlapping Subproblem (부분 문제 반복) Opt..