문제 링크https://www.acmicpc.net/problem/17216 문제 요약주어진 수열 \(A\)에서 합이 가장 큰 감소하는 부분 수열을 찾는 문제이다. 문제 풀이감소하는/증가하는 부분 수열을 찾는 문제는 전형적인 동적 계획법(Dynamic Programming) 문제들 중 하나이다. 이 문제 역시 점화식을 세워 동적 계획법으로 문제를 해결할 수 있다. 점화식을 세우기 전에 DP 배열부터 정의를 해보자. \(dp[i]\)는 수열 \(A\)에서 \(A[i]\)로 끝나는 감소 부분 수열의 합 중에서 가장 큰 값을 저장하는 배열이다. 그다음으로 DP 배열을 초기화한다. 각 원소는 자기 자신만을 포함하는 감소 부분 수열이 될 수 있으므로, \(dp[i]\)의 초기값을 \(A[i]\)로 설정한다. 이제..
문제 링크https://www.acmicpc.net/problem/17845 문제 요약최대 공부시간 \(N\)과 과목 수 \(K\)가 주어진다. 이어서 각 과목 \(i\)의 중요도 \(I_i\)와 필요한 공부시간 \(T_i\)가 주어진다. 최대 공부시간 \(N\)을 초과하지 않으면서 중요도 합이 최대가 되도록 과목을 선택할 때, 최대 중요도를 구하는 문제이다. 문제 풀이이 문제는 전형적인 배낭 문제(Knapsack Problem)로 동적 계획법(Dynamic Programming)을 이용해 풀 수 있다. 동적 계획법은 Top Down 방식과 Bottom Up 방식으로 풀 수 있는데, 여기서 두 가지 방법 모두를 이용해 문제를 푸는 방법을 소개한다. Top Down 방식으로 문제 풀기동적 계획법을 Top ..
문제 링크https://www.acmicpc.net/problem/15989 문제 요약정수 N이 주어졌을 때, 1, 2, 3의 합으로 N을 나타내는 경우의 수를 찾는 문제이다. 순서만 다른 것은 같은 경우라는 것을 주의해야 한다. 문제 풀이이 문제는 전형적인 동적 계획법(dynamic programming, 이하 DP)로 해결할 수 있다. DP는 상향식과 하향식 두 가지 방법으로 구현할 수 있는데 보통은 하향식 방법이 구현이 쉽고 직관적이다. 하지만 슬라이딩 윈도우, 컨벡스 헐 트릭등 다양한 DP 최적화 전략을 이용하기 위해서라면 상향식 방법도 이용할 줄 알아야 하기 때문에 두 가지 방법으로 모두 구현을 해본다. 하향식으로 문제 풀기상향식으로 문제를 풀 때 가장 먼저 해야 할 일은 재귀적으로 문제를 해결..
