-
Gomory-Hu algorithm을 응용해 minimum odd cut 문제 해결하기
Introduction $T$-join 문제의 LP-relaxation을 생각해보자. (이 문제의 정의는 필자의 이전 글들에서 여러번 언급 했으므로 자세한 설명은 생략한다.) \[\begin{align*} \text{minimize:} & & \sum_{e \in E} c_e \cdot x_e && \\ \text{subject to:} & & x(\delta(S)) \ge 1 & &\forall S \subseteq V, \lvert S \cap T \rvert \equiv 1\pmod2 \\ & & x_e \ge 0 & & \forall e \in E \end{align*}\] 이 문제의 경우, LP의 optimal solution이 integral 하여, LP를 해결하면 원본 문제를 효율적으로 (다항...
-
Coldgame in problem solving
Intro 알고리즘 대회에 출전하거나 문제를 해결하다보면 게임을 하는 게임이론 문제를 가끔씩 만나볼 수 있습니다. 또한, 이러한 문제에 등장하는 게임은 다양한 분류가 가능하며 그 분류에 따라서 문제를 해결할 수 있는 방법도 가지각색입니다. 이 글에서는 여러분에게 조금은 더 친숙한 님 게임과 Sprague-Grundy Theorem이 아닌 Coldgame 이라는 것에 대해서 problem solving(이하 PS)의 관점에서 소개하고, 문제를 푸는 방법까지 설명하려고 합니다. About Coldgame은 Combinatorial game theory에서 Temperature에 따라 분류된 게임의 한 종류입니다. 위 문장의 각각에 대해서 설명하면 아래와 같습니다. Combinatorial...
-
Github Action + AWS Code Deploy로 CI/CD 구축하기
Intro CI/CD를 구축하는 방법은 여러 가지가 있지만, 이번 글에서는 Github Action과 AWS Code Deploy를 이용하여 CI/CD를 구축하는 방법에 대해 알아보겠습니다. AWS Code Deploy에서 on-premise 서버 등 AWS 서비스가 아닌 개인 머신에 배포하는 기능도 있지만, 이번 글에서는 EC2 인스턴스에 배포하는 방법에 대해 알아보겠습니다. CI/CD CI/CD는 Continuous Integration/Continuous Deployment의 약자로, 지속적 통합/지속적 배포를 의미합니다. 직관적인 말로 풀이하면, 작성한 코드를 자동으로 원하는 머신에 배포(설치)하는 것을 말합니다. CI/CD가 없다면, 다음과 같은 과정을 거쳐야 합니다. 코드 작성 머신 접속 코드...
-
Iterated Rounding을 이용해 Degree Bounded T-join 문제 해결하기
Introduction $T$-join 문제는 가중치 있는 무향 그래프 $G = (V, E, c)$ 와 짝수 크기의 정점의 부분집합 $T \subseteq V$ 가 주어질 때, $T$에 속하는 정점의 차수는 홀수, 그 외 정점의 차수는 짝수가 되게 하는 최소 비용의 $J \subseteq E$ 를 찾는 문제이다. 이 문제는 다양한 응용이 있으며, 대표적인 예로는 중국인 우채부 문제(Chinese Postman Problem)와 외판원 문제(TSP)에 대한 Christofides Algorithm이 있다. 과거 필자가 소개한 $s$-$t$ 경로 외판원 문제의 근사 알고리즘 또한 $T$-join 문제를 이용해 해결하였다....
-
Advanced SIMD Guide
Intro 최근에 SIMD 연산을 활용해서 최적화를 해 볼 기회가 있었습니다. 그 과정에서 겪었던 어려운 점들과 흥미로운 점들, 그리고 유용한 점들을 모아 공유하고자 합니다. 확인해보니, 암호학 분야를 깊게 보시는 blisstoner께서 기존에 SIMD에 관한 소개글을 포스팅하신 것이 있습니다. Link 이 글에서는 좀더 다양한 연산들, 주의해야 할 점들, 그리고 어떻게 쉽게 개발할 수 있을지를 집중적으로 설명해봅니다. 간단하게 다시 짚고 넘어가자면, SIMD (Single Instruction Multiple Data) 연산은 다수의 데이터에 동일한 연산을 한꺼번에 적용하고자 하는 목표를 가집니다. 여러 개의 데이터를...