-
PS에서 C++ 상속 활용하기 2
지난 글에 이어, PS에서 상속을 활용할 수 있는 사례 하나를 더 소개해보도록 하겠습니다. 행렬 라이브러리 PS 문제를 풀다보면, 가끔 행렬을 이용해서 풀어야 하는 문제들을 만날 수 있습니다. 이러한 문제들을 풀기 위해서는 행렬 곱셈 등의 연산을 구현해야 합니다. 비록 코드가 길지는 않지만, 이러한 행렬 곱셈을 매번 구현하는 것은 귀찮은 일이니, 행렬에 관한 라이브러리를 만들어두고 필요할 때마다 가져다 쓰는 것이 편할 것입니다. (더 빠른 행렬 곱셈 알고리즘이나, 반복문의 반복 순서 조정을 통한 캐시 히트율 개선 등 성능적...
-
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 문제를 이용해 해결하였다....