Problem Solving102 힙(Heap)을 이용한 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 방향이 있는 가중치 그래프에서의 단일 시작점 최단 경로 알고리즘이다. 단, 조건으로 모든 간선의 가중치가 음이 아닌 수여야 한다. 다익스트라 알고리즘은 해 집합(S)에서 해가 아닌 집합(T)로 향하는 경로 중, 가장 짧은 경로를 매번 선택한다. 아래 그림을 보자. 단일 시작점을 a라 하고, 위에서 말한 정의에 따라 표현했다.특정 시점에서의 가장 짧은 경로를 a→u-v라 하자. 즉, a에서 u까지 가는 경로에 간선 u-v를 추가하는 경로이다. 이 때, v가 S에 포함되는 경우가 2가지 경우가 있다. 1) a에서 S의 원소 u까지 가는 최단 경로에다가 u-v를 잇는 간선을 추가해서 v가 S의 원소가 되는 경우 2) a에서 T의 원소 u'까지 가는 최단 경로에다가 u-v를 잇는 간선을 추.. 2017. 2. 23. Shortest Path Faster Algorithm(SPFA) 방향성 가중치 그래프 G = (V, E)에서 단일 시작점 s가 있을 때, Shortest Path Faster Algorithm(SPFA)는 s에서 출발하여 다른 정점 v에 이르는 최단경로를 찾아낸다. Pseudo Code를 보면 다음과 같다. 초기에 다른 정점에 이르는 최단거리는 다 무한대로 설정하고 시작점에 이르는 최단거리는 0으로 정한다. Queue에 시작점을 넣고 Queue가 비어있지 않을 동안 반복한다. Queue의 맨 앞에서 원소 하나를 꺼내서 그 정점을 u라고 하자. u에서 뻗어나가는 간선들을 훑어보며, 간선이 가리키는 점 v의 최단거리를 갱신할 수 있으면 갱신해준다. 갱신하고 나서, Queue에 v가 없다면 Queue에 삽입한다. Queue에 어떤 정점 x가 있는지, 없는지의 여부는 정점 .. 2017. 2. 16. Parametric Search (파라메트릭 서치) 가능한 해 구간에 대해서 이분탐색을 하는 방법을 'Parametric Search'라고 한다. 흔히 가능한 해의 최솟값이나 최댓값을 구하라는 문제에서 사용할 수 있는 기법이다. Optimization Problem을 Binary Search + YES/NO Problem으로 바꾸어 푸는 방법이다. Parametric Search를 사용하기 위해서는 몇 가지 조건이 있다. 1. 가능한 해의 영역이 연속적이어야 한다. 예시로 가능한 해의 최솟값을 찾는 문제에서 설명하면 가능한 해 구간 [ L , R ]에서 우리가 정한 답 X를 기준으로 2가지 경우가 있다. 1) X가 해를 만족할 때, [ X , R ]에 대해서도 모두 해를 만족해야 한다. 따라서 X의 탐색 범위를 해 구간 [ L , R ]에서 [ L , X.. 2017. 2. 14. 친구 수 세기 - USACO_2014MAR_FRIENDS 문제 링크(koitp.org/problem/USACO_2014MAR_FRIENDS/) 2017. 2. 12. 가장 거리가 먼 두 점 - FARTHEST_PAIR 문제 링크(koitp.org/problem/FARTHEST_PAIR/)답이 되는 두 점의 쌍은 컨벡스헐 위에 존재한다.컨벡스헐 위의 점들에 대해서 로테이팅 캘리퍼스로 답을 탐색한다.로테이팅 캘리퍼스에서 판단 기준은 유클리드 거리가 아닌 CCW로 판단한다.구간의 양 끝이 [A, B]라고 한다면,A번째 점과 A+1번째 점을 잇는 선분과, B번째 점과 B+1번째 점을 잇는 선분의 외적을 계산해 방향이왼쪽으로 계속 꺽이다가 오른쪽으로 꺽이게 되는 순간 멈추면 된다. 2017. 2. 9. 이전 1 2 3 4 5 6 7 ··· 21 다음
