목록2026/06 (1)

clohi 님의 블로그

동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming, DP) 이란 ? 큰 문제를 작은 부분 문제로 쪼갠 뒤, 한 번 푼 부분 문제의 답을 저장해두고 재활용하는 알고리즘 설계 기법 DP는 문제를 작게 쪼갠다는 점에서 분할 정복(Divide and Conquer)과 헷갈릴 수 있지만 분할 정복은 쪼갠 부분 문제들이 서로 겹치지 않는 반면 DP는 같은 부분 문제가 여러 번 반복해서 등장한다. DP를 쓸 수 있는 조건 1. 최적 부분 구조(Optimal Substructure) : 큰 문제의 최적해가 작은 문제들의 최적해로 구성되는 성질 EX) 최단 경로 문제에서, A에서 C로 가는 최단 경로가 B를 거친다면, A→B 구간 역시 최단 경로여야 한다. 부분이 최적이어야 전체가 최적이 되는 구조다. 2. 겹치는 ..
CS/자료구조&알고리즘 2026. 6. 2. 14:00
이전 Prev 1 Next 다음