알고리즘(Java)

[알고리즘] Dynamic Programming(동적 계획법)

1. 동적 계획법(DP)란? - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산X - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 2. DP vs 분할 정복 DP 분할 정복 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨 동일한 부분 문제가 반복적으로 계산되지 X 최적 부분 구조를 가질 때 사용 O (큰 문제를 작은 문제로 나눌 수 있고 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 상황) 3. DP의 2가지 방식 1. Top-Down(하향식) - 재귀 이용 - 메모이제이션 기법 활용 - 한 번 계산한 결과를 메모리 공간에 메모하는 기법(캐싱) - 다이나믹 프로그래밍 구현 기법(하..