-
동적 계획법을 최적화하는 9가지 방법 (Chapter 1)
동적 계획법을 최적화하는 9가지 방법 (Chapter 1) 동적 계획법(DP) 알고리즘의 시간 복잡도를 줄이는 기법에 대해서는 다양한 프로그래밍 대회에서 많이 출제된 바가 있다. 이러한 알고리즘은 굉장히 아름다운 방법으로 시간 복잡도를 줄이기 때문에 다양한 대회에서 인기가 많으나, 실제로 표준적인 알고리즘 교과서나 입문서에서 배우기는 힘든 내용이라 초심자가 시작하기 힘든 것이 단점이다. 현재 동적 계획법 최적화에 대해서 배울 수 있는 인터넷 자료들은 대부분 최신 자료가 아니기 때문에, 내가 알고 있는 동적 계획법 최적화 기법을 모두 소개함으로써 이 분야의 지식...
-
Tree Isomorphism
소개 안녕하세요. 이번 글에서는 Tree Isomorphism에 대해 소개해드리려고 합니다. Isomorphism이란 어떤 두 대상이 수학적으로 동등한 관계에 있음을 나타내는 용어인데, 트리에서의 Isomorphism이라 하면 한쪽 트리의 정점을 적절히 renumbering했을 때 다른 한 쪽 트리와 같아지는 것을 말합니다. (정확히는 그러한 mapping을 가리킵니다.) 이해를 돕기 위해, 다음과 같이 두 개의 트리가 있다고 합시다. 딱 보면 두 트리의 모양이 달라보이지만, 오른쪽 트리의 정점을 아래와 같이 renumbering하면 왼쪽 트리와 완전히 같은 연결 관계를 갖게 됩니다. 즉, 두 트리는 isomorphic합니다. 이처럼 두...
-
Effective Modern C++
오늘은 예전에 Effective Modern C++ 을 공부하며 정리했던 내용들을 포스팅해볼까 한다. C++11/14 에서의 best practice 에 관한 내용으로서 최근 C++20 이 나오는 시점에서 이 또한 최신 내용은 아니긴 하지만 여전히 많은 부분들이 유효한 내용들이라서 큰 도움이 된다고 생각한다. Chapter 1. 형식 연역 (Type Deduction) 항목 1. 템플릿 형식 연역 규칙을 숙지하라. 아래에 적어놓은 코드를 보면 C++11/14에서의 Template Type Deduction 규칙을 파악할 수 있을 것이다. 대부분 직관과 거의 잘 맞아떨어진다. 그래도 주의 할 점 몇가지를 살펴보면,...
-
Randomize algorithm
안녕하세요? 저번 글에서는 karger’s algorithm에 대한 글을 써보았습니다. 이번 글에서는 그에 이어 또다른 randomize algorithm인 Freivald’s algorithm과 기타 다른 randomize된 기법들에 대해 간단히 설명해보겠습니다. Freivald’s algorithm 행렬 A, B, C가 주어졌을때 A*B=C를 만족하는지 어떻게 확인할 수 있을까요? 물론 직접 곱해본다면 간단하게 확인할 수 있지만, 행렬의 곱은 시간이 굉장히 많이 소요되는 작업입니다. 무려 $O(n^3)$ 만큼의 시간이 소요됩니다. 물론 이 시간복잡도를 더 줄이는 방법이 존재하긴 합니다. 슈트라센 알고리즘을 사용하면 복잡도를 $O(n^{2.807})$로 줄일 수 있고, 분할을 더 잘...
-
Introduction to Matroid Union
Matroid Matroid에 대한 기본 지식은 다른 글을 참고하는 것이 좋다. 여기서는 Matroid의 정의만 짚고 넘어가자. 정의 1. 유한집합 $S$와 $S$의 부분집합족 $\mathcal{I}$에 대해 $M=(S, \mathcal{I})$가 아래 조건을 만족할 경우 $M$을 Matroid라고 한다. ${}\in\mathcal{I}$ (Empty set is Independent set) $B\subset A\in\mathcal{I}\Rightarrow B\in\mathcal{I}$ (hereditary property) $A, B\in\mathcal{I}, \mid A\mid>\mid B\mid\Rightarrow\exists x\in A\setminus B$ $s.t.$ $B+x\in\mathcal{I}$ (augmentation property) $S$의 부분집합이 $\mathcal{I}$에 포함될 경우 독립집합(Independent set)이라고 부른다. Matroid Union Matroid Union은 Matroid의 합집합으로, 다음과 같이 정의된다. 정의 2. Matroid...