Problem Solving/Algorithm12 SPFA Optimization Techniques Shortest Path Faster Algorithm(SPFA) 알고리즘이 무엇인지 궁금하다면 이 게시글을 참고하자. 본 글에서는 SPFA 최적화 기법에 대해서만 서술하겠다. 1. Small Label First (SLF) 큐(Queue)에 최단 거리를 갱신할 수 있는 점(v)를 삽입할 때에, 큐의 가장 앞 부분에 위치한 정점(u)과 최단 거리를 비교한다. 만약 시작점으로부터 u에 이르는 거리보다 v에 이르는 거리가 더 짧다면, 큐의 가장 앞 부분에 v를 삽입하면 된다. 아래의 코드는 BOJ 1753번에 위 방법을 적용한 것이다. 2. Large Label Last (LLL) 큐(Queue)에 최단 거리를 갱신할 수 있는 점(v)를 삽입할 때에, 시작점으로부터 큐에 들어가 있는 정점들에 이르는 최단 거.. 2019. 10. 18. Vertex Cover, Independent Set Vertex Cover : 그래프 G=(V,E)의 정점 집합 중 어떤 부분집합 C를 택하였을 때에, 그래프 상에 존재하는 모든 간선이 C에 속하는 정점과 인접하다면 C를 G의 Vertex Cover라고 한다. 이 때 가능한 C 중 최소 크기의 C를 Minimum Vertex Cover(최소 정점 덮개)라고 한다. Independent Set : 그래프 G=(V,E)의 정점 집합 중 어떤 부분집합 I를 택하였을 때에, I의 모든 원소가 서로 인접하지 않다면(두 정점을 연결하는 간선이 존재하지 않는다면) 해당 집합 I를 Independent Set이라고 한다. 이 때 가능한 I 중 최대 크기의 I를 Maximum Independent Set(최대 안정 집합)이라고 부른다. 이와 연관하여 알아두면 좋은 사실들.. 2018. 7. 20. 힙(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. 이전 1 2 3 다음
