문제 백준 2881번 풀이 나무가 존재하는 좌표를 XY좌표 나누어 관리하면 이분 탐색을 사용하여 log 복잡도로 빠르게 구할 수 있습니다. 꼭짓점에 걸쳐서 겹치는 좌표는 map을 사용하면 빠르게 빼줄 수 있습니다. 소스코드 #include using namespace std; unordered_map xAxis, yAxis; unordered_map mp; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int p; cin >> p; while (p--) { int x, y; cin >> x >> y; xAxis[x].push_back(y); yAxis[y].push_back(x); mp[x][y] = ..

문제 BOJ 1396번 풀이 쿼리가 하나 있다고 가정하면 아래와 같이 풀 수 있습니다. * mid보다 작거나 같은 간선들만 합쳐줍니다. (Union Find) * (쿼리) 정점 u와 v의 루트 노드가 같으면, right를 mid로 두고 그렇지 않으면 left를 mid + 1로 만들어준 뒤 계속 이분 탐색을 돌립니다. - 가중치(고유값)이 mid 이하인 간선을 이용해 정점 u, v를 포함하는 MST를 구성할 수 있냐 는 결정 문제로 볼 수 있습니다. 위와 같은 이분 탐색을 사용하면 간선을 이분 탐색하는데 $ O(log M) $, mid보다 작거나 같은 간선을 합치는데(MST를 만드는데) 시간이 $ O(M logN) $ 이고, 쿼리가 총 $ Q $개 있으니 총 시간 복잡도는 $ O (QM log N log ..

문제 BOJ 6549번 풀이 히스토그램 문제에 스택과 세그먼트 트리를 사용한 풀이가 있는데, 세그먼트 트리를 사용하여 풀어보겠습니다. 위와 같은 히스토그램이 있습니다. 아래와 같은 분할 정복을 사용하여 문제를 풀어보겠습니다. * 구간 [left, right]를 정복하고 있을 때, - 해당 구간에서 최소 높이를 h라고 두고, 높이가 h인 직사각형의 인덱스를 i라고 하겠습니다. - (right - left + 1) * h가 답이 될 수 있습니다. - 그리고 구간 [left, i - 1]과 [i + 1, right]에서 다시 분할 정복을 해나가면 됩니다. 테스트케이스를 예시로 설명해보겠습니다. [1, 7]을 정복하고 있을 때 2번째 직사각형의 높이가 1로 가장 작으니(최솟값이 여러개 있으면 아무거나 선택해도 ..

문제 백준 14428번 풀이 전형적인 세그먼트 트리를 구현하는 문제입니다. left ~ right의 대푯값을 left ~ right에서 가장 작은 값의 인덱스로 놓아주고 갱신해주면 됩니다. 소스코드 #include using namespace std; int arr[100001], seg[400001]; int init(int node, int start, int end) { if (start == end) return seg[node] = start; int mid = start + end >> 1; int a = init(node * 2, start, mid), b = init(node * 2 + 1, mid + 1, end); if (arr[a] == arr[b]) return seg[node] =..

문제 백준 9997번 풀이 모든 경우의 수를 고려하더라도 시간 복잡도가 $ O(2^N) $ 이므로 시간 내에 해결할 수 있습니다. 그러나, 비트 연산자를 이용해서 탐색하는 경우 시간 복잡도가 $ O(N 2^N) $ 이므로 TLE가 나기 때문에, dfs를 구현하여 풀어야 됩니다. a부터 z를 사용하였는지 체크하는 것은 OR 비트 연산을 사용하여 빠르게 처리할 수 있습니다. 소스코드 #include using namespace std; typedef long long ll; int n; vector vec; int solve(int sz, int vis) { if (sz == n) { if (vis == (1 > n; for (int i = 0; i > s..

문제 백준 14462번 풀이 dp[l][r] = 왼쪽 목초지를 l까지, 오른쪽 목초지를 r까지 봤을 때의 최대 개수로 점화식을 세우겠습니다. dp table을 채우는 방법을 생각해보겠습니다. l과 r을 모두 방문하면서 dp[l][r]을 구성할 때 dp[l - 1][r] 또는 dp[l][r - 1]이 그대로 오는 경우가 답이 될 수 있습니다. 또는, 횡단보도를 놓을 수 있는 경우가 있습니다. ($ | left[l] - right[r] | n; for (int i = 1; i > l[i]; for (int i = 1; i > r[i]; for (int i = 1; i