-
정수 자료형으로 기하학 문제 데이터 검증하기
개요 기하학 문제가 까다로운 이유 중 하나는 실수 자료형을 쓸 때 생기는 부동 소수점 오차 때문입니다. 같은 이유로, 데이터가 문제의 조건에 맞는지 검증하는 과정 역시 쉽지 않습니다. 심지어 실수 자료형으로는 해결할 수 없는 경우도 존재합니다. BOJ 20939 달고나를 출제하면서 겪은 문제들과 해결한 과정에 대해 정리하고자 합니다. 입력 조건 문제에서 데이터 형식과 범위를 제외하고 검증해야 하는 조건들은 다음과 같습니다. 단순 다각형의 꼭짓점은 반시계방향 순서이다. 선분의 개수와 원의 개수 합이 2,000을 넘지 않는다. 세 개 이상의 선(원...
-
Catalyst Acceleration
서론 Convex Optimization의 주요 목적 중 하나는, convex function $f$가 있을 때 최적화 문제 $ f_{*} = \min_{x \in \mathbb{R}^d} f(x) $ 를 효율적으로 해결하는 것입니다. 특히, $f$가 수학적으로 좋은 조건을 만족하는, 즉 convex, closed, proper function인 경우를 (CCP function) 주로 다룹니다. Gradient Descent와 같은 first-order algorithm들은 이 목표를 달성하기 위해서 Gradient 또는 Subgradient를 이용합니다. 이제부터 다룰 대상은 Gradient를 사용하여 최적화를 하는 대신, Proximal Operator $ prox_{\lambda f}(x) = \text{argmin}_y \left( f(y) + \frac{1}{2\lambda} ...
-
Centroid of a Tree
Centroid of a Tree Centroid는 트리에서 문제를 해결하는 경우에 중요한 역할을 하는 경우가 많습니다. 이번 글에서는 트리에서 정의되는 centroid가 무엇인지, 어떤 성질을 가지고 있는지 그리고 어떻게 사용하는지 등을 알아보고자 합니다. Centroid 트리에서 centroid는, 어떤 정점 $v$가 크기 $n$짜리 트리 $T$에서 삭제했을 경우 생기는 subtree들이 모두 각각 크기가 $n/2$ 이하가 되는 경우, $v$를 $T$의 centroid라고 합니다. 위 그림에서는 1번 노드가 centroid 입니다. 1을 삭제했을 때 각각 크기가 3, 4, 4인 서브트리가 생기고 전체 트리의 크기는 11이므로...
-
Generalized Sorting with Predictions
이 글에서는 Pinyan Lu 외 3인의 논문 “Generalized Sorting with Predictions”에 대해 소개합니다. (글이 발행된 이후에 koosaga님의 project_tcs에 영상 및 자료가 올라갈 예정입니다.) 1. Generalized Sorting Problem 1.1. 문제의 정의 어떤 object들을 정렬하는 것은 컴퓨터 과학에 있어 매우 중요한 문제입니다. 일반적으로 우리가 (comparison-based) 정렬을 한다고 할 때, 우리는 임의의 원소 간의 “비교”가 가능한 상황을 상정합니다. Generalized sorting problem에서는 이 상황을 보다 일반화하여 일부 원소들 사이에는 비교 연산을 이용할 수 없는, 즉 일부 원소들 간의 비교만...
-
오일러 회로와 경로
이 글에서는 연결 무방향 단순 그래프를 다룹니다. 오일러 회로 그래프의 모든 간선을 단 한 번씩 지나서 시작점으로 돌아오는 경로를 오일러 회로라고 합니다. 연결 그래프면서 차수가 홀수인 정점이 없다면 오일러 회로가 존재합니다. 그리고 오일러 회로가 존재한다면 차수가 홀수인 정점이 없습니다. 오일러 회로와 관련된 문제를 풀기 위해서는 이 필요충분조건만 알고 있어도 되지만 아래에 서술할 증명이 간단하기에 한 번쯤 읽고 넘어가는 것을 추천합니다. 그래프에서 사이클이 존재하지 않기 위해선 트리가 되어야 하지만 트리에는 차수가 홀수(1개)인 리프 노드가 존재하기 때문에...