[동적 계획법] Dynamic programming
동적 계획법이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔다. 중복되는 부분 문제 없애 최적화하여 속도향상을 꾀하는 알고리즘 설계 기법이 바로 동적 계획법이다. 동적계획법은 분할 정복과 접근방식이 같다. 주어진문제 -> 더 작은문제들 -> 조각 계산 -> 조각의 답들로부터 원래 문제 답 계산 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에 여러번 계산하는 대신 한번만 계산하고 계산 결과를 재활용함으로써 속도 향상을 꾀함 각 문제의 답을 메모리에 저장해 둘 필요가 있음 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시라고 부름 두번 이상 계산되는 부분문제를 부분 문제(overlapping subproblems)라고 부름 계산의 중복 횟수는 분할의 깊이가 깊어질 수록 지수적으로 ..
2021.01.06