본문 바로가기

분류 전체보기

BOJ)9470 Strahler 순서 문제: icpc.me/9470 indegree가 0인 노드들의 순서가 1인데 어떤 노드의 indegree와 연결된 노드 중 순서가 가장 큰 값을 i라고할 때 i가 1개 들어오면 해당 노드의 순서는 i 2개 이상 들어온다면 해당 노드의 순서는 i+1이 된다. 우리는 indegree의 정보를 이용하여 위상정렬을 실행하는데 이때 들어오는 indegree의 최댓값과 개수만 count해주어 값을 갱신해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include #include using namespace std;int k, m, p,.. 더보기
BOJ)13711 LCS4 문제: icpc.me/13711 LCS의 크기를 구하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 LCS를 구할 수 있다. 하지만 LCS4 문제는 N이 10만이기 때문에 다른 방법을 생각해보아야 한다. 단순히 N이 10만에서 최장 공통 부분 수열을 구하라고 한다면 무척 어려운 문제가 되겠지만 다행히 조건이 더 주어진다. 1~N까지 정수는 두 수열 A,B에서 전부 한번 씩 주어진다는 것이다. 우리는 수열 A에서 입력을 받은 후 입력 받은 수의 인덱스로 A[x]의 들어온 순서를 삽입하는 방식으로 A수열을 정의 해준 뒤 A[B[i]]의 LIS를 구함으로서 최장 공통 부분 수열의 길이를 구할 수 있다. 이때 N이 10만이기 때문에 N^2 DP로 LIS를 구하는 방법은 안되고 NlogN 이분 탐색의 방법으로.. 더보기
BOJ)1183 약속 문제: icpc.me/1183 도착하는 시간 A 배열과 기다리는 시간 S배열이 주어질 때 SUM[ abs(S[i]-A[i]+T) ] 을 최소로 만드는 T의 개수를 세는 것이다. 어짜피 s배열과 a배열 둘다 입력으로 주어지는 수니 수식의 간편화를 위하여 X로 표시할 수 있다 결국 우리는 SUM[ abs(X[i]+T) ]를 구하면 되는 것이다. X[i]들을 전부 정렬한 후 어떤 수 T를 어떤 수 -X[i]로 잡고 값을 정할 때 T를 -X[i]에서 증가 시킬 경우 (X[i]보다 큰수들-X[i]보다 작은수들)만큼 증가하며 -X[I]에서 감소 시킬 경우 (X[i]보다 작은수들-X[i]보다 큰수들)만큼 증가하게 된다. 결국 이를 이용하여 생각하면 정렬을 했을 때 중앙값의 음수부호를 취해준 -X[i]가 합을 최소로 .. 더보기
SCC(Strongly Connected Component) 방향 그래프에서 어떤 그룹 X에 있는 임의의 두 정점 A,B에 대해서 항상 A->B로 가는 경로가 존재한다면 그 그룹을 SCC(Strongly Connected Component)라 칭합니다. 더 정확하게 정의하자면 SCC가 되는 그룹은 항상 최대로 정의되기 때문에 다음과 같은 조건을 만족해야 합니다. 1. 같은 SCC 내의 임의의 두 정점 A,B사이의 경로가 항상 존재한다.2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다. (SCC 끼리는 사이클이 존재하지 않는다.) SCC를 직역하면 "강한 연결 요소" 라는 뜻이됩니다. 즉 SCC는 집합 내에서 정점들이 서로 왕복 가능한 최대 크기의 집합입니다. 다음과 같은 그래프에.. 더보기
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.. 더보기

티스토리툴바