소피it블로그

자료 출처: https://youtu.be/cswJ1h-How0 1. 투 포인터 알고리즘 예시 문제: 특정한 합을 가지는 부분 연속 수열 찾기 start, end가 0번째 인덱스를 가리키도록 함 (start

문제 출처: https://youtu.be/5Lu34WIx2Us 이 문제가 다이나믹 프로그래밍 유형인 이유를 먼저 생각해보자. 2, 3원을 가지고 15원을 만들 수 있는지, 있다면 최소한의 화폐 개수는 몇 개인지 알기 위해서는 어떻게 해야 할까? 15원을 만들기 위한 최소한의 화폐 개수를 f(15)라고 하자. (15원에서 2원을 뺀) 13원과 (3원을 뺀) 12원을 만들 수 있다면, 각각 +2원 or +3원의 과정을 한 번만 더 하면 15원을 만들 수 있을 것이다. 즉, f(15)의 최솟값은 min(f(13), f(12)) + 1원이 된다. 13원일 때의 최소 화폐 개수와 12원일 때의 최소 화폐 개수를 비교하여 거기에 한 번의 연산만 더해준다면 f(15)를 구할 수 있다는 것. 그렇다면 f(13)과 f..

문제, 풀이 출처: https://youtu.be/5Lu34WIx2Us 이 문제 역시 1) 최적의 부분 구조와 2) 중복되는 부분 문제라는 조건을 만족시키기 때문에 다이나믹 프로그래밍으로 접근하여 풀 수 있다. 핵심은, 한 칸 이상씩 떨어진 식량 창고를 털어야 하기 때문에 마지막 n번째 식량 창고에 대하여 1) i - 1 번째 식량 창고까지의 최적의 해 2) i - 2 번째 식량 창고까지의 최적의 해 + i번째 식량 창고에 저장된 식량 둘 중 더 큰 값을 선택하면 된다는 것. 그리고 각각은 부분 문제로 반복된다는 점을 파악하는 게 중요하다. i번째 창고까지의 최적의 해를 Ai라고 하고, i번째 창고에 있는 식량의 양을 Ki라고 한다면 다음과 같은 점화식이 성립한다. Ai = max(Ai-1, Ai-2 +..