재원블로그 재원블로그

이 문제는 위상 정렬, 우선순위 큐를 이용해서 풀었다. 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..

이 문제는 세그먼트 트리를 이용해서 풀었다. 값을 저장하는 쪽에는 모두 long long 을 써줘야 풀린다. 세그먼트 트리를 구현할 수만 있으면 풀리는 기초 문제였다. 몇 가지 주의할 점이 있는데, 첫번째로는 update를 할 때 차이를 더해줘야 하므로 c - arr[b]를 한 값을 update의 인자로 던져줘야 한다. 이 때문에 update 전에 입력 배열인 arr[b] = c를 해줘야 한다. 이거 안해줘서 계속 틀렸었다. 두번째는 update의 dif 또한 long long으로 선언해야한다는 것이다. 값이 int 자료형을 가뿐히 뛰어넘을 수 있기 때문이다. 로직은 단순하나 자료형으로 정답률을 낮춘 문제였다. #include #include #include #include #include using n..