-
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...
-
C++ STL 컨테이너의 메모리 사용량 (1)
C++로 Problem Solving을 하는 사람도, 일반적인 프로그래밍을 하는 사람도 C++의 컨테이너는 매우 유용하게 사용합니다. 대표적인 예시가 동적 배열인 vector, 이진 탐색 트리인 set 등입니다. 이러한 자료구조를 적재적소에 사용하지 않으면 시간/공간 복잡도가 예상을 뛰어넘을 수 있습니다. 대표적인 예시가 “priority_queue가 set보다 빠르다”는 말입니다. 이는 일반적으로 사실이지만, 왜 그럴까요? 이와 관련된 질문에 답하기 위해 C++ 컨테이너가 메모리를 원소별로 얼마나 할당하고 그 이유는 무엇일지 gmem이라는 라이브러리를 통해 파트별로 알아보도록 하겠습니다. gmem 라이브러리 gmem은 동적으로 메모리를 할당할 때마다 로그를 남기고,...
-
2019 ACM-ICPC Seoul Regional 풀이
서론 2019년 2019년 11월 9일 토요일에 ACM-ICPC 서울 리저널이 진행 되었다. 대회에 대한 정보는 http://icpckorea.org 에서 찾아볼 수 있다. (학교 기준으로) 1등은 모든 문제를 해결한 서울대학교의 Cafe Mountain, 2등은 9문제를 패널티 1004분으로 해결한 연세대학교의 Inseop is Korea top, 3등은 9문제를 패널티 1464분으로 해결한 KAIST의 CMD이다. 올해에는 12문제가 출제 되었고, 이 문제들에 대한 풀이를 작성해보려고 한다. A - Fire on Field 문제 $A[0] = 1, A[1] = 1$ 이고, 2 이상의 $i$에 대해, $A[i]$ 를 모든...