-
solving JIE-constant (acmicpc 22222)
문제 소개 지애 상수는 백준의 22222번째 문제를 기념하여 출제된 문제로, 문제에서 정의된 지애 상수라는 값을 소수점 222자리까지 구하는 문제입니다. 지애 상수의 정의는 아래와 같습니다. Definition of 지애 상수 지애 상수는 좌표평면의 점 $A(0,0),B(1,0),C( {1 \over 2} , { \sqrt 3 \over 2})$로 정의된 정삼각형 $ABC$에서 시작하여 만든 시에르핀스키 삼각형에서 독립적으로 균등하게 잡은 점 두 개의 유클리디안 거리의 기댓값입니다. 균등하게 점 잡기? 지애 상수를 정의하기 위해서는 우선 시에르핀스키 삼각형에서 점을 균등하게 잡는 것을 수학적으로 정의할 수...
-
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가 제공하는 여러 기능을 살펴본 후, 이를 응용하여 간단한 예제 프로그램을 만들어 보겠습니다. 본 글은 기본적인 시그널 제어 및 프로세스 핸들링을 이해하고 있다는 가정 하에 작성되었습니다. 시그널과 프로세스에 대한 기본적인 이해가 없는 경우, 먼저 해당 내용을 숙지하신 후...