-
youngyojun's profile image
youngyojun
March 20, 2022
실무에서 빠르게 LCS를 계산하는 실용적인 Hunt-Szymanski 알고리즘에 관하여
개요 두 문자열의 가장 긴 공통 부분문자열을 찾는 Longest Common Subsequence (LCS) 문제는 정보과학에서 기초가 되는 잘 알려진 문제이다. 이렇게 기초적임에도 불구하고, LCS 문제는 생물정보학이나 전산언어학, 그리고 실생활에서 자주 사용하는 검색 엔진 등 다양한 학문과 분야에서 활용되는 아주 중요한 문제이다. 길이가 각각 $L_1, \cdots, L_N$인 문자열 $N$개의 LCS는 다이나믹 프로그래밍 기법을 이용하여 $\displaystyle \mathcal{O} \left( N \prod _{k=1}^{N} L _k \right) $의 시간 복잡도로 해결할 수 있음이 잘 알려져 있다. 본 글은 길이 $N$, $M$...
-
youngyojun's profile image
youngyojun
February 18, 2022
Stern-Brocot Tree를 활용한 수론적 함수의 합 계산
개요 정수론에서 주로 다루는 중요한 수론적 함수로는 약수 함수 $\sigma_k (n)$, 오일러 피 함수 $\phi (n)$, 뫼비우스 함수 $\mu (n)$ 등이 있다. 이러한 함수의 학문적 중요도는 이루 말할 수 없으며, 컴퓨터과학와 PS 분야에도 종종 등장할 정도로 다양하게 활용된다. 본 글은 수론적 함수의 대표인 약수 함수 $\sigma (n)$의 구간 합을 효율적으로 계산하는 알고리즘을 서술한다. 함수의 합을 기하적으로 해석한 후, 이를 Stern-Brocot Tree 자료구조로 계산한다. 이후, 이 알고리즘의 시간 복잡도가 $\tilde{O} \left( N^{1/3} \right)$로 아주 효율적임을 보인다....
-
youngyojun's profile image
youngyojun
September 19, 2021
영 타블로의 조합론적 의미와 알고리즘적 응용 (1)
개요 영 타블로(Young tableaux)는 20세기 초반, 알프레드 영(Alfred Young)이 제안한 객체로, 조합론에서 군(Group)을 표현할 때 유용하게 사용할 수 있는 특수한 형태의 행렬이다. 본 글은 다소 어려운 개념인 영 타블로를 쉽게 서술하고, 조합론적인 의미를 설명하며, 이를 활용하여 얻을 수 있는 효율적인 알고리즘과 새로운 문제 해결 관점 등을 소개하고자 한다. 본문은 특별한 배경지식을 가지지 않아도 읽고 이해할 수 있도록 작성되었다. 용어의 정의 영 다이어그램 영 타블로에 대하여 이야기하기 전에, 먼저 영 다이어그램(Young diagram)을 정의하자....
-
youngyojun's profile image
youngyojun
July 17, 2021
트리를 활용한 새로운 효율적인 수열 쿼리 알고리즘
개요 그래프란 정점과 간선으로 구성된 자료구조로, 버스 노선 설계와 같은 생활속 문제부터 다양한 학술 분야의 이론까지 폭넓게 도입할 수 있다. 트리란 그래프의 일종으로 사이클이 없으며 연결성을 가진다는 강력한 조건을 가져 알고리즘 설계에 자주 사용된다. 본 글은 수열에서 특정 조건을 만족하는 순서쌍의 개수를 세는 복잡한 쿼리를, 트리를 활용하여 효율적으로 처리하는 새로운 알고리즘을 소개한다. 본문은 아래의 내용을 부가적인 설명 없이 서술한다. 각 항목에 대하여 자세하게 서술한 좋은 글을 링크해두었다. 세그먼트 트리 (Segment Tree) Heavy-Light Decomposition...
-
youngyojun's profile image
youngyojun
May 17, 2021
다양한 생성함수와 그 응용 (2)
개요 본문은 아래의 포스트와 내용이 이어지며, 다음 포스트의 내용을 부가적인 설명 없이 서술한다. 다양한 생성함수와 그 응용 (1) 이번에는 생성함수를 어떻게 실제 PS 문제에 적용할 수 있는지 살펴본다. 다변수 생성함수 이항계수의 생성함수 이항계수 $\displaystyle \binom{n}{k}$의 OGF를 유도하자. 먼저, 이항계수와 같은 값을 가지는 함수 $f(n, k)$를 귀납적으로 정의하자. 다음은 이항계수의 일반적인 귀납적 정의이다: 다음을 만족하는 함수 $f : \mathbb{Z}_{\ge 0}^2 \rightarrow \mathbb{R}$은 모든 음이 아닌 정수 $n$, $k$에 대하여, $\displaystyle f(n, k) =...
-
youngyojun's profile image
youngyojun
April 18, 2021
다양한 생성함수와 그 응용 (1)
개요 어떤 주어진 성질을 만족하는 것의 가짓수를 세는 문제를 연구하는 학문을 조합론이라 하며, PS 분야 뿐만 아니라 통계학, 수리물리학 등 다양한 분야에서 중요하게 다루어진다. 일반적으로, PS 분야에서 조합론 문제는 Dynamic Programming 테크닉을 이용하여 효율적으로 해결할 수 있다. 하지만, DP 수열을 정의하는 점화식을 알아내는 작업은 조합론의 영역이지만, 그렇게 정의된 DP 수열을 빠르고 효율적으로 계산하는 작업은 알고리즘의 영역에 속한다. 본 글은, 후자의 알고리즘 문제를 해결하는 좋은 방법에 대하여 수학적으로 기술한다. 점화식 형태로 정의된 수열이 주어질...
-
youngyojun's profile image
youngyojun
March 19, 2021
그래프의 간선을 제거할 때 절점의 개수를 세는 효율적인 알고리즘
개요 그래프는 일상생활 뿐만 아니라 대부분의 과학 분야에서 ‘추상화’를 위해 사용하는 아주 강력한 자료 구조이다. 그래프의 중요한 성질로 여러 가지가 있으며, 이 글은 그 중에서 특히 절점과 절선에 대하여 다룬다. 무방향 그래프에서 각 간선을 끊었을 때, 그래프의 절점의 개수를 효율적으로 세는 알고리즘에 대하여 알아보고자 한다. 즉, 이 알고리즘은 다음과 같은 일상생활 속 문제를 해결할 수 있게 도와준다: 사내 서버망에서 어떤 회선이 끊어졌다고(불능이 되었다고) 하자. 여기서, 추가적으로 어떤 서버가 고장나야 서버망이 끊기게 되는가. 즉, 어떤 ‘중요한’...