Dev On The Coffee Dev On The Coffee

# 다이나믹 프로그래밍 (Dynamic Programming) 현대에서 컴퓨터를 사용해도 해결하기 어려운 문제는 최적의 해를 구하는데 매우 많은 시간을 요하거나 메모리 공간을 매우 많이 요구하는 문제들이다. 그런데 어떠한 문제는 메모리 공간을 조금 더 사용하면 연산 속도를 비약적으로 상승시킬 수 있는 방법이 있다. 메모리를 적절히 사용하여 수행 시간 효율을 비약적으로 상승시키는 방법을 다이나믹 프로그래밍(Dynamic Programming)이라고 하며 동적 계획법이라고도 부른다. 다이나믹 프로그래밍은 1. 큰 문제를 작게 나누고, 2. 같은 문제라면 한 번 씩만 풀어 문제를 효율적으로 해결하는 알고리즘이다. 즉, 다이나믹 프로그래밍은 다음의 두 조건을 갖췄을 때만 사용가능하다. 1. 최적 부분 구조 (O..