동적 계획법 (Dynamic Programming)

1. 동적 계획법이란?동적 계획법이란 해결하고자 하는 문제를 작은 문제로 나누어 해결하고, 작은 문제들의 해들로부터 큰 문제의 답을 구하는 방식입니다. 여기서 중요한 점은 "분할과 정복"과 달리 DP는 분할된 작은 문제들이 상호 독립적이지 않고, 일정 부분을 공유한다는 점입니다. 본인은 편의점 알바를 하고있습니다. 그리고 저는 항상 출근하면 가장 먼저 담배 재고를 조사합니다. 담배를 꺼내 세다보면 맨 오른쪽처럼 10개가 넘어가는 재고들이 종종 있는데, 이런 경우에는 한눈에 몇개인지 들어오지도 않고 이런 것들을 하나하나 다 세다보면 재고 조사에 쓰는 시간이 꽤 길어집니다. 그렇다고 대충 눈대중으로 세고 넘어가기에는 여간 찝찝한게 아니죠.사진 속 모든 담배의 개수를 세야한다고 가정해볼까요?  세줄로 나누어 ..

2024.05.26