hades

🥅 문제https://www.acmicpc.net/problem/1753 🔍 설계adj_matrix를 사용하면, 20000*20000*4Byte로 메모리 초과가 발생한다. adj_list를 사용해야 한다. 우선순위 큐를 이용하여 어떤 점에서 갈 수 있는 점까지의 경로 중 작은 것부터 뽑는다. 이렇게 하면 뒤에 갱신하는 경로의 비용은 앞에 있는 경로의 길이보다 항상 크다. 따라서, 반복문의 최대 횟수는 간선의 개수인 300000이 된다. 👊 풀이#include #include #include #include using namespace std;int n, e, k, u, v, w, result = 0;vector>> adj_list(20001);vector dist(20001, 1e9 + 7);pri..

🥅 문제https://www.acmicpc.net/problem/1181 🔍 설계1차로 단어 길이 순으로 정렬, 2차로 사전 순으로 정렬하고, 중복을 제거하면 된다. 중복을 제거하기 위해 unique와 erase를 사용한다. unique는 중복이 있는 원소들을 벡터의 끝으로 보내고, 중복 원소들의 시작점을 반환한다. erase는 erase(iterator first, iterator last); 에서 [first, last) 범위의 원소를 제거한다. 중복을 제거했으므로, 남아있는 원소의 개수는 n이 아닐 수 있으므로 주의한다. 👊 풀이#include #include #include #include using namespace std;int n;string s;vector words;bool comp..

🥅 문제https://www.acmicpc.net/problem/1504 🔍 설계1부터 N까지의 경로 중 최단 경로는 다익스트라 알고리즘으로 구할 수 있다. 하지만 두 점을 무조건 지나야 한다. 1부터 어떤 정점까지 최단 경로를 구하고 갱신하는 과정에서 아무런 구분 없이 비용 하나만으로 갱신하면 안된다. 두 점을 지났는지 여부를 알 수 없기 때문이다. 어떤 정점에 도달하기까지 두 점을 지났는지의 여부에 따라 나오는 경우의 수는 아래와 같이 4이다. 0) v1, v2를 모두 지나지 않음1) v2만 지남2) v1만 지남3) v1, v2 모두 지남 따라서 비용을 저장할 때도 4가지 경우로 나누어 저장한다. ★시작점인 1은 v1일 수도 있고, 아닐 수도 있으므로, 경우에 따라 큐에 넣는 초깃값을 잘 넣어야 ..

🥅 문제https://www.acmicpc.net/problem/1238 🔍 설계각 마을에서 x까지의 최단 시간와 x에서 각 마을까지의 최단 시간을 더하면 된다. 플로이드 워셜 알고리즘을 이용해서 모든 마을에서 모든 마을까지의 거리를 구하고, x까지 갔다가 돌아오는 거리의 최단 시간을 갱신하였다. 시간복잡도는 O(V^3)이다.시간 복잡도를 줄이기 위해 O(ElogV)인 다익스트라 알고리즘을 사용할 수 있다. 최종적으로 시간복잡도는 O(VElogV)이다. 👊 풀이1#include #include #include #include using namespace std;vector> dist(1001, vector(1001, 1e9+7));int n, m, x, start, endd, cost, max_co..

🥅 문제https://www.acmicpc.net/problem/1629 🔍 설계반복문을 사용하여 계속 a를 곱하고 c로 나누면서 갱신한다면, b가 20억 이상이므로 시간 초과가 발생한다. 거듭제곱의 특성 중에 x^(y+z) = x^y * x^z가 있다. 여기서는 간단하게 홀수 짝수로 구분한다. 👊 풀이#include #include #include #include using namespace std;long long a, b, c;long long square(long long b) { if (b == 0) { return 1; } else if (b % 2 == 0) { long long half = square(b / 2); return half * half % c; } else if (..

