-
Mukjjippa (BOJ 32469)
이 글은 2024 KAIST 14th ICPC Mock Competition에 출제했던 문제 중 하나인 Mukjjippa (BOJ 32469)에 대해 다룬다. Problem 두 플레이어 A와 B가 묵찌빠라는 게임을 한다. 이 게임은 여러 턴으로 이루어진다. $i$번째 턴($1\le i\le n$)에서: 각 플레이어는 $\{\mathrm R,\mathrm S,\mathrm P\}$에서 정확히 하나를 선택한다. (각각 묵(rock), 찌(scissors), 빠(paper)를 나타낸다.) $X_i$와 $Y_i$를 각각 A와 B의 선택이라 하자. 만약 $(X_i, Y_i) \in \{(\mathrm R,\mathrm S),(\mathrm S,\mathrm P),(\mathrm P,\mathrm R)\}$라면, A가 $(i+1)$번째 턴의 공격자가 되고 게임은 계속된다. 만약 그렇지...
-
다양한 그래프 표현 방법
개요 그래프는 다양한 방법으로 표현될 수 있습니다. 각 방법은 특정 상황에서 장단점을 가지며, 문제의 요구 사항에 따라 적절한 표현 방법을 선택하는 것이 중요합니다. 이 글에서는 그래프를 표현하는 4가지 방법인 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List), CSR(Compressed Sparse Row), 그리고 XOR Linked Tree에 대해 설명합니다. (XOR Linked Tree 개념은 코드포스 글 https://codeforces.com/blog/entry/135239을 참고해 작성했습니다) 1. 인접 행렬 (Adjacency Matrix) 개념 인접 행렬은 그래프를 2차원 배열로 표현하는 방법입니다. 그래프에 i번 정점에서 j번 정점으로 가는 간선이 있다면 i행...
-
Aggregated Funnels
Intro 저번 글에서 Software Combining이 무엇인지, 이를 이용해 fetch-and-add를 어떻게 구현할 수 있는지를 살펴보았다. 이번에는 fetch-and-add 연산을 더 빠르게 만들어주는 Aggregating Funnels 알고리즘을 알아보자. Aggregating Funnels는 PPoPP 2025에서 발표될 논문에서 소개된 알고리즘이다. 본인은 알고리즘 설계 및 실험 수행에 주로 참여하였다. 실험 코드 또한 https://github.com/Diuven/aggregating-funnels 에 공개되어 있다. Combining Funnels와 목표하는 바는 비슷하고, 둘 다 Software Combining의 접근을 취하지만, 작동 방식 및 성능은 상당히 다르다. 이 글에서는 알고리즘의 개요와 성능에 대해서 설명한다. Key Points & Brainstorming...
-
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가...