📌 1. DP(동적 계획법)란 무엇인가?DP(Dynamic programming)는 큰 문제를 풀기 위해 작은 문제로 나누고, 그 작은 문제의 답을 저장해두었다가 재활용해서 빠르게 푸는 알고리즘입니다. 반드시 아래 두 조건을 만족해야만 이 알고리즘을 쓰는 의미가 있습니다.최적 부분 구조(optimal substructure) : 큰 문제의 최적해가 작은 문제의 최적해로 구성됨중복 부분 문제(overlapping sub-problems) : 동일한 하위 문제를 여러 번 계산해야 하는 경우더 쉽게 풀어서 설명우리가 문제를 풀 때 똑같은 계산을 계속 반복하게 되는 경우가 있습니다.DP는 그런 "같은 계산을 다시 하지 않기 위해" 한 번 계산한 결과를 어딘가에 저장해놓고 그 값을 나중에 가져다 씁니다.그래서 ..