본문 바로가기

알고리즘 관련

BOJ)2150 Strongly Connected Component 문제: icpc.me/2150 SCC를 구하는 기본 문제이다. 출력을 SCC가 속한 가장 작은 정점의 정점 번호 순으로 출력해야 하므로 정렬이 필요하다. 코사라주 알고리즘을 통하여 구현하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include #include #define MAX_V 10000using namespace std;int v, e, visited[MAX_V + 1], x, y, r;vector scc;vector vt;vector rvt;stack st;bo.. 더보기
BOJ)3176 도로 네트워크 문제: icpc.me/3176 N개의 도시와 그 도시를 연결하는 N-1개의 도로 네트워크가 있을 때 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하는 문제이다. 우리는 모든 도시 쌍에는 그 도시를 연결하는 유일한 경로가 있다는데에서 주어진 그래프가 트리임을 유추할 수 있다. 우리는 문제를 해결하기 위하여 LCA를 이용할 것이다. 우리는 LCA를 구할 때 두 도시의 2^i번째 부모를 저장한다. 이 때 우리는 2^i번째 부모를 저장할 뿐만 아니라 x번째 정점 기준으로 2^i번째 부모까지의 모든 간선중에 최솟값과 최댓값을 같이 저장할 수 있다. 이를 이용하여 쿼리를 처리하면 문제를 해결할 수 있다. 1234567891011121314151617181920212223242.. 더보기
BOJ)11983 Radio Contact 문제: icpc.me/11983 파머존과 소가 움직이는 경로가 주어질 때 파머존만 움직이거나 소만 움직이거나 둘이 동시에 움직일수 있다. 이동 후 둘의 거리의 제곱에 비례하게 라디오의 에너지가 소모될 때 파머존과 소가 목적지에 도착했을 때 소모된 라디오 에너지의 최솟값을 출력하는 문제이다. 우리는 이 문제를 다이나믹 프로그래밍을 통하여 해결할 수 있다. dp[x][y]의 정의는 Farmer John이 X번 이동한 위치이고 소가 Y번 이동한 위치일 때까지 소모된 라디오 에너지의 최솟값이다. 점화식은 dp[x][y]=min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1])+dist(FJx ,COWy)가 되겠다. 파머존과 소가 한번도 움직이지 않았을 때는 에너지 소모가 없다고 하니 기저는 dp[.. 더보기
Topological Sort(위상 정렬) DAG에서 방향성을 거스르지 않게 정점들을 나열하는 알고리즘을 Topological sort(위상 정렬)이라 합니다. DAG란 Directed Acyclic Graph의 줄임말로 직역하자면 사이클이없는 방향(유향) 그래프 정도가 될 것입니다. DAG는 유향 그래프에서 정의되며 DAG가 되려면 Cycle이 없어야 합니다. 우리는 유향 그래프에서 한 정점에서 DFS를 실행 할 경우 DFS의 방문순서에 따라서 스패닝 트리를 얻을 수 있습니다. 우리는 이러한 트리를 DFS 스패닝 트리(DFS Spanning Tree)라고 부르며 DFS 스패닝 트리에서 간선의 특징에 따라 간선 분류를 할 수 있습니다. 1. 트리 간선-> 스패닝 트리에 포함된 간선 2. 순방향 간선-> 스패닝 트리에는 포함되지 않았지만 선조에서 .. 더보기
BOJ)1766 문제집 문제: icpc.me/1766 문제집을 푸는 순서가 주어지는데 이때 가능하면 쉬운 문제부터 풀어야 할 경우 문제를 푸는 순서를 출력하는 문제이다. 우리는 문제집을 푸는 순서가 주어질 때 topological sort를 통하여 순서를 출력할 수 있다. 하지만 가능하면 쉬운 문제를 풀어야 하니 topology가 여러개일 경우 작은 순서를 먼저 출력해줘야 한다. 이는 min heap을 통하여 해결 가능하다. 123456789101112131415161718192021222324252627282930313233#include #include #include #include #define MAX_N 32000using namespace std;int n, m, a, b, in[MAX_N + 1];vector vt.. 더보기
BOJ)2623 음악프로그램 문제: icpc.me/2623 음악프로그램의 출연 순서의 리스트가 주어졌을 때 모든 리스트를 만족시키도록 출연 순서를 출력하는 문제이다. 만약 모든 리스트를 만족할 수 없는 경우 0을 출력하면 된다. 우리는 출연 순서가 A->B->C 라면 A->B / B->C의 방향으로 간선을 연결해 준 뒤 topology를 구해줌으로서 리스트를 구할 수 있다. 이때 모든 리스트를 만족할 수 없는 경우는 사이클이 생기는 경우로서 그래프의 사이클 여부를 체크해줌으로서 확인 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include #include #define MA.. 더보기
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.. 더보기

티스토리툴바