dh_0e

발전소 (백준 1102번) 비트필드를 이용한 dp 문제로 n이 16 이하의 자연수이기 때문에 $O(2^{n}*n^{2})$으로 해도 최대 16,777,216이 나오기 때문에, 시간초과가 나오지 않는다. 풀이 과정 dp 점화식을 dp[i][j] = 'i개의 발전소가 작동할 때, 발전소 상태가 j인 경우 드는 최소 비용' 으로 잡는다. 이때, j에 들어가는 값은 비트필드로 각 비트는 n(n-1)(n-2)...54321와 같이 내림차순으로 n~1번 발전소의 고장 여부를 나타낸다.(n이 5라고 가정했을 때, j가 10110이면 5, 3, 2번 발전소가 켜져있다는 뜻) 초기 dp 배열은 -1로 초기화하고, 작동중인 발전소들을 나타내는 값(: bit)을 구해서 dp[작동중인 발전소 수(: cnt)][bit]를 0..

LCA와 쿼리 2 (백준 15480번) 어떤 트리의 root를 계속해서 바꾸면서 LCA를 구하는 쿼리를 해결하는 문제로, LCA를 최대 100,'000번 구성하도록 코드를 짜면 무조건적으로 시간초과가 나온다. 수학적 패턴이나 조건 분기들을 따져야 하는 문제 같아서 계속 고민해 봤지만 발상이 쉽지 않았다. 풀이 과정 LCA(r, a)와 LCA(r, b), LCA(a, b)의 값을 비교하여 답을 쉽게 도출할 수 있다.LCA(r, a)와 LCA(r, b)가 같다면 LCA(a, b)가 root를 r로 바꾼 트리의 최소 공통 조상이 된다.이 경우엔, a부터 b로의 경로 중에 r이 없다는 뜻으로 root를 r로 바꾸어도 LCA는 그대로 LCA(a, b)가 된다.그렇지 않다면, LCA(r, a)와 LCA(r, b) ..

트리와 쿼리 2 (백준 13511번) 최소 공통 조상(LCA) 문제로 희소 배열, Binary Lifting을 사용하여 LCA를 $O(logn)$만에 구해야 한다. 풀이 과정 문제 설계는 여타 LCA 문제를 구현하듯이 하되, parent 배열에 비용, 정점 번호를 함께 저장한 뒤, LCA 함수를 약간 수정하고 문제 형식에 맞게 출력하면 된다. LCA 함수를 만들 때, u, v 정점에서 최소 공통 조상까지의 거리를 각각 cost에 더해주면서 합을 구해주고, 최소 공통 조상의 정점 번호를 함께 pair로 반환해준다. 반환한 값을 바탕으로 (1 u v) 형식의 쿼리는 그냥 cost 값을 출력해주면 되며, (2 u v k) 형식의 쿼리는 약간의 작업이 필요하다. 최소 공통 조상까지의 정점 갯수를 각각 LCA_u..

행성 터널 (백준 2887번) MST(Minimum Spanning Tree) 알고리즘 문제로 좌표상이 3차원이기 때문에 각 노드별로 간선을 만들어 풀면 $O(N^2)$으로 시간초과가 나온다. 풀이 과정 각 행성을 연결하는 터널(간선)을 만들 때 드는 비용이 $min(\lvert x_a - x_b \rvert,\; \lvert y_a - y_b \rvert,\; \lvert z_a - z_b \rvert)$ 이기 때문에, x, y, z를 기준으로 각각 정렬을 하여 인접한 행성들 간의 간선들만 만들어준다. 각 축을 기준으로 행성당 6개의 간선이 나오며 이 간선들의 비용을 오름차순으로 정렬하여 크루스칼 알고리즘으로 최소 스패닝 트리를 완성하는 총 비용을 구하면 된다. 본인은 priority queue를 활용..

아이돌 (백준 3648번) 2-SAT 문제에 상근(1번 참가자)이가 항상 합격할 수 있는 경우가 있는지를 찾는 문제. 풀이 과정상근이가 포함된 SCC 집합을 true로 만들고 각 SCC 집합 관계가 맞는지 확인하는 방식은 너무 복잡해짐.상근이가 항상 합격해야 한다는 심사위원의 평가를 하나 만들면 된다. vec[ch(-1)].push_back(1) → (1, 1) 의 평가를 하나 추가하여 1번 참가자가 무조건 합격하게끔 만드는 식으로 한정지어줌#include#include#include#include#includeusing namespace std;stack st;vector vec[2'001];bool vi[2'001];int p[2'001];int id = 0, scc = 0;auto ch = [](i..

2-SAT - 4 (백준 11281번) 2-SAT-3 에서 식을 true로 만들 수 있는 변수들의 값을 출력하면 되는 문제. 풀이 과정2-SAT 문제에서 변수 값을 정할 때 위상 정렬(Topological Sort) 순서를 거꾸로 따라감그래프에서 A → B 라는 건, A를 결정해야 B를 알 수 있다는 뜻이며 이게 위상 정렬 순서가 된다(A가 B보다 앞에 옴).근데 만약 우리가 A를 참(True)으로 정했는데, 이게 어찌어찌 흘러가서 A ⇒ ... ⇒ ¬A 라는 모순을 만들면 식이 성립할 수 없다.이런 모순을 피하는 가장 안전한 방법은, 함의 관계의 맨 끝, 즉 종착지부터 값을 정하는 것. 종착지는 위상 정렬 순서에서 가장 나중에 오므로, 위상 정렬의 역순으로 거슬러 올라가면서 값을 결정한다. 이렇게 하..