웅재의 코딩세상

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고, 다시 그 결과를 이용하여 큰 문제를 해결 할 때 사용하는 방식이다. 결과를 저장할 공간이 있어야 하기 때문에 이렇게 되면 공간 복잡도 측면에서 보면 손해를 볼 수 밖에 없다. 하지만 시간 복잡도 측면에서 큰 이득을 볼 수 있기 때문에 공간 복잡도를 포기하는 기법이다. 알고리즘 문제를 풀다 보면 엄청나게 큰 시간 복잡도를 요구하는 문제들이 존재한다. -> O(n!) or O(n^n) 등 위의 시간복잡도를 가진 문제를 동적 계획법을 적용하여 문제를 풀면 O(n^2)과 같은 형태로 줄일 수 있다. 하나의 case의 경우를 보고 규칙을 찾아낸 후 그 규칮을 전체에 대해 일반화 시키는 점화식을 찾아내는 것이 중요하다. 동적계획법 예제 각 칸마..