본문 바로가기

Problem Solving/알고리즘

(4)
Small to Large Trick Intro Small to Large Trick은 집합을 서로 합치는 연산을 최적화 할 때 사용하는 트릭입니다. (한국에서는 작은거 큰거 라고도 불리는 모양입니다.) 예를 들어 $n$개의 disjoint한, 크기가 1인 집합을 서로 합쳐야 한다고 합시다. 당연하게도 크기가 $a$인 집합에 크기가 $b$인 집합을 추가하는 데는 $O(b)$의 시간이 걸립니다. 이걸 Naive하게 구현한다면 얼마의 시간이 걸릴까요? 만약 두 집합을 합칠 때 아무 집합을 다른 집합에 합치는 것을 계속 반복한다면, 최악의 경우에는 크기가 가장 큰 집합을 크기가 가장 작은 집합에 계속해서 넣으면서 총 $O(N^2)$의 시간이 걸릴 것입니다. 하지만 어지간히 멍청한 알고리즘이 아니고서야, 크기가 큰 집합을 작은 집합에 합칠리가 없습..
PS: 뉴비를 위한 Simulated Annealing 입문 (2) INTRO 국내에서 가장 널리 사용되는 온라인 저지인 BOJ에는 Simulated Annealing으로 풀 수 있는 유명한 문제가 하나 있습니다. 바로 동전 뒤집기 2 (https://www.acmicpc.net/problem/2582) 입니다. 많은 사람들이 KOI에도 시뮬레이티드 어닐링 같은 특수한 알고리즘을 시용해서 푸는 문제가 나오냐고 의아해 하는데, 저 당시에는 서브태스크가 아닌 테스트 케이스 당 부분점수가 있었고, 따라서 정해가 적절한 가지치기를 동반한 백트래킹이었다고 추측해 볼 수 있을 것 같습니다. 하지만, 고생고생해서 백트래킹에 휴리스틱 함수를 적용시키는 것 보다는 시뮬레이티드 어닐링을 배워서 써먹는 쪽이 아무래도 훨씬 빠르겠죠. 시뮬레이티드 어닐링은 이러한 종류에 문제에 더 일반적으로 ..
PS: 뉴비를 위한 Simulated Annealing 입문 (1) INTRO PS에서 우리가 푸는 평범한 알고리즘 문제들은 결정론적 문제입니다. 이 말은, 이미 출제자에 의해서 밝혀진 고정된 시간 안에 동작하는 해법이 있고, 우리는 그 해법을 찾아서 구현하기만 하면 된다는 뜻입니다. 그렇지만 NYPC 예선에서 나오는 출력 파일 문제라던가, IOI의 "그 문제"인 nowruz로 대표되는 Output Only 문제, Topcoder에서 진행되는 Marathon Match 등에서는 완벽한 최적해를 찾아내는 것이 불가능하기도 합니다. 이럴 때에는 많은 사람들이 휴리스틱 알고리즘을 사용합니다. 사실 휴리스틱 알고리즘이라고 하면 어떤 특정한 알고리즘을 지칭하는 것이 아닌데, 보통 저는 휴리스틱을 완전 탐색을 할 때 속도 향상을 위해 사용하는 일반적인 휴리스틱과 전역에서 최적점과 ..
[알고리즘] 최소 스패닝 트리 최소 스패닝 트리 (Minimum Spanning Tree, MST)는 모든 정점을 연결하면서 가장 작은 가중치를 가지는 트리를 만드는 알고리즘이다. 트리를 만드는 알고리즘이므로 이 그래프는 사이클이 없는 DAG 형태여야 한다. 이 문제를 해결하는 데에는 두 가지 알고리즘이 대표적으로 사용되는데, 바로 크루스칼 알고리즘과 프림 알고리즘이다. 일단은 크루스칼 알고리즘을 설명한 뒤에 프림 알고리즘을 구현할 때가 되면 그때 와서 추가해 놓겠다.크루스칼 알고리즘 크루스칼 알고리즘은 모든 간선 중 가장 가중치가 작은 간선부터 차례로 연결시키는데, 만약 새로 연결하는 간선 때문에 사이클이 생긴다면 그 간선을 포기한다. 원리도 굉장히 간단하고 구현도 굉장히 간단하다. 근데 Greedy한 알고리즘 답게 증명은 간단하지..