엘리베이터에는 한번에 탑승 가능한 무게 제한이 있다. 엘리베이터에 탑승하기 위한 승객들이 대기하고 있고, 무게 제한을 만족하면서 최소한의 운행 횟수로 승객들을 운반해야한다. 가장 작은 운행 횟수를 구하는 문제를 동적 계획법으로 해결해보자. vi weight = { 86, 58, 76, 102, 91 }; int lim = 200; input 값으로 승객들의 무게 데이터와 엘리베이터의 무게 제한이 주어진다. pair best[1

배낭 문제는 특정 무게와 가치를 갖는 물건들이 주어질 때 배낭의 무게 제한을 만족하면서 가장 가치를 크게 하는 물건들의 조합을 찾는 전형적인 동적 계획법(Dynamic programming) 문제이다. int knapsack(vi weight, vi value, int limit) { vector ans(weight.size() + 1, vi(limit + 1, 0)); int row = weight.size(); int col = limit; weight.insert(weight.begin(), 0); value.insert(value.begin(), 0); //add sentinel value for (int i = 1; i

2차원의 공간이 주어지고 각 인덱스의 공간마다 특정 값(Value)가 주어진다. 가장 상단 왼쪽의 격자부터 가장 하단 오른쪽의 격자로 이동하면서 경로 상의 값이 총합이 최대가 되도록 하는 알고리즘을 동적 계획법으로 풀어보자. 이동 조건은 오른쪽 혹은 아래 방향으로만 움직인다는 것이다. 1 2 1 2 0 1 3 4 5 6 1 2 3 5 1 위의 예시에서는 1 2 1 2 0 1 3 4 5 6 1 2 3 5 1 위의 경로로 이동하는 것이 최대값을 가진다. int maxSumRoute(vector arr) { vector sum(arr.size(), vi(arr[0].size(), 0)); for (int i = 0; i < arr.size(); i++) { for (int j = 0; j < arr[0].si..

최장증가 부분수열이란 수열이 주어졌을 때, 원소가 차례로 증가하는 부분 원소들을 말한다. 예를 들어 2 6 1 5 7 8 4 9 라는 수열이 있으면 증가하는 부분 배열의 예시들은 다음과 같다. 2 6 1 5 7 8 4 9 2 6 1 5 7 8 4 9 2 6 1 5 7 8 4 9 위의 3가지 예시에서 가장 길이가 긴 케이스는 1번과 2번 케이스로 5의 길이를 가진다. 가장 길이가 긴 케이스를 찾는 알고리즘을 동적 계획법으로 해결해보자. #include using namespace std; typedef vector vi; vi longestIncreasingSubseq(vi arr) { vi leng(arr.size(), 0); //벡터 초기화 for (int k = 0; k < arr.size(); k+..

옛 노래는 "이웃을 미워하라"고 선언하고, 오네틴빌 주민들은 그 말을 마음에 새겼다. 모든 주민들은 양쪽 모두 옆집 이웃들을 싫어한다. 그의 이웃들만큼 마을 우물에서 멀리 떨어진 곳에 살고 싶어하는 사람은 아무도 없기 때문에 마을은 우물 주위에 큰 원을 그리며 배열되어 있다. 불행하게도, 그 마을의 우물은 황폐해졌고 복구가 필요하다. 당신은 세이브 오어 웰 기금을 위한 기부금을 모으기 위해 고용되었습니다. 마을 주민 각자는 기부금에 명시된 대로 일정 금액을 기부할 의사가 있으며, 이는 우물 주위에 시계 방향으로 나열되어 있다. 하지만, 아무도 그의 이웃이 기부한 기금에 기꺼이 기부하려 하지 않는다. 기부금의 첫 번째와 마지막 항목이 이웃을 위한 것이라는 점을 제외하고는 이웃이 기부금에 항상 연속적으로 등..