-
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) 연산은 다수의 데이터에 동일한 연산을 한꺼번에 적용하고자 하는 목표를 가집니다. 여러 개의 데이터를...
-
New Updates on Proximity Testing with Logarithmic Randomness
소개 이전 글에서, “Proximity Testing with Logarithmic Randomness”라는 논문을 소개했습니다. 이 논문을 읽은 당시에 제가 논문에 있었던 증명의 작은 오류를 찾아 이를 수정하는데 기여하기도 했으며, 그 내용도 이전 글에 소개되어 있습니다. 1월 이후, 해당 논문과 관련된 여러 새로운 발견이 이루어졌습니다. 이 글에서는 1월 이후 Proximity Testing에 대한 추가적인 발전에 대해서 다룹니다. 복습 이전 논문에서 다룬 핵심적인 정리는 다음과 같습니다. For any $[n, k, d]$ code $V \in \mathbb{F}_q^n$ and $e < d/3$, given $u_0, \cdots,...