hades

🥅 문제https://www.acmicpc.net/problem/15486 🔍 설계데이터가 엄청 많고, 최대의 이익을 얻도록 상담을 구성하므로, 다이나믹 프로그래밍으로 방향을 잡았다. dp[i]에는 상담을 i번째 날까지 했을 때, 최대 이익을 저장한다. i로부터 상담이 끝나는 날은 i + 소요 날 - 1이고, 이것을 finish_day로 지정하였다. i번째 날에 상담을 시작한다면, 상담이 끝난 날 얻는 이득인 dp[finish_day]는 dp[i-1] + 상담 이익이다. 여기서 dp[i]가 아닌 dp[i-1]을 더해야 함에 유의한다. dp[i]는 i번째 날까지 상담이 이루어지므로 상담을 시작할 수 없다. 또한, i번째 날에 상담이 끝나지 않는 경우를 고려하면, 전날까지의 이익과 비교하여 최댓값을 구하..

🥅 문제https://www.acmicpc.net/problem/30805 🔍 설계사전 순으롤 가장 뒤에 있는 공통 부분 수열을 찾으면 되므로, 먼저 각 수열을 큰 수가 앞에 오도록, 수의 크기가 같다면, 인덱스가 작은 것이 앞에 오도록 하게 하기 위해 우선순위 큐를 이용하였다.  각각의 우선순위 큐에서 앞에 있는 하나를 꺼내면서 같다면, 결과에 추가한다.다르다면, 큰 것이 있는 우선순위 큐에서 하나를 없앤다. 큰 것이 계속 남아있다면, 그와 같은 것이 다른 쪽에 없기 때문이다. 주의해야할 것은 크기 뿐만 아니라 결과에 포함되는 수가 각각 양쪽 수열에서 어느 인덱스에 위치하는 지를 기록하고, 그 인덱스보다 작다면 결과에 추가될 수 없으므로 없애는 과정이 포함되어야 한다. 👊 풀이#include #i..

🥅 문제https://www.acmicpc.net/problem/16236 🔍 설계초기 설계에서는 초를 늘리면서, 거리가 동일할 때는 위, 왼쪽, 오른쪽, 아래 순으로 우선순위가 높으므로, 탐색 순서도 위, 왼쪽, 오른쪽, 아래 순으로 탐색한다.  먹을 수 있는 것이 있으면, 바로 먹고, 거리를 반환한다. 먹을 수 없으면, 거리를 갱신하고, 큐에 담는다. 반환된 거리가 0이 아니면, 먹을 수 있는 것이 있다는 의미이므로, 최종 결과에 더한다.반환된 거리가 0이면 먹을 수 있는 것이 더 이상 없다는 의미이므로 반복문을 종료한다.#include #include #include #include using namespace std;int n, baby_shark_size = 2, eat_count = 0, ..

🥅 문제https://www.acmicpc.net/problem/5639 🔍 설계입력으로 주어진 50 30 24 5 28 45 98 52 60 에서 루트, L, R을 구분하면, 50 30 24 5 28 45 98 52 60 이다.L, R 서브트리 각각의 서브트리를 구해도 루트는 첫 번째, L은 두 번부터 루트보다 작은 수까지, R은 루트보다 큰 수부터 끝까지라는 것을 알 수 있다. 서브 트리에 해당하는 인덱스의 범위를 재귀로 만들어서 LRV를 진행하면 된다. 주의해야할 점은 개수가 정해져 있지 않기 때문에, while을 이용하여 벡터에 입력값을 지정했는데, 이럴 경우 최종 인덱스는 마지막 인덱스보다 하나 더 많은 총 개수이다. 따라서 범위를 지정할 때, end는 사용되지 않는다는 것에 유의해야 한다...

🥅 문제https://www.acmicpc.net/problem/17144 🔍 설계확산, 반시계 순환, 시계 순환을 각각 구현하면 된다. 먼저, 확산을 설계해보았다. 확산은 동시에 일어나기 때문에, 기존 벡터에서 진행하면 안된다.  예를 들어, 0행 0열에서 확산이 일어났고, 확산된 양을 0행 1열에 추가하면, 0행 1열에서 확산이 일어날 때, 더해진 양을 고려한 미세먼지의 양으로 확산이 일어난다. 따라서, 확산과 관련된 연산은 before_spread에서 하고, 확산되는 양과 남은 양을 저장하기 위해 after_spread를 만들었다. 확산되는 양의 총합을 구하기 위해 확산되는 위치에서 더하는 것은 잘했으나, 남은 양을 저장하는 데 있어서 =으로 처리해서 문제가 있었다. =으로 처리할 경우, 확산되..

