다이나믹 프로그래밍

개요알고리즘 학습을 하다 보면 반드시 한 번쯤은 마주치게 되는 유명한 문제가 있습니다. 바로 '배낭 채우기 문제' (Knapsack Problem)입니다. 배낭 문제는 크게 두 가지로 나뉩니다. 물건을 부분적으로 쪼갤 수 있는 Fractional Knapsack 문제와, 물건을 온전히 하나만 선택하거나 선택하지 않아야 하는 0/1 Knapsack 문제가 있습니다. 실제 현실 세계에서는 물건을 마음대로 쪼개서 담을 수 없는 경우가 대부분이기 때문에, 0/1 배낭 문제가 주로 사용되고는 합니다. 본 글에서는 두 가지 문제 중  0/1 Knapsack 문제에 대해서 정리하고자 합니다. 배낭 문제 해결을 위한 초기 접근 방법들도둑이 보석 가게에 침입했다.배낭의 최대 용량을 초과하면 찢어지기 때문에, 무게 제한 ..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - RGB 거리" 문제는 거리에 있는 집들을 R(red), G(green), B(blue)로 칠할 때, 다음 제약사항을 만족하면서 최소 비용으로 칠하는 문제입니다.인접한 집은 같은 색으로 칠할 수 없음1번 집과 2번 집은 다른 색이어야 함N번 집과 N-1번 집은 다른 색이어야 함2~N-1번 집은 양옆의 집과 다른 색이어야 함현재 집을 칠하는 최소 비용이 이전 집의 색상 선택에 따른 최소 비용에 의존하므로, 문제를 작은 부분 문제로 나누어 해결할 수 있는 최적 부분 구조를 만족하며, 동일한 계산이 반복되는 중복되는 부분 문제 특성도 있어 다이나믹 프로그래밍으로 해결할 수 있습니다. [Algorithm] 동적 계획법(Dynamic Programming, DP..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 퇴사" 문제는 퇴사 전 최대 수익을 창출할 수 있는 상담을 선택하여 최대 수익을 내는 것 입니다. 상담 기간과 수익이 주어지며, 특정 상담을 수행하면 해당 상담 기간만큼의 날이 소요됩니다.퇴사일 이후로 상담이 넘어가면 해당 상담은 수행할 수 없습니다.최대 수익을 구하기 위해 DP를 활용합니다. 문제 자체는 어렵지 않으나 점화식을 도출하는 과정이 까다롭습니다. 우리의 목표는 퇴사 전 최대 수익을 뽑는 것인데, 각 날짜에서 상담을 선택하거나 선택하지 않는 경우를 고려하고, 이전까지의 최적해를 활용하여 현재의 최적해를 구하는 동적 계획법의 특성을 잘 활용해야 합니다. 특히 상담이 걸리는 기간과 수익을 고려하면서 dp 배열에 각 날짜까지의 최대 수익을 저장하..

문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 포도주 시식" 문제는 포도주가 1 ~ n개 있을 때 아래의 조건을 만족하는 가장 많은 양의 포도주를 마실 수 있는 양을 출력하는 문제입니다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.즉, 순서대로 포도주를 마실때 최대의 포도주 양을 구하면 되는 문제입니다. 문제의 핵심은 연속해서 3잔을 마실 수 없을 때 최대의 포도주 양을 구하는 것이 기 때문에, 이 점을 고려해야합니다. 위와 같이 테이블에 연속된 포도주가 [6, 10, 13, 9, 8 ,1]이 있을 때 마실 수 있는 최대의 포도주의 양은 첫 번째, 두 번째, 네 번째, 다섯 번째 포도..