강의자료/알고리즘 37

[알고리즘] 모스알고리즘(Mo's algorithm)

모스알고리즘이란? 모스 알고리즘은 업데이트가 없는 구간 쿼리들을 처리하는 알고리즘이다. 기본 아이디어는 업데이트가 없기 때문에 '앞에서 계산된 값을 최대한 활용하자'이다. 특히 조회만 하는 경우는 쿼리의 순서를 자유롭게 바꿀 수 있는 환경에서 미리 계산된 값을 다시 이용할 수 있을 것이다. 이전에 살펴 보았던 제곱근분할법(https://wondangcom.tistory.com/2721) 을 이용하여 모스알고리즘을 구현 할 수 있는데 이 알고리즘으로 해결할 수 있는 문제는 원소의 수정은 없고 구간 내에서 어떤 결과를 찾는 종류의 쿼리만 있는 문제이다. 그렇다면 기존 문제보다 활용범위가 좁은 것은 아닐까? 간혹 세그먼트 트리 등을 이용해서 해결하지 못하는 경우가 발생한다. 이러한 문제 유형은 아래에서 살펴 ..

[알고리즘] 제곱근 분할법(Sqrt Decomposition)

제곱근 분할법(Sqrt Decomposition)이란? Sqrt Decompostion 의 아이디어는 다음과 같다. 1 2 3 4 5 6 7 8 9 위와 같이 9 개의 원소가 있다면 연속적인 원소들을 하나의 묶음으로 생각한다는 것이다. 이 때 한 묶음을 √N 개로 묶는다( 따라서 Sqrt 라는 이름이 붙는다.) (1,2,3),(4,5,6),(7,8,9) 위와 같이 3개의 그룹으로 묶은 다음 각 그룹에 대푯값을 정한다. 만약 그룹의 합을 구하는 쿼리라고 하면 그룹의 합이 대푯값이 되고 쿼리가 구간의 최댓값을 구하는 쿼리라면 그룹의 최댓값이 구간의 쿼리가 된다. 이러한 제곱근 분할법은 Mo's Algorithm 의 기반이 되는 알고리즘으로 사용된다. 제곱근 분할법(Sqrt Decomposition) 구현 여..

알고리즘] 최소 절단

최소 절단 알고리즘을 알기 위해서는 절단이라고 불리는 개념을 생각해야 한다. 절단(cut)란 네트워크를 정확히 두래로 쪼개는 것을 의미한다. 문제의 입력으로 시작점 s와 종점 t 가 들어 오기 때문에 우리는 둘로 쪼개는 여러 방법 중에 한쪽에는 s에 속하고 다른쪽엔느 t에 속하도록 하는 절단만을 고려한다. 이것을 s-t절단 이라고 부르는데 이 글에서는 다른 절단에 대해서는 고려하지 않기 때문에 절단이란 s-t 절단을 가르킨다고 생각한다. 그래프 절단이란 어떤 정점 집합 S ⊆ V 에 대해서 s ∈ S 이고 t ∈ V\S 일 때 (S,V\S) 처럼 나타내며 S로부터 나가는 변의 집합을 말한다. 또한 그 용량의 합을 절단의 용량이라고 말하며 절단에 포함된 변을 모두 제거하면 s에서 t까지의 경로가 존재하지 ..

inchworm 알고리즘

inchworm 알고리즘이란? inchworm은 자벌레를 말하는데 inchworm 알고리즘은 자벌레가 기어가는 모양과 같이 선두와 마지막에 변화를 가하면서 조건을 만족하는 구간을 찾는 알고리즘이다. 머리와 꼬리가 이동하는 개념으로 투포인트와 같은 개념이다. 이 알고리즘은 프로그래밍 콘테스트에 자주 출제 되는 유형으로 다음과 같은 문제가 있다. 예제 문제(출처 POJ 3061) 각각 10000보다 작거나 같은 N개의 양의 정수(10 > n >> m; ans.clear(); for(int i=0;i> num; ans.push_back(num); } int s=0,t=0,sum=0,res=n+1; for(;;) { while(t

기하알고리즘] 회전하는 캘리퍼스

캘리퍼스란? 캘리퍼스는 작은 물건의 지름,너비 등을 측정할 때 쓰는 도구로 두개의 평형한 변 사이의 길이를 측정하는 도구이다. 회전하는 캘리퍼스(Rotating Calipers) 알고리즘이란? 회전하는 캘리퍼스 알고리즘은 실제 볼록 다각형의 지름을 재는데 사용된다. 다각형을 따라 두 직선을 한바퀴 돌리면서 두 직선에 닿는 꼭지점들 간의 거리를 구하는 알고리즘이다. 백준 10254번 고속도로 문제를 기준으로 살펴 보자 https://www.acmicpc.net/problem/10254 10254번: 고속도로 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 www...

[알고리즘]다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 출발점이 있는 곳에서 모든 정점까지의 최단거리를 찾는 알고리즘이다. 경로에 음수가 포함되면 경로를 찾을 수 없다. 알고리즘 모든 정점의 최단거리를 구할 배열 d[]를 만들고 배열에 INF 값을 채워 넣는다.(INF 는 경로의 계산에서 나올 수 없는 매우 큰 값을 의미한다.) 출발하는 정점의 위치에 0을 채워 넣는다. 방문하지 않은 경로 중 현재까지의 값중에서 가장 짧은 거리의 정점을 선택한다.(만약 이 값이 INF 라면 갈 곳이 없다는 것이므로 더이상 진행하지 않아도 된다.) 선택된 정점은 방문한 정점으로 마킹을 한다. 선택된 정점에서 갈 수 있는 모든 경로를 가 보면서 자신까지 온 거리와 다음 정점까지 갈 수 있는 거리의 합이..

[알고리즘] Floyd-Warshall(플로이드워셜) 알고리즘

1. 플로이드 워셜(Floyd-Warshall) 알고리즘 플로이드 워셜 알고리즘이란 모든 정점들간의 상호 최단거리를 구하기 위한 알고리즘이다. 시간복잡도는 O(N^3) 으로 i에서 j를 갈때 i->k->j 와 같이 모든 정점(k)를 거쳐서 i 에서 j를 가면서 가장 가까운 거리를 찾는 알고리즘이다. 기본적인 알고리즘 의사코드는 다음과 같다. 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each edge (u,v) 3 dist[u][v] ← w(u,v) // 변 (u,v)의 가중치 4 for each vertex v 5 dist[v][v] ← 0 6 for k from 1 to |V| 7 for ..

[알고리즘] 크루스칼알고리즘

크루스칼 알고리즘이란? 그래프 내의 모든 정점들을 가장 적은 비용으로 연결 하기 위해 경로를 찾을 때 사용되는 알고리즘입니다. 즉 그래프에는 노드(node)와 엣지(edge)가 있으며 엣지에는 가중치가 포함되어 있습니다. 이러한 그래프에서 모든 정점을 포함하고 사이클(Cycle)이 없는 연결선을 그렸을 때 가중치의 합이 최소가 되는 값을 구할 때 사용합니다. 크루스칼 알고리즘은 다음과 같은 단계로 구합니다. 1단계 : 각 정점 하나만을 포함하는 n개의 집합을 만듭니다. 2단계 : 모든 간선을 가중치 값을 기준으로 오름차순으로 정렬합니다. 3단계 : 가중치가 가장 작은 것 부터 검사하여 간선이 서로소(disjoint)인 두 집합을 연결하면 그 간선을 추가하고 연결된 두 집합을 하나의 집합으로 연결 합니다...

[알고리즘] 부분합

부분합 알고리즘이란? N명의 시험 성적을 내림차순으로 정렬해 둔 score[] 가 있다고 하면 여기서 우리는 a등에서 b등까지의 평균을 구하려고 한다. 가장 간단한 알고리즘으로는 a등부터 b등까지의 합을 구한 다음 b - a + 1 로 나누는 것이다. 하지만 이렇게 구하는 횟수가 빈번해진다고 하면 1회를 구할 때마다 최대 N번씩 반복하게 된다. 이럴 때 유용하게 사용하는 것이 부분합(Partial sum)이다. 위와 같이 psum 테이블을 미리 구해 놓는다고 하면 2번지 부터 4번지까지의 부분합을 구하려고 하면 psum[4] 는 0,1,2,3,4 의 모든 합이기 때문에 여기서 0,1 의 값을 빼면 2번지부터 4번지 까지의 부분합이 된다. 따라서 psum[4] - psum[1] 의 값이 2번지 부터 4번지..

[알고리즘] 조합탐색

조합탐색이란? - 완전 탐색 알고리즘은 대개 답을 만드는 과정을 여러개의 선택으로 나눈 뒤 재귀 호출을 이용해 각각의 선택지를 채워가는 형태로 구현됨 - 기존 완전 탐색은 모든 답을 다 만들어 보면서 문제를 해결하므로 완전 탐색의 수행시간은 탐색 공간의 크기에 직접적으로 비례 - 이는 문제의 규모에 따라 기하급수적으로 크기가 증가. - 조합탐색이란 완전 탐색을 포함해 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아 내는 알고리즘 목표 - 기본적으로 모두 최적해가 될 가능성이 없는 답들을 탐색하는 것을 방지하여 만들어 봐야 하는 답의 수를 줄이는 것을 목표로 함 조합탐색 최적화 기법 - 가지치기 : 탐색 과정에서 최적해로 연결될 가능성이 없는 부분을 잘라낸다. 예) 외판원 문제에서 길이가 10인 경로를 이미..