본문 바로가기

분류 전체보기

다익스트라 알고리즘(Dijkstra's Algorithm) 다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘 입니다. 여기서 말하는 1:N이란 한 정점 V를 기준으로 V와 같은 컴포넌트에 속해있는 모든 정점들과의 최단거리를 계산한다는 의미입니다. 보통 가중치가 없는 그래프에서의 1:N 최단거리는 BFS (O(V+E))를 통하여 계산해주고, 가중치가 있는 그래프에서의 N:N 최단거리는 플로이드 워셜(O(N^3))으로 계산해주는게 일반적입니다. 단 다익스트라를 포함한 위에서 제시한 알고리즘들은 가중치가 음수 일때는 사용하지 못합니다. 가중치가 음수일 경우 벨만포드 알고리즘(O(VE))이나 SPFA(O(VE))를 통하여 최단거리를 구해주어야 합니다. 그렇다면 다익스트라는 어떤 방식으로 1:N 최단거리를 구해낼까요? 일단 다익스트라.. 더보기
BOJ)2261 가장 가까운 두 점 문제:icpc.me/2261 가장 가까운 두점을 N^2보다 적은 시간에 구해야하는 문제이다. 우선 점들을 x좌표 기준으로 스위핑해보자. 이후 x좌표가 증가하는 순서대로 점들을 볼건데 이미 본 점들은 y좌표 기준으로 정렬이 되도록 set에 삽입해준 후 지금까지의 최단거리가 d라면 현재 볼 점의 x좌표가 d이상 차이나거나 y좌표가 d이상 차이나는 점들을 제외하고 비교해준다. x좌표가 정렬 된 순서로 보기 때문에 포인트를 잡아서 기록해두면 x좌표가 차이나는 점들은 set에서 제거해줄 수 있고 y좌표는 lower_bound와 upper_bound를 통하여 탐색 지점을 정해놓고 비교해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373.. 더보기
BOJ)5038 Flight Planning 문제: icpc.me/5038 트리가 주어질 때 하나의 간선을 삭제하고 다시 하나의 간선은 연결하여 만든 트리의 지름이 최소가 되도록 하는 문제이다. N제한이 2500밖에 안되기 때문에 모든 간선을 다 삭제해 본 뒤 지름을 비교해보는걸 생각해볼 수 있다. 그렇다면 하나의 간선을 제거하였을 때 트리의 지름이 최소가 되도록 간선을 이어붙이려면 어떻게 붙여야할까? 바로 트리의 반지름을 이용하면 된다. 트리의 간선을 하나를 제거하면 두개의 트리가 생기게 된다. 이 때 두 트리의 반지름을 각각 구해준 뒤 반지름을 형성하는 정점들 사이에 간선을 연결하면 트리의 지름은 max(트리1의 지름,트리2의 지름,트리1의 반지름+트리2의 반지름+1)이 된다. 따라서 모든 경우에 대하여 트리의 지름을 구해준 뒤 비교하여 답을 .. 더보기
BOJ)8872 빌라봉 문제: icpc.me/8872 문제의 내용을 풀어서 설명하면 결국 포레스트가 주어졌을 때 해당 포레스트에 몇개의 간선을 추가하여 만들어진 트리의 지름의 최솟값을 구하는 문제이다. 문제의 답은 세 경우중 하나가 될 수 있는데 1.기존의 포레스트내의 트리에서의 지름중 최댓값 2-3. 포레스트 내부의 서브트리들의 반지름 중 가장큰 반지름을 가지는 서브트리에 나머지 반지름들을 길이 L로 연결하였을 때2.가장 긴 반지름 + 두번째로 긴 반지름 +L3.두번째로 긴 반지름 + 세번째로 긴 반지름 +L+L 이 세값 중 최댓값이 답이된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555.. 더보기
트리의 이심률,지름,반지름 트리에서 존재하는 한 정점 v에서의 이심률(eccentricity)이란 v가 속한 트리내의 모든 정점 u에 대해 max(dist(v,u))를 의미한다. 트리에서의 반지름은 트리내의 모든 정점 v에 대해서 이심률이 최소가 되는 v의 이심률이고 트리에서의 지름은 트리내의 모든 정점 v에 대해서 이심률이 최대가 되는 v의 이심률이다. 간단하게 정리하면 v의 이심률은 v에서 가장 먼 정점까지의 거리로 정의되며 트리의 지름은 트리 내부에서 가장 먼 두점 사이의 거리이며 트리의 반지름은 각 정점들에서의 가장 먼거리들 중 최소가 되는 거리이다. 트리의 지름을 구하는 방법은 익히 잘알려져있는 방법으로 임의의 정점에서 v에서 dfs를 통하여 이심률을 구하고 해당 이심률의 단말에 해당되는 정점 u에서 다시 dfs를 통하여.. 더보기
SPFA에서 음수 사이클을 확인하는 방법 이러한 사실을 이용하여 BOJ)11657 타임머신 문제를 spfa로 풀 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include #include #define INF 987654321using namespace std;int n, m, a, b, c;vector vt;vector v, cycle, dist;int main() { scanf("%d%d", &n, &m); vt.resize(n + 1); for (int i = 0; i dist[here] + next.second) { dist[next.first] = dist[here] + next.. 더보기
BOJ)1444 숌 언어 문제:icpc.me/1444 대문자와 소문자가 번갈아 나타나는 문장이 주어질 때 대문자와 소문자로 이루어진 최소 몇개의 단어로 문장을 만들 수 있는지를 출력하는 문제이다. 이 문제는 (대문자,소문자)로 이루어진 단어와 (소문자,대문자)로 이루어진 단어의 이분 그래프로 나타내면 최소 버텍스 커버 문제로 치환하여 해결할 수 있다. 예를들어 AaAbBa라는 단어가 있을 때 Ab라는 정점과 bB라는 정점이 연결되고 bB라는 정점과 Ba라는 정점이 연결될 것이다. 이 연결을 할 수 있게 만드는 정점의 최소수를 구하는 문제이기 때문에 최소 버텍스 커버 문제로 해결 가능한 것이다. 하지만 맨 처음 나오는 Aa라는 단어와 Ba라는 단어는 항상 선택이 강제 되어야하므로 해당 단어와 연결 된 간선들을 모두 제거해준 뒤 그.. 더보기
UVaOJ)12797 Letters 문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4662 NxN의 맵이 주어질 때 1,1에서 n,n까지의 최단거리를 구하는 문제이다. 단 제약조건이 있는데 발판으로 주어지는 알파벳중에 대문자나 소문자 하나를 정해놓고 일관성있게 밟아야 한다. 알파벳이 최대 10개밖에 없기 때문에 상태에 대하여 비트마스킹을하여 넘겨주어 BFS를 1024번만 돌려주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #incl.. 더보기
UVaOJ)11765 Component Placement 문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2865 N개의 정점이 있을 때 N개의 정점이 상단에 연결되어야 하는지 하단에 연결되어야 하는지 여부를 구해주어야 하는 문제이다. 각각 상단에 연결되었을 때와 하단에 연결되었을 때의 비용이 주어지며 반드시 상단에 연결되어야 하는 경우, 반드시 하단에 연결되어야 하는 경우, 둘다 가능한 경우가 주어진다. 이 후 M개의 정보가 주어지는데 이 정보는 x 와 y 정점이 같은 곳(상단or 하단)에 연결되지 않았을 경우 생기는 추가비용이다. 이 때 모든 정점을 연결하였을 때 최소비용을 구하는 문제이다. 이 문제를 최소컷 문제로 변형해서 푼다고 생각을 하면 하나의.. 더보기
UVaOJ)12159 Gun Fight 문제:https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3311 N개의 power가 존재하는 점이 주어지고 진영을 가르는 직선을 결정하는 두 점이 주어진다. 두 점으로 부터 진영을 갈라서 수가 적은 진영이 수가 많은 진영을 이기도록 최대한 매칭할 수 있는 수를 출력하는 문제이다. ccw를 이요하여 모든 점의 진영을 구해준 뒤 진영이 적은 쪽에서 진영이 많은 쪽으로 두 점 사이의 거리가 R이하이고 Power가 0이상이고 진영이 적은 쪽의 power가 진영이 많은쪽의 power보다 많은 두 점을 서로 매칭시켜준 뒤 최대매칭을 구해주면 된다. 123456789101112131415161718192021222324.. 더보기

티스토리툴바