-
ptrace로 프로세스 제어 및 응용하기
Intro 안녕하세요. 이번 글에서는 리눅스에서 제공하는 시스템 콜인 ptrace를 활용하여 프로세스를 제어하는 방법을 다루어보려 합니다. ptrace는 프로세스(process)를 추적(trace)하고 디버깅하는 데 사용되는 강력한 기능을 제공합니다. 우리가 흔히 사용하는 GDB(GNU Debugger)도 내부적으로 ptrace를 사용하여 디버깅 기능을 수행합니다. 본 글에서는 ptrace가 제공하는 여러 기능을 살펴본 후, 이를 응용하여 간단한 예제 프로그램을 만들어 보겠습니다. 본 글은 기본적인 시그널 제어 및 프로세스 핸들링을 이해하고 있다는 가정 하에 작성되었습니다. 시그널과 프로세스에 대한 기본적인 이해가 없는 경우, 먼저 해당 내용을 숙지하신 후...
-
Cartesian Tree를 활용한 문제 해결
Cartesian Tree Cartesian Tree는 대소 관계가 있는 값의 배열으로부터 유도되는 Binary Tree로, 구간의 min/max와 관련된 문제에 사용하면 편리한 자료 구조입니다. 배열의 최솟값 또는 최댓값에 해당하는 인덱스를 루트로 하게 되는데, Min Cartesian Tree의 경우 최솟값에 해당하는 $\mathrm{array}[i] = \min_{l \leq i \leq r}(\mathrm{array}[i])$인 $i$가 루트가 되며, $[l, r]$번째 원소의 최솟값에 대응되는 노드 $i$의 왼쪽 자손은 $[l, i-1]$에서의 최솟값, 오른쪽 자손은 $[i+1, r]$에서의 최솟값에 해당하는 인덱스가 됩니다. 자주 사용하게 되는 성질 몇 가지가 있는데, 각 노드의 subtree가...
-
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...