재원블로그 재원블로그

이 문제는 백트래킹 문제이다. 시간 복잡도를 조금이라도 줄이려면 애초에 백트래킹 탐색을 할 때 사전식으로 앞서도록 탐색하게 만들면 된다. 어떤 좌표 (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 ..

이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 트리의 정점 개수는 최대 100만이므로 O(N log N) 이하 알고리즘을 만들어야 한다. 먼저 각 상태를 정의했다.어떤 한 노드를 골랐을 때, 그 노드가 얼리 어답터인 경우에는 주변부의 얼리 어답터 여부는 중요하지 않다.그러나 그 노드가 얼리 어답터가 아닐 경우에는 반드시 주변부 모두가 얼리 어답터야 한다. 이를 점화식으로 정의할 수 있었는데, 다음과 같다.dp[i][0] : 내가 얼리 어답터가 아님 -> sum(dp[next][1])dp[i][1] : 내가 얼리 어답터임 -> sum(min(dp[next][0], dp[next][1])) 이 둘을 정의한 순간 문제는 거의 풀린다. 최악의 경우에도 100만 * 2 배열을 모두 채우면 되므로 1초 안에 충..

이 문제는 세그먼트 트리를 이용해서 풀었다. 시간 제한이 0.7초이므로 약 7,000만번의 연산 안으로 문제를 해결해야 한다. 특정 구간에서의 직사각형 넓이의 최댓값을 구하는 문제로, 세그먼트 트리가 떠올랐다. 처음에는 단순히 세그먼트 트리에 특정 구간의 직사각형 넓이 최댓값을 바로 집어넣었다. 그러나 이런식으로는 풀리지 않는데, 절반씩 구간이 잘리는 형태에서 왼쪽과 오른쪽을 부분적으로 포함하는 범위에서 최댓값이 존재할 수 있기 때문이다. 그래서 세그먼트 트리에는 특정 구간에서의 최소 높이를 가진 인덱스를 저장하고, 이 인덱스로 좌우를 나누는 것이 정답을 맞출 수 있는 포인트이다. #include #include #include #include #include #include using namespace..

이 문제는 세그먼트 트리를 이용하는 문제이다. 이전에 구간 합 구하기 문제의 경우 update 함수를 변경하는 숫자의 차이를 더해서 구했다. 그러나 구간 곱의 경우 한번 0으로 바뀌면 다른 수로 바꿀 수 없는 문제가 발생했다. update 함수를 init과 거의 동일하게 구현함으로써 이 문제를 해결할 수 있었다. #include #include #include #include #include #include using namespace std; #define MAX 1000000 #define MOD 1000000007 typedef long long LL; int N, M, K; int arr[MAX + 1]; LL segment[MAX * 4 + 1]; LL init(int start, int end..