재원블로그 재원블로그

이 문제는 유니온 파인드, 배낭 문제 알고리즘을 이용해서 풀었다. 한 아이의 사탕을 뺏으면 친구들의 사탕도 모조리 뺏는다는 조건을 보고 유니온 파인드를 떠올렸다.친구 그룹을 형성하여 총 사탕 수와 총 인원 수를 각각 candy, groupCount에 저장했다. 또한 각 그룹을 선택할지 말지에 대한 배낭 문제와 동일하다는 생각이 들어 배낭 문제의 알고리즘을 그대로 사용했다.이 때 주의할 점은 dp[i - 1]에 대한 비교가 계속되므로 i = 0일 때 i = -1인 지점을 찾게 되어 오류가 발생할 수 있다.따라서 i = 1부터 시작하도록 만들어 문제를 해결했다.#include #include #include #include using namespace std;#define MAX 30000vector> fr..

이 문제는 유니온 파인드를 이용해서 풀었다. 처음에는 dfs를 이용해서 그룹 수를 찾으면 되겠다고 생각했지만, 이는 정확한 정보를 주지 못한다.D L L LD UR R U와 같은 경우 만약 (0, 0)부터 탐색을 돌 경우 왼쪽 원에만 visited가 true가 되고 맨 오른쪽 L는 적용되지 않는다. 따라서 그룹이 2개가 나오게 된다. 그러나 전체가 그룹 하나로 이루어져야 정답이 된다. 따라서 이 같은 경우를 없애기 위해 유니온 파인드로 그룹화를 했다. 각 좌표에 대해 번호를 매기고, 이 번호를 토대로 그룹화를 하여 쉽게 문제를 풀 수 있었다. 주의할 점은 safe zone의 개수를 구할 때 set를 사용하면 시간 초과가 난다는 점이다. 단순히 for문 두개로 푸니 정답이 나왔다.#include #in..

이 문제는 최소 스패닝 트리를 이용한 문제이다. 최소 스패닝 트리는 모든 정점을 연결한 최소의 가중치의 부분 그래프를 의미한다.문제에서는 마을을 두 개의 분리된 마을로 분할해야 하고, 마을에는 집이 하나 이상 있어야 한다는 요구사항이 있다. 최소 스패닝 트리가 모든 정점을 연결한 최소 가중치의 부분 그래프라면, 크루스칼 알고리즘을 통해 MST를 만들 때 마지막으로 merge된 간선을 빼준다면 두 개의 부분 트리가 만들어 질 것이라고 예상하고 문제를 풀었고 정답을 맞출 수 있었다.#include #include #include using namespace std;#define MAX 100000struct Edge { int a; int b; int cost;};vector edges;int N, M;in..

이 문제는 백트래킹 문제이다. 시간 복잡도를 조금이라도 줄이려면 애초에 백트래킹 탐색을 할 때 사전식으로 앞서도록 탐색하게 만들면 된다. 어떤 좌표 (y, x)가 있을 때, 이를 3으로 나눴다가 3으로 곱하면 해당 칸의 시작 인덱스를 구할 수 있다. 이걸 이용하면 좀 더 쉽게 구현할 수 있다. 물론 이는 0부터 시작해서 8로 끝나는 인덱스를 이용할 때 활용 가능하다.#include #include #include using namespace std;#define SIZE 9int board[SIZE][SIZE];void input() { for (int y = 0; y > c; board[y][x] = c - '0'; } }}pair findStart(int y, int x) { y /= 3; x ..

이 문제는 위상 정렬, 우선순위 큐를 이용해서 풀었다. N개의 문제는 모두 풀어야 하고, 먼저 푸는 것이 좋은 문제는 먼저 풀고, 가능하면 쉬운 문제부터 푸는 3개의 요구사항이 존재하는 문제이다. 일단 먼저 푸는 것이 좋은 문제는 먼저 풀어야 하므로 위상 정렬을 사용해야 한다. 여기서 걸리는 것은 가능하면 쉬운 문제부터 푸는 것인데, 이 경우는 우선순위 큐로 작은 숫자부터 뽑아내도록 하여 문제를 쉽게 해결할 수 있었다.#include #include #include #include #include using namespace std;#define MAX 32000vector edges[MAX + 1];int N, M;int incoming[MAX + 1];void input() { cin >> N >> ..

이 문제는 비트마스킹, 다이나믹 프로그래밍을 이용해서 풀었다. 이 문제는 일단 계단 수를 만드는 로직을 만들고, 거기에 숫자의 여부를 포함하는 비트 필드를 추가하는 방식으로 구현하는 게 훨씬 간단하다.또한 필드가 어떻게 구성될지는 돌릴때마다 다르므로, 바텀업 방식보다는 탑다운 방식으로 구현하는 것이 좀 더 간단하다. dp[i][j][k] : i (1 와 같이 설정하여 문제를 풀 수 있었다.dp배열의 크기는 최대 100 * 10 * 1024로 구성되어 약 100만이므로 충분히 2초 안에 풀 수 있다.#include #include #include #include using namespace std;#define MOD 1000000000int N;int dp[101][10][1024];int solve(i..

이 문제는 dfs, 위상 정렬을 이용해서 풀었다. 위상 정렬과 더불어 방향 그래프에서의 사이클 판정을 할 수 있으면 쉽게 풀리는 문제였다. 방향 그래프에서는 dfs 변형을 통해 사이클 판정을 할 수 있고, 무방향 그래프에서는 유니온 파인드를 이용해서 사이클 판정을 할 수 있다. 방향 그래프에서 유니온 파인드를 써보면 제대로 답이 나오지 않는다. 위상 정렬은 원래 dfs를 이용해서 푸는 방식을 선호했는데, 요구 사항이 복잡해지는 문제를 잘 해결하지 못하는 경우가 많았다. 그러나 incoming 카운트를 세어서 queue에 넣어 위상정렬하는 방식은 문제 요구 사항이 추가되어도 변형이 쉬운 편이고, 구현도 직관적이다. 이 문제에서는 후자의 방식으로 풀 수 있었다.#include #include #include..

이 문제는 다이나믹 프로그래밍으로 풀었다. 문제의 시간 제한이 0.5초이므로 약 5,000만번의 연산 이하로 알고리즘을 짜야 한다. 수열의 크기 N이 최대 2,000이므로 2,000 * 2,000 의 배열을 만들 수 있고, 400만 정도의 연산으로 dp배열을 모두 채울 수 있다. 따라서 다이나믹 프로그래밍으로 문제를 해결할 수 있다. dp[i][j] : 구간 [i, j] 의 팰린드롬 여부 저장으로 정했고, 구간의 길이에 따라 연산을 다르게 하였다. 구간의 길이가 1인 경우, 즉 start와 end가 같을 경우에는 당연히 팰린드롬이므로 true를 저장한다.구간의 길이가 2인 경우에는 두 숫자가 서로 같을 경우 true를 저장한다.구간의 길이가 3 이상인 경우에는, start = i + 1, end = j ..