hades

🥅 문제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..

🥅 문제https://www.acmicpc.net/problem/2638 🔍 설계치즈가 닿아있는 블럭이 2개 이상이면 녹을 예정이다. 치즈 내부에 있는 공기는 치즈에 영향을 줄 수 없다. 모눈종이의 맨 가장자리들은 치즈가 놓이지 않는다고 했으므로, 그 중 대표적인 (0, 0) 에서 시작하여 외부 공기의 영향력을 행사한다.  외부 공기의 영향력을 행사하는 방법은 BFS를 이용하여 치즈가 놓인 곳에 2번 방문했을 때, 1시간 후에 녹으면서 새롭게 영향력을 행사할 수 있는 외부 공기 후보들의 모임인 next_q에 추가하는 것이다. 만약 next_q에 아무것도 추가되지 않는다면 그대로 종료되고, 추가된 것이 있다면 1초를 증가시킨다. next_q에 추가하는 이유는 치즈가 녹는 과정은 1시간 후에 동시에 이루..

🥅 문제https://www.acmicpc.net/problem/15654 🔍 설계전형적인 백트래킹 문제이다. 사전 순으로 출력해야 하므로, 오름차순 정렬 후, 백트래킹을 사용하면 된다. 👊 풀이#include #include #include using namespace std;int n, m;vector number(8);vector visited(8);vector temp;void bt(int count) { if (count == m) { for (int i = 0; i > n >> m; for (int i = 0; i > number[i]; } sort(number.begin(), number.begin() + n); bt(0); return 0;}

🥅 문제https://www.acmicpc.net/problem/9465 🔍 설계처음에 전 열에서 어떤 행을 사용했는지에 따라 큐에 추가하는 방식을 사용하려고 생각해보았는데, 2^100000으로 시간 초과가 발생할 것으로 생각되어 제외하였다. 쉽게 다이나믹 프로그래밍을 이용하여 해결할 수 있다. 현재 열에서 0행을 사용할 것이라면, 전 열에서는 1행 또는 아무것도 사용하지 않았을 때의 값 중 최댓값에 더해야 한다. 아무 것도 사용하지 않았을 때는 인덱스 2에 저장하였다. 현재 열에서 1행을 사용할 것이라면, 전 열에서는 0행 또는 아무것도 사용하지 않았을 때의 값 중 최댓값에 더해야 한다  현재 열에서 아무것도 사용하지 않을 것이라면, 전 열에서 0행을 사용을 사용했을 때와 1행을 사용했을 때 중 큰..

🥅 문제https://www.acmicpc.net/problem/2096 🔍 설계전 줄까지의 결과에 새로운 줄에 입력받은 수를 더하여 최대 최소를 구하는 다이나믹 프로그래밍 문제이다. 처음 메모리 제한을 보지 않고, 100000줄을 다 받았는데, 메모리 초과가 발생하였다. 새로운 줄에 입력받을 수와 전 줄까지의 점수, 새로운 줄까지의 점수만 필요하므로 벡터를 3개만 생성한다. 다이나믹 프로그래밍에서는 초기화가 항상 중요한데, 첫째 줄까지의 점수는 입력받은 수 그대로이다.  👊 풀이#include #include #include using namespace std;int n, col;int dy[] = { -1,0,1 };vector new_line(3);vector> before_score(3, {..

🥅 문제https://www.acmicpc.net/problem/1987 🔍 설계어떤 알파벳을 중복해서 방문할 수 없으므로, 알파벳에 대한 방문 여부를 visited에 저장한다. 말이 최대 연속해서 몇 칸을 지날 수 있는지 구하기 위해서는 DFS를 이용해야 한다. 지나는 경로 중간에 다른 방향으로 경로를 탐색하기 위해 백트래킹을 이용한다. 👊 풀이#include #include #include using namespace std;int r, c, result = 0;int dx[] = { -1,1,0,0 };int dy[] = { 0,0,-1,1 };vector> board(20, vector(20));vector visited(26);string s;void dfs(int cur_x, int cu..

🥅 문제https://www.acmicpc.net/problem/1918 🔍 설계후위 표기식을 나타내는 데는 스택을 사용한다. A+B-C의 경우, ABC-+ 인데, 출력 순서를 고려하면, 먼저 들어온 +가 나중에 출력되어야 하기 때문이다.  알파벳이면, 그냥 출력하여 스택에는 괄호와 연산자만 담기게 한다. 괄호 내부의 식을 고려하기 위해, 현재 문자가 '('이면 스택에 그냥 추가하고, ')'이면, 괄호 내부에서 아직 출력하지 않은 연산자를 출력하고, '('를 제거하여 괄호 내부의 식을 끝낸다. 현재 문자가 괄호가 아닌 연산자이면, 뒤에 괄호가 올 수 있으므로, 마지막에 스택에 추가해야 한다. 괄호에 대한 연산자를 먼저 출력하고, 그 이후에 출력해야 하기 때문이다. 마지막에 스택에 추가하기 전에 연산자..

🥅 문제https://www.acmicpc.net/problem/11501 🔍 설계어느 날의 가격보다 이후의 날 가격들 중 가장 높을 때 팔아야 이익을 최대화할 수 있다. 가장 가격이 높은 날에 팔고, 그 날 이후의 날들 중에서 가장 가격이 높은 날 팔고, 이 방식을 반복해야 한다. 현재 상황에서 가장 높은 가격을 구하기 위해 우선순위 큐를 활용했는데, 중요한 것은 남아있는 가격들 중 가장 높은 가격에 차익을 보고 판매한 주식 가격들이 있으므로, 인덱스를 함께 담아 제거해야 한다. 맨 뒤까지 고려했을 때, 주식 가격이 가장 높은 지점에서 팔아야 한다. 순서를 바꿔서 맨 뒤부터 최댓값을 갱신하면서 차이를 빼주면 간단하게 해결할 수 있다. 👊 풀이#include #include #include #inc..

🥅 문제https://www.acmicpc.net/problem/11657 🔍 설계음수인 간선이 존재하므로, 벨만 포드 알고리즘을 사용해야 한다. 데이크스트라를 이용한다면 음수 간선으로 인해 거리가 음의 무한대로 계속 갱신되어 무한 루프에 빠지게 된다. 기본적인 벨만 포드 식은 Dx(y) = min(Dx(y), Dx(z) + z~y)이다. x에서 y까지의 최소 거리는 x에서 z까지 최소 거리 + z에서 y까지의 거리 중 최솟값이다. 벨만 포드 알고리즘은 벨만 포드 식 적용이 확산된다고 생각하면 된다. 물론, 벨만 포드 알고리즘도 사이클로 인해 음의 무한대가 발생할 수 있다. 정점의 개수가 n이라고 할 때, 한 정점에서 다른 정점들까지의 거리를 모두 갱신하는데는 n-1번 모든 간선에 대해 벨만 포드 식..

🥅 문제https://www.acmicpc.net/problem/1916 🔍 설계인접 리스트를 활용하여 데이크스트라 알고리즘으로 해결할 수 있다. 다만, 우선순위 큐를 활용하므로, 이미 어느 정점까지 가는데 최소 비용으로 갱신되었을 수도 있으므로, 확인 후 skip하는 것이 필요하다. 그렇지 않으면 인접한 정점까지 반복문을 또 돌게 되어 시간 초과가 발생한다. 👊 풀이#include #include #include #include using namespace std;int n, m, start, endd, cost, a, b;vector>> adj_list(1001);vector dist(1001, 1e9 + 7);priority_queue, vector>, greater>> pq;void Dijk..