정리하기 위한 블로그 정리하기 위한 블로그

DP와 메모이제이션 개념 동적 계획법 (dp) - 복잡한 문제를 작은 부분 문제(subproblem)으로 쪼개어, 각 부분 문제의 최적해를 계산하여 중복 계산을 피하면서 전체 문제의 최적해를 찾는 알고리즘 설계 기법. 전체 문제의 하위 부분 문제의 답으로부터 전체의 답을 구하는 방법. 메모이제이션 - 중복 계산을 피하기 위해 계산 결과를 따로 저장해놓는 기법. dp 에서 사용되는 기법 중 하나이다. dp에 포함되는 개념. DP의 2가지 주요 요소 1. Optimal Substructure (최적 부분 구조) : 하위 문제의 최적해로부터 전체 문제의 최적해를 구할 수 있음. 2. Overlapping sub-problems (겹치는 부분 문제) : 동일한 부분문제가 여러번 반복적으로 해결되는 현상. 메모이..