🥅 문제https://www.acmicpc.net/problem/9935 🔍 설계문자열의 반복문을 돌리면서, 폭발 문자열과 일치하는 부분 문자열이 만들어지면, 맨 위부터 폭발시켜야 하므로, 스택을 이용한다는 것은 쉽게 파악할 수 있었다.  폭발 문자열과 일치하면 현재 인덱스에서 폭발 문자열에서 일치한 인덱스를 save에 저장하고, 다음 탐색할 인덱스(cur_idx)를 1 증가시키면서 폭발 문자열의 길이와 일치하면 폭발시키는 방식으로 설계했다. 초기 설계에서의 문제점은 스택에 문자만 담았기 때문에 폭발하고 난 후, 다음 탐색할 인덱스를 폭발 문자열이 완성된 위치에서 폭발 문자열의 길이를 뺀 인덱스에서의 save 값과 같이 잘 못 구했었다. 하지만 이런 경우,  abaabcdbcdcd abcd  와 같이..

🥅 문제https://www.acmicpc.net/problem/1197 🔍 설계단순히, 최소 스패닝 트리를 구현하는 문제이다.  최소 스패닝 트리를 어떻게 구현하는지 복기해보자. 1. 간선 정보를 비용을 기준으로 오름차순으로 정렬한다. 본인은 우선순위 큐를 사용하였다.2. 우선순위 큐에서 하나씩 꺼내서(= 비용이 작은 간산부터) 두 정점을 연결 시도한다. 두 정점의 부모가 같은 경우, 이미 연결되어 있다는 뜻이므로 넘어간다. 두 정점의 부모가 다른 경우, 연결되어 있지 않다는 의미이므로 union을 통해 연결하고 가중치에 비용을 추가한다. 👊 풀이#include #include #include #include using namespace std;int v, e, a, b, c, result = 0..

🥅 문제https://www.acmicpc.net/problem/9663 🔍 설계N-Queen에서 퀸들은 같은 행, 같은 열, 대각선에 놓이지 말아야 한다. 한 행씩 모든 열에 배치를 시도하고, 배치가 가능하면, 다음 행으로 넘어가서 배치한다. 이 과정을 반복한다. check에서 현재 행과 현재 행 이전까지의 행을 살펴보기 때문에 같은 행에 놓일 수 없고, 같은 열인지, 대각선에 위치하는지만 확인하면 된다. 👊 풀이#include #include #include #include using namespace std;int n, result = 0;vector col(15);bool check(int cur_row) { for (int i = 1; i > n; nqueen(1); cout

🥅 문제https://www.acmicpc.net/problem/1932 🔍 설계어떤 수까지의 경로 상의 합은 맨 위부터 왼쪽 아래, 오른쪽 아래를 계속 선택하여 얻어지므로 다이나믹 프로그래밍을 이용한다. 일차원 배열에 수를 모두 담았을 때, 어떤 수가 n번째 줄에 있다면, 왼쪽 아래에 있는 수는 +n에 있고, 오른쪽 아래에 있는 수는 +(n+1)에 있다. 👊 풀이#include #include #include #include using namespace std;int n, number, k, result;vector triangle(1, -1);vector dp(500 * 501 / 2);int main(void){ ios_base::sync_with_stdio(false); cin.tie(nul..

🥅 문제https://www.acmicpc.net/problem/15666 🔍 설계같은 수를 여러 번 사용해도 되므로, 수를 저장할 때 여러 개를 저장할 필요가 없으므로 중복을 제거한다. 중복을 제거하기 전에 오름차순 정렬이 이루어지므로, 비내림차순으로 결과를 출력할 준비가 되었다. 중복을 허용하므로 방문 처리는 필요가 없고, 비내림차순이므로 마지막으로 사용한 인덱스부터 이후까지 사용할 수 있다. 👊 풀이#include #include #include #include using namespace std;int n, m, temp;vector number;vector result;void bt(int count, int last_idx) { if (count == m) { for (int i = 0..