🥅 문제https://www.acmicpc.net/problem/1167 🔍 설계가지가 1인 노드들에서 dfs를 이용하여 트리의 지름을 구하려고 했는데, 시간 초과가 발생하였다. 도저히 해결방법을 모르겠어서 레퍼런스 블로그를 참고하였다. 임의의 노드에서 가장 먼 노드를 구하고, 그 노드에서 가장 먼 노드를 구하면, 트리의 지름을 구할 수 있다고 한다.어떻게 이런 결과가 나오는지 공부해본다. 임의의 노드를 x라고 하고, x에서 가장 먼 노드를 y라고 하면, 3가지 경우가 있다.1) x가 트리의 지름의 양 끝 점 중 하나라면, x에서 가장 먼 노드인 y가 나머지 끝 점 중 하나가 되므로 y에서 가장 먼 노드(x)까지의 거리는 트리의 지름이 된다.2) y가 트리의 지름의 양 끝 점 중 하나라면, 당연하게 ..

🥅 문제https://www.acmicpc.net/problem/1149 🔍 설계바로 이전 집에서의 색과 다른 색을 칠하기 위해 각 집을 고려할 때마다 큐에서 하나씩 꺼내서 칠할 색을 결정한다. 큐에는 이전 집에서의 색과 비용이 저장되어 있다. 하지만, 칠할 수 있는 색에 대하여 모든 경우를 고려할 경우, 메모리 초과가 발생한다. 따라서, 어떤 집까지 색을 칠했을 때, 최소 비용을 갱신하고, 그 때의 색과 비용을 큐에 저장하면 메모리 초과 문제를 해결할 수 있다. 큐를 이용하지 않고, 간단하게 다이나믹 프로그래밍으로 해결할 수도 있다. 아이디어는 같다. 👊 풀이1#include #include #include #include using namespace std;int n, result = 1e9 +..

🥅 문제https://www.acmicpc.net/problem/1043 🔍 설계파티에 최종적으로 진실을 알게 되는 사람이 한 명이라도 있으면, 거짓말을 할 수 없다. 파티에 진실을 아는 사람을 먼저 찾고, 있으면 파티에 있는 사람들을 진실을 아는 사람들의 집합으로 union 하려고 했는데, 이 방법은 파티 중 뒤에 진실을 아는 사람이 있으면, 앞에 파티에서는 진실을 아는 사람들의 집합으로 union할 수 없다. 단순하게 파티에 있는 사람들을 묶기만 하면, 진실을 아는 사람이 뒤쪽 파티에 나와도 뒤쪽 파티에서 진실을 아는 사람들의 집합으로 반영되기 때문에, 파티 각각에서 진실을 아는 사람이 없으면 총 파티 수에서 감소시키기만 하면 된다. 👊 풀이#include #include #include usi..

🥅 문제https://www.acmicpc.net/problem/28702 🔍 설계3개의 문자열이 주어지는데, 숫자가 하나도 없을 수는 없다. Buzz, Fizz, 숫자Fizz, Buzz, 숫자FizzBuzz, 숫자, 숫자 세 조합만 가능하다. 따라서, 숫자가 몇 번째로 들어오는지 확인 후, 답인 수를 구해 배수 관계를 체크해서 문자열로 반환하면 된다. 👊 풀이#include #include #include #include using namespace std;string s;string check(int n) { if (n % 3 == 0 && n % 5 == 0) { return "FizzBuzz"; } else if (n % 3 == 0) { return "Fizz"; } else if (n..

🥅 문제https://www.acmicpc.net/problem/30804 🔍 설계꼬치에 과일을 모두 꽂아놓고 양끝에서 빼는 것은 앞에서부터 하나씩 끼우고 꽂힌 과일의 종류가 2개를 넘으면 앞에 있는 과일을 빼는 것과 같다. 아직 꽂히지 않은 과일들은 뺐다고 생각하면 되기 때문이다. 과일을 하나씩 끼우고, 꼬치에 현재 없는 과일이라면 과일의 종류를 하나 증가시킨다. 꼬치에 꽂혀있는 과일의 종류가 2개를 초과한다면, 2개가 될 때까지 앞에서부터 뺀다. 2개가 되었으면 결과값을 갱신한다. 👊 풀이#include #include #include #include using namespace std;int n, fruit, type = 0, result = 0;vector fruit_count(10);que..