본문 바로가기

분류 전체보기

LCA(Lowest Common Ancestor) 1개 이상의 노드로 구성 된 사이클이 없는 그래프를 트리라고 합니다. 우리는 트리에서 정의되는 LCA(Lowest Common Ancestor)에 대해서 얘기해 보려 합니다. LCA를 직역하면 최소 공통 조상(?) 정도의 뜻으로 해석되며 두 정점에서 (자신을 포함한)조상들을 거슬러 올라갈 때 처음으로 공통되게 만나는 정점을 지칭합니다. 예를 들기 위해 다음과 같은 트리가 존재한다고 합시다. 이 트리에서 6번 정점과 10번 정점의 LCA를 구하면 다음과 같이 2번 정점이 6번 정점과 10번 정점의 LCA가 됩니다. 이번에는 7번 정점과 10번 정점의 LCA를 구해보겠습니다. 다음과 같이 1번 정점이 7번 정점과 10번 정점의 LCA가 됩니다. 자, 이제 어느정도 LCA의 정의에 대한 감이 오시나요? 마지막.. 더보기
BOJ)11438 LCA 2 문제:icpc.me/11438 이 문제는 LCA (BOJ 11437) 의 풀이도 포함한다. 루트의 번호가 1번인 N개의 정점으로 이루어진 트리가 존재할 때 두 노드의 쌍 M이 주어질 때 두 노드의 LCA를 구하는 문제이다. 여기서 LCA(Lowest Common Ancestor)란 직역하면 최소 공통 조상(?) 이다. 즉 트리의 두 노드가 주어졌을 때 서로의 조상을 거슬러올라갔을 때 가장 먼저 만나는 정점이 LCA가 된다. LCA를 구하는 방법으로 두 노드의 높이(깊이)를 맞춘후에 한칸씩 올라가며 조상이 같아질 때까지 비교하는 방법이 있다. 하지만 이방법은 한번의 쿼리를 처리할 때 O(N)의 시간복잡도를 가지므로 LCA 2문제 같이 M과 N이 10만이면 O(N*M)으로 TLE를 피하기 힘들것이다. 그래서.. 더보기
BOJ)4386 Freckles 문제: icpc.me/4386 N개의 점들이 주어지고 각 점들사이의 가중치는 거리와 비례한다 할 때 MST를 구성하는 문제다. N이 100밖에 되지 않으니 N^2의 방법으로 간선들을 구해준 후 크루스칼을 돌려주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include using namespace std;int n, par[101], it;double r;pair p[101];priority_queue pq;double calc(pair cx, pair cy) { return sqrt((cx.first - cy.first)*(cx.first - cy.first) + (cx.se.. 더보기
BOJ)4343 Arctic Network 문제: icpc.me/4343 P개의 전초기지가 있을 때 S개의 전초기지는 위성채널과 연결되어 있을 때 전초기지 전체가 위성채널과 연결되게 하는데 필요한 마지막 최소 연결비용을 출력하는것이다. 연결비용은 두 전초기지의 거리와 같다. 우리는 P-S개의 간선을 연결하는 MST를 구현하여 마지막으로 연결되는 간선의 가중치를 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include #include using namespace std;int t, n, m, x, y, par[501], c;pair p[501];double r;double calc(pa.. 더보기
BOJ)13325 이진 트리 문제: icpc.me/13325 포화 이진트리의 높이 K가 주어 질 때 에지의 가중치를 증가시켜서 루트에서부터 리프까지의 거리를 모두 같게 만드는 문제이다. 아래에서 부터 부모가 같은 두노드의 엣지의 가중치 차이를 바텀업으로 중첩시켜서 증가시켜주면 된다. 12345678910111213141516171819#include #include using namespace std;int n, a[1 더보기
BOJ)11975 Build Gates 문제: icpc.me/11975 펜스를 동서남북으로 치려고 할 때 펜스로 인하여 닫힌 구간은 나가야 할 문이 필요하다고 할 때 문의 최소 개수를 출력하는 문제이다. 문제를 다시 해석하자면 그래프를 그린 뒤 완전히 닫혀있는 구간의 개수를 세는것이다. 즉 평면의 개수를 찾는 문제인데, 선을 그어서 생긴 그래프이므로 평면그래프가 되니 V-E+F=2라는 공식을 이용하여 F=2-V+E로 평면의 개수를 구할 수 있다. 이때 그래프 전체가 평면의 개수에 포함되기 때문에 F-1을 출력해주면 된다. Vertex와 Edge는 중복이 되면 안되므로 set을 통하여 관리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #i.. 더보기
BOJ)11974 Subsequences Summing to Sevens 문제: icpc.me/11974 N마리의 소가 각각의 고유 ID를 가지고 있을 때 연속된 소의 고유 ID의 합이 7의 배수인 구간의 길이를 출력하는 문제이다. 소를 입력 받은 후에 소의 partial sum을 저장한 뒤 partial sum을 7로 나눈 나머지를 저장한다면 해당 값이 같은 가장 긴 구간이 답이될 것이다. 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;typedef long long ll;ll n, a[50000], p[50000], r;int main() { scanf("%lld", &n); for (int i = 0; i 더보기
BOJ)11973 Angry Cows 문제: icpc.me/11973 Angry Cow를 x위치에 던지면 [x-R,x+R]위치의 건초가 모두 파괴된다. N개의 건초더미의 위치가 주어질 때 K마리의 Angry Cow를 던져서 모든 건초를 파괴하려할 때 R의 최솟값을 출력하는 문제이다. 우리는 건초더미들의 위치를 구간으로 생각하여 한 Angry Cow가 구간 2*R을 파괴할 때 K마리의 Angry Cow가 전체 구간을 다 파괴할 수 있는지를 확인하여 R의 최솟값을 구해야한다. R의 최솟값은 이분탐색을 통하여 구할 수 있다. 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;typedef long long ll;ll n, k, .. 더보기
BOJ)10216 Count Circle Groups 문제: icpc.me/10216 N개의 진영이 주어 질 때 각 진영이 통신영역이 닿거나 겹치는 부분이 있으면 서로 통신이 가능하다. 그리고 직접적으로 통신이 불가능 하더라도 중간에 몇개의 통신을 거쳐서 통신이 가능하다면 i와 j는 통신이 가능하다고 본다. 통신이 서로 가능한 진영들을 그룹으로 묶을 때 그룹의 수를 출력하는 문제이다. 우리는 a와b가 통신이 가능하고 b와c가 통신이 가능하면 a와c가 통신이 가능한 그룹이 된다는 사실을 가지고 disjoint set을 통하여 문제를 해결할 수 있다. N이 3000밖에 되지 않으므로 N^2의 방법으로 각 진영들을 비교하여 같은 그룹이 아닌 그룹들중에서 통신영역이 겹치는 두 그룹을 union 시켜주면서 시켜줄때마다 그룹의 수를 하나씩 차감시키는 방법으로 답을 구.. 더보기
BOJ)13913 숨바꼭질4 문제:icpc.me/13913 X의 위치에서 1초후에 X+1,X-1,2*X의 위치로 이동가능할 때 K로 가는데 걸리는 가장 빠른시간과 경로를 출력하는 문제이다. 우리는 각 좌표를 정점으로 생각하여 다익스트라를 돌린다면 가장 빠른시간을 구할 수 있다. 경로를 출력하는것은 백트래킹을 해야하는데 좌표N에 대한 최단경로가 갱신되는 순간에 N을 부른 위치를 기록해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include using namespace std;int dp[250000], n, k, back[250000];stack st;int main().. 더보기

티스토리툴바