-
Constructive 문제를 어떻게 풀 것인가
Constructive 문제를 어떻게 풀 것인가 들어가며 알고리즘 대회에서 Constructive Algorithm(구성적 알고리즘)은, 말뜻 그대로 답을 증명할 수 있는 실제 예시를 구성하는 것이다. 이 용어는 수학의 Constructive Proof(구성적 증명, 존재성의 증명 등에서 귀류법이나 귀납법을 쓰지 않고 직접 조건을 만족하는 예시를 만들어 증명하는 방법)에서 왔다고 할 수 있다. Constructive 문제에서 구성해야 하는 대상은 대개 Sequence나 Graph이다. 무에서 유를 창조해내야 하는 문제의 특성상, 많은 배경 지식을 필요로 하기도 하며, 특정 문제에서의 테크닉을 일반화하기 어렵다는 Ad-hoc의 특징도 가지고 있다. 그렇다고...
-
Lucas–Lehmer primality test
안녕하세요? 오늘은 $2^p - 1$꼴의 수(메르센 수)에 대해 소수 여부를 빠르게 판정할 수 있는 Lucas–Lehmer primality test에 대해 설명해보고자 합니다. 일반적인 소수 판정법은 시간이 굉장히 오래 소요됩니다. 가장 자명한 방법으로는 해당 숫자의 제곱근 이하의 소수들로 모두 나누어보는 방법이 있지만, 수가 어느 정도 커지면 사용하기 힘들어지게 됩니다. 더 큰 수에 대해 사용할 수 있는 알고리즘으로는 밀러-라빈 소수판정법이 있는데, 비결정론적인, 즉 확률에 의존한다는 단점이 있습니다. 하지만 특정 형태의 수에 대해서는, 굉장히 큰 숫자여도 해당 숫자가 소수인지를 결정론적으로...
-
Karp의 21대 NP-완전 문제
Richard Karp는 알고리즘의 선두를 이끈 인물 중 한 명입니다. Problem solving을 하는 사람들에게는 Edmonds-Karp 최대 유량, Hopcroft-Karp 이분 매칭, Rabin-Karp 부분문자열 탐색 등으로 잘 알려져 있는데, 이 분의 업적으로 NP-완전성을 빼놓을 수 없습니다. 배경 지식 P, NP, 다항 시간 환원, 그리고 NP-완전 문제에 대해서는 koosaga님의 글 계산 복잡도 위계와 불리언 식의 “QBF 문제” 직전까지를 참조해 주시기 바랍니다. NP-완전 문제 1971년, Stephen Cook은 The complexity of theorem proving procedures 논문에서 “비결정적 튜링 기계로 다항 시간에 결정할...
-
임의의 원소를 수정할 수 있는 우선순위 큐
서론 힙 (Heap)은 그 간단한 구조와 시간 / 공간 측면에서의 여러 장점들 때문에 문제 풀이뿐만 아니라 실무에서도 우선순위 큐로서 널리 애용되는 자료구조입니다. C++의 std::priority_queue, Java의 java.util.PriorityQueue, Python의 heapq1 등 고수준 언어의 자료구조 라이브러리에서 웬만하면 지원을 해주기도 합니다. 우선순위 큐를 라이브러리로만 접하면 기능이 매우 적은 것에 대해 실망할 수도 있습니다. 대체로 원소를 삽입하는 기능과, 최대 혹은 최솟값을 확인하고 제거하는 연산이 전부이기 때문입니다. 그런데 사실 힙에는 그 외에도 많은 가능성들이 숨어있습니다. 단순한 형태의 구현체에서는 수행하기 어려운 연산들을...
-
Dictionary 기반 압축 알고리즘
안녕하세요? 오늘은 저번 글에 이어, 압축 알고리즘에 대한 설명을 추가로 진행해보려 합니다. Dictionary Type Data Compression 저번 글에서 소개드린 데이터 압축 기술은 대부분 data entropy를 기반으로 되어 있습니다. 다시 말해, 전체 데이터의 빈도 수를 세고 빈도가 높은 것에 작은 길이의 bit를 할당하는 방식으로 작동하며 data entropy와 최종 압축률이 거의 유사한 값을 가지게 됩니다. 이번 글에서 살펴볼 방법들은 그와는 약간 다른, 출현하는 패턴들을 기억하는 dictionary를 사용하는 압축 방법들입니다. 다만, dictionary type data compression 또한 반복되는 패턴이...