그래프는 정보 간의 연결 관계를 나타내기 위한 자료 구조이다. search나 중복값 탐색을 위해 그래프 전체를 순회해야할 경우가 생기는데 그래프 순회를 위한 기법 중 하나가 깊이 우선 탐색(Depth first search, DFS)이다. 그래프를 나타내기 위해 많이 사용하는 방법 중 하나가 인접 리스트이다. void initGraph2(vector& adj) { adj.push_back({ {0, 0} }); //sentinel node adj.push_back({ {2, 5}, {4, 9}, {5, 1} }); adj.push_back({ {1, 5}, {3, 2} }); adj.push_back({ {2, 2}, {4, 6} }); adj.push_back({ {1, 9}, {3, 6}, {5, 2..

엘리베이터에는 한번에 탑승 가능한 무게 제한이 있다. 엘리베이터에 탑승하기 위한 승객들이 대기하고 있고, 무게 제한을 만족하면서 최소한의 운행 횟수로 승객들을 운반해야한다. 가장 작은 운행 횟수를 구하는 문제를 동적 계획법으로 해결해보자. 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+..

각 가치가 A, B, C, D인 화폐가 있다고 하자. 최소한의 화폐 장수를 사용하여 특정 액수 X를 만들어야 하는 문제이다. 최적해의 해를 빠르게 구하기 위해서는 동적 프로그래밍(Dynamic Programming)을 이용하여야 한다. typedef vector vi; #define inf pow(2,30); int minNumCoin(int curBalance, vi coinCase, map& selected) { if (curBalance < 0) { return inf; } else if (curBalance == 0) { return 0; } else { int ans = inf; for (auto coin : coinCase){ int pre_result = minNumCoin(curBalanc..