-
ho94949's profile image
ho94949
August 19, 2023
연산에 대한 O(n log n) / O(1) 구간 쿼리
프로그래밍을 하면서 많이 맞닥뜨리는 연산중 하나는 “구간 쿼리”입니다. 결합법칙을 만족하는 어떤 종류의 연산이든, $O(N \log N)$ 전처리로 쿼리당 $O(1)$ 시간에 구간에 대한 쿼리를 답할 수 있는 구조를 설명하려고 합니다. 구간 쿼리 구간 쿼리는 다음과 같은 문제입니다. (전처리) 배열 $A = (A_0, A_1, \cdots, A_{N-1})$과 연산 $\circ$가 주어집니다. (쿼리) $1 \le l \le r \le N$이 주어지면, $A_l \circ A_{l+1} \circ \cdots \circ A_r$을 계산해야합니다. 여기서, 우리가 주목해볼 연산의 성질은 다음과 같습니다. 결합법칙: 임의의 세 원소...
-
ho94949's profile image
ho94949
July 22, 2023
Erdös-Ginzburg-Ziv 정리의 O(n log n) 시간 해법 찾기
Erdös-Ginzburg-Ziv 정리는 임의의 길이 $2n-1$의 정수열에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. 이전에 작성된 글에서는 $O(n^2/w)$ 풀이를 소개했지만, 최근에 공개된 이 부분수열을 직접 찾는 $\mathcal{O}(n \log n)$ 풀이에 대해서 소개합니다. Erdös-Ginzburg-Ziv 정리와 증명 Erdös-Ginzburg-Ziv 정리는 길이가 $2n-1$인 임의의 정수열 $A = { {a}_1, {a}_2, \cdots, {a}_{2n-1}}$에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. $A$에 따른 $A$의 부분수열을 Erdös-Ginzburg-Ziv 정리의 해법이라고 부릅니다. Erdös-Ginzburg-Ziv가 간단한 증명을 제시했고, 이...
-
ho94949's profile image
ho94949
June 21, 2023
그래프 채색 개론
서론 (무향) 그래프 $G$는 정점 집합 $V$와 간선 집합 $E$ 로 이루어진 구조입니다. 간선은 두 원소를 잇는 (순서가 없는) 선입니다. 여기서 그래프의 정점을 색칠한 다는 것은, 간선의 양 끝이 다른 색이 되도록 색칠한다는 것입니다이 게시글에서는 그래프 색칠에 대한 다양한 주제를 다룹니다. 해당 주제는 그래프 색칠에 대한 시각을 늘려줄 것이라고 생각합니다. 다룰 주제는 다음과 같습니다. 주제 이분그래프 색칠 그리디 색칠, $(\Delta+1)$색 정리, $6$색 정리 $5$색 정리, $4$색 정리, Kempe Chain, $\Delta$색 정리 채색 다항식 표기법 이...
-
ho94949's profile image
ho94949
February 19, 2023
Diversified Late Acceptance Search
서론 지역 검색(Local Search) 알고리즘은, 여러 종류의 최적화 문제를 광범위하게 해결하는 데에 사용하고, 다양한 알고리즘의 기준선(baseline)이 될 수 있습니다. 우리는 이 알고리즘 중 기초적인 언덕 오르기(Hill Climbing) 알고리즘과, 그 변형인 늦게 수용하는 언덕오르기(Late Acceptance Hill Climbing, LAHC) 알고리즘 중 하나인 다양성을 갖춘 늦게 수용하는 탐색(Diversified Late Acceptance Search, DLAS)에 대해 알아봅니다. 언덕 오르기 알고리즘과 변형 언덕 오르기 알고리즘은 최적화 문제를 해결하기 위한 간단하고 직관적인 알고리즘 중 하나입니다. 이 알고리즘은 현재 상태에서 지역 최적해를 찾는 데...
-
ho94949's profile image
ho94949
September 15, 2022
최소 절단 그래프 모델링
서론 최소 절단(Minimum Cut) 문제는 다음과 같은 문제입니다. 유향 가중치 그래프 $G$가 있습니다. 그래프의 정점을 두 개의 집합 $S$와 $T$로 나눌 것인데, 다음 조건을 만족해야 합니다. 주어진 정점 $s$에 대해 $s \in S$여야 합니다. 주어진 정점 $t$에 대해 $t \in T$여야 합니다. 절단된 간선의 가중치 합을 최소화 해야합니다. 모든 간선 $u \xrightarrow{w} v$에 대해 $u \in S$이고 $v \in T$인 경우, 해당 간선은 절단되었다고 합니다. 이 문제에 대한 답을 $s-t$ 최소 절단이라고 합니다. 최대유랑 -...
-
ho94949's profile image
ho94949
March 10, 2022
Minimum Steiner Tree의 계산
서론 그래프 $G$와, 정점의 부분집합 $T$가 주어졌을 때, $T$를 모두 포함하는 Spanning Tree ($G$의 부분그래프 중, 정점과 간선 일부를 선택하여 만든 트리)를 $T$의 Steiner Tree라고 한다. 가중치가 주어진 방향 없는 그래프 $G$에 대해 간선 가중치 합이 가장 작은 Steiner Tree를 계산하는 문제는 일반적인 상황에서 NP-Hard임이 알려져있다. 이 게시글에서는, 해당 Steiner Tree를 계산하는 동적계획법을 다룬다. Naïve 편의상, 그래프의 $G = (V, E)$의 정점 개수를 $N$, 간선 개수를 $M$, 정점 부분집합 $T$의 크기를 $K$라고 하자. 가장 쉽게...
-
ho94949's profile image
ho94949
August 20, 2021
와일드카드 문자열 매칭
서론 문자열 매칭 알고리즘은, 문자열 $S$와 $T$가 주어졌을 때, $S$의 부분문자열(substring) 중에 $T$가 어느 위치에 등장하는지 찾는데 사용하는 알고리즘이다. 우리는 이 문자열 매칭 알고리즘에 와일드카드 문자, 즉, 어떤 문자에도 대응 될 수 있는 ? 문자가 들어갔을 때 어떤 식으로 문제를 해결해야 하는지 알아본다. ? 문자가 들어가지 않았을 때 문자열 매칭을 하는 법에 대해서는, KMP 알고리즘과 Aho-Corasick 알고리즘 문서에 잘 설명이 되어 있으니, 참고하면 된다. 문제 우리가 풀고 싶은 문제는 다음과 같다. 문자열 길이 $N$의 문자열...
-
ho94949's profile image
ho94949
March 18, 2020
Erdös-Ginzburg-Ziv 정리
서론 0과 1이 $X$개 있을 때, 그 중 항상 같은 수가 $N$개 이상 있게 하는 최소의 $X$는 $2N-1$이다. $X=2N-2$인 경우에는, 0과 1이 $N-1$개 존재하면 불가능하다. $X = 2N-1$개 있을 때는, 비둘기집의 원리에 의해서 항상 0이 $N$개 혹은 1이 $N$개 존재한다. 우리는 이 비둘기집의 원리의 일반화된 버전을 생각해 본다. 임의의 정수가 $X$개 있을 때, 그 중 합이 $N$의 배수가 되는 $N$개를 고를 수 있는 최소의 $X$는 얼마인가? 수로 0과 1만 가능한 것이 아니라, 모든 정수가 가능하다....
-
ho94949's profile image
ho94949
December 14, 2019
이항계수의 빠른 계산
서론 $\binom{N}{K}$ 는 $N$개의 구분이 되는 물체 중 $K$개를 고르는 가짓수이고, 이를 이항계수라고 부른다. 이항계수는 한 조합론적 상황에서 많이 사용된다. 이 $\binom{N}{K} = \dfrac{N!}{K!(N-K)!}$임이 잘 알려져 있다. 이 수를 소수가 아닌 임의의 수 $M$으로 나눈 나머지를 구하는 방법에 대해서 알아본다. Naive 이항계수를 $M$으로 나눈 나머지를 구하는 가장 쉬운 방법은 실제로 $N!$을 그냥 1부터 $N$까지의 모든 수를 곱하는 것으로 계산하는 것이다. 하지만 이럴 경우에 나눗셈이 잘 되지 않는다. 예를 들어서, $M=9$인 경우에는, $6! = 720$과 $7!=5040$을...
-
ho94949's profile image
ho94949
November 14, 2019
2019 ACM-ICPC Seoul Regional 풀이
서론 2019년 2019년 11월 9일 토요일에 ACM-ICPC 서울 리저널이 진행 되었다. 대회에 대한 정보는 http://icpckorea.org 에서 찾아볼 수 있다. (학교 기준으로) 1등은 모든 문제를 해결한 서울대학교의 Cafe Mountain, 2등은 9문제를 패널티 1004분으로 해결한 연세대학교의 Inseop is Korea top, 3등은 9문제를 패널티 1464분으로 해결한 KAIST의 CMD이다. 올해에는 12문제가 출제 되었고, 이 문제들에 대한 풀이를 작성해보려고 한다. A - Fire on Field 문제 $A[0] = 1, A[1] = 1$ 이고, 2 이상의 $i$에 대해, $A[i]$ 를 모든...
-
ho94949's profile image
ho94949
October 18, 2019
제곱수의 합
서론 숫자를 제곱수의 합으로 표현하는 문제는 매우 유명한 문제이다. 예를 들면, $11339 = 1^2+27^2+103^2$ 으로 표현 가능 하고, 11339는 세 제곱수의 합으로 표현 가능하다. 우리는 이 글에서, 어떤 자연수를 최소 갯수의 제곱수의 합으로 표현하는 방법에 대해 알아본다. 제곱수의 최소 갯수 우리는 어떤 자연수가 최소 갯수의 제곱수의 합으로 표현되려면, 제곱수의 합으로 어떤 자연수를 표현하려면, 제곱수가 몇 개 필요한지를 알아 볼 필요가 있다. 이를 위해서 다음의 세 정리들이 필요하다. Lagrange의 네 제곱수 정리 Lagrange는 1770년에, 모든 자연수는...
-
ho94949's profile image
ho94949
September 17, 2019
N! mod P 의 빠른 계산
서론 $N!$ 은 1이상 $N$ 이하의 모든 정수를 곱한 수 이다. 이 $N!$는 다양한 조합론적 상황에서 많이 사용된다. 이 $N!$을 특정한 소수 $P$로 나눈 나머지를 빠르게 ($O(\sqrt{N} \log{N})$ 시간에) 계산 하는 방법에 대해서 알아본다. Naive 팩토리얼을 구하는 가장 쉬운 방법은 모든 1이상 $N$ 이하의 수를 곱해서 $P$ 로 나누는 것이다. $ab$를 $P$로 나눈 나머지와 $(a \bmod P)(b \bmod P) \bmod P$ 가 같다는 것을 이용하면, 사이에 나오는 숫자를 항상 $P^2$ 이하로 유지하면서 쉽게 구할 수...
-
ho94949's profile image
ho94949
August 17, 2019
빠른 격자점 세기
서론 우리는 어떤 그래프 내부의 격자점을 세어야 할 일이 있는 경우가 있다. 예를 들면, 원 안의 격자점의 갯수를 세는 것은 $\pi$ 의 값과 피타고라스 쌍과 관련이 있으며, 약수의 갯수의 합을 구하려 $f(x) = \frac{N}{x}$ 내부의 격자점의 수를 세기도 한다. 여기서는 이 전략을 구체화 시켜서 convex hull 위의 점의 갯수로 문제를 푸는 방법에 대해 알아보고, 또한 약수의 갯수를 $\tilde{O}(n^{\frac{1}{3}})$ 에 세는 방법을 알아본다. 약수 두 자연수 $A$, $B$에 대해서 $B$로 $A$를 나눴을 때 나누어 떨어지면, 우리는...
-
ho94949's profile image
ho94949
July 20, 2019
이진탐색의 확장 - 트리에서의 효율적인 탐색
서론 이진탐색은 정렬된 $N$개의 원소가 있을 때, 원하는 수의 위치를 $O(\log N)$ 시간에 찾는 테크닉이다. 이 글에서는 이진탐색을 트리로 확장할 것이다. 그리고 트리에서도 원하는 수의 위치를 $O(\log N)$시간에 찾을 수 있다는 증명과, 비교연산을 최소로 하는 방법을 설명할 것이다. 이진탐색 탐색이란 숨겨진 $a$ 이상 $b$이하의 정수 $x$에 대해, 이 $x$를 찾는 과정이다. 이진탐색에서는 다음과 같은 질문을 할 수 있다: “어떤 수 $y$ 에 대해, $y$와 $x$의 대소관계는 무엇인가?” $y$가 $x$보다 크다는 답이 돌아오면, 우리는 $x$가 $y+1$...
-
ho94949's profile image
ho94949
June 16, 2019
다항식 나눗셈과 다중계산
서론 다항식 다중계산(Multipoint evaluation)은, $N$차 다항식 $f$에 대해, $Q$개의 원소 $x_1, x_2, \cdots, x_Q$ 를 $O(\max(N, Q)\log^2 \max(N, Q))$ 시간에 계산할 수 있도록 도와주는 도구이다. 이 Multipoint evaluation의 계산을 위해서는, 다항식의 빠른 곱셈, 다항식의 빠른 나눗셈을 알아야 한다. 이 글에서는 이를 계산 하는 빠른 방법을 알아본다. 다항식 곱셈 다항식의 빠른 곱셈에는 FFT를 사용한다. FFT란, $x_0, x_1, \cdots, x_{N=1}$ 을 $X_0, X_1, \cdots, X_{N=1}$으로 다음과 같은 규칙에 따라 바꾸는 변환이다. $X_k = \sum_{n=0}^{N-1} x_n \omega^{nk} \qquad...
-
ho94949's profile image
ho94949
May 5, 2019
그래프 색칠과 NP-Completeness
서론 현실의 여러 대상들은 그래프로 추상화 할 수 있다. 그래프를 색칠하는 것은, 서로 인접한 두 정점이 같은 색을 같지 않도록 색칠 하는 것이다. 이 그래프를 색칠하는 문제는, 다양한 스케쥴링 문제 혹은 컴파일러의 레지스터 배치, 패턴 매칭, 시험/수업 시간표 작성 등 다양한 문제를 해결할 수 있다. 이런 문제들이 다항시간안에 검증이 가능하지만, 다항 시간안에 풀리는지는 밝혀지지 않는 NP-Complete 문제라는 것을 알아보자. 그래프 그래프는, 정점을 나타내는 집합 $V$와, 간선을 나타내는 집합 $E$의 원소인, $G = (V, E)$로 나타낸다....
-
ho94949's profile image
ho94949
April 8, 2019
최소 외접원 찾기
서론 최소 외접원 문제는, 2차원 평면 상에 점이 $N$개가 있을 때, 이들을 모두 담는 최소 반지름의 원이 과연 무엇인지를 찾는 문제입니다. 실생활에서 굉장히 많이 사용될 수 있는 문제이며, 예를 들면, 어떤 도시에 기지국을 지어야 하는데, 어느 곳에 지어야 송신소를 모두에게 도달하면서, 최소한의 반지름으로 모든 송신소를 덮을 수 있는 지 등, 효율적인 배치에 관한 문제입니다. 이 게시글에서는 이 문제를 $O(N)$에 푸는 방법을 소개 합니다. 담금질 기법 담금질 기법은, 원래는 모든 최적화 문제에 사용되는 기법입니다. 담금질 기법은,...
-
ho94949's profile image
ho94949
March 9, 2019
OpenAI Gym 사용하기
서론 OpenAI Gym은 강화학습을 도와주고, 좀 더 일반적인 상황에서 강화학습을 할 수 있게 해주는 라이브러리 입니다. 이 게시글에서는 OpenAI Gym을 사용하는 법을 알아보고, 샘플 프로젝트인 CartPole-v1에서 동작하는 신경망을 만들어봅니다. OpenAI Gym의 설치 OpenAI Gym은 python3.5 이상에서 작동합니다. gym은 간단하게 pip로 설치할 수 있습니다. 그리고 이 샘플 프로젝트를 도와주는 numpy와 keras를 설치해야합니다. 기본적으로 이는 Python에 추가적인 지원을 해주는 Anaconda가 해줄 수 있으며, gym설치 및 numpy 업그레이드를 진행해야합니다. pip install gym pip install numpy --upgrade CartPole-v1 우리가...
-
ho94949's profile image
ho94949
February 9, 2019
랜덤 올바르게 사용하기
서론 프로그램을 작성할 때 랜덤한 요소는 많이 들어갑니다. 어떤 공간을 탐색할 때 무작위로 탐색을 하기도 하고, 프로그램의 비밀 키를 만들거나 게임을 만들 때 카드 덱을 섞을 때 등, 랜덤이 프로그램에 사용되는 곳은 굉장히 많습니다. 하지만 이 랜덤은 자주 잘못 사용되고는 합니다. 랜덤을 올바르게 사용하는 방법에 대해 알아보려고 합니다. 랜덤이란? 랜덤이란 특정한 패턴이 없다는 것을 말합니다. 즉, 어떤 규칙에 의해 생성되지 않고 다른 변수와 독립적으로 만들어진 결과를 랜덤한 결과라고 합니다. 과연 완벽한 좋은 랜덤을 만들 수...
-
ho94949's profile image
ho94949
January 10, 2019
그래프 모델링 - 최단경로
서론 실생활의 다양한 문제들은 (유향)그래프로 표현이 가능합니다. 이 포스트에서는 문제들을 그래프로 변형하는 방법과, 그래프로 변형하여 문제를 간단하게 푸는 방법에 대해 소개합니다. 그래프 “내가 가고 싶은 도시들이 있고, 그 도시들 사이에 교통 수단을 표현하려면 어떤 방법을 써야할까요?” 그래프(graph)는 정점(vertex, 주로 $V$ 로 표기)와 간선(edge, 주로 $E$ 로 표기)로 이루어진 구조입니다. 각 정점은 임의의 집합입니다. 즉, 아무것이나 될 수 있습니다. 각 간선은 정점 두개를 잇는 선입니다. 이 때, 각 정점의 순서가(즉, 방향이) 있으면 유향그래프, 없으면 무향그래프라고 말합니다....