실무에서 빠르게 LCS를 계산하는 실용적인 Hunt-Szymanski 알고리즘에 관하여
두 문자열의 가장 긴 공통 부분문자열을 찾는 Longest Common Subsequence (LCS) 문제는 정보과학에서 기초가 되는 잘 알려진 문제이다. 이렇게 기초적임에도 불구하고, LCS 문제는 생물정보학이나 전산언어학, 그리고 실생활에서 자주 사용하는 검색 엔진 등 다양한 학문과 분야에서 활용되는 아주 중요한 문…
글 읽기Secmem
7개의 글
Stern-Brocot Tree를 활용한 수론적 함수의 합 계산
정수론에서 주로 다루는 중요한 수론적 함수로는 약수 함수 σk(n), 오일러 피 함수 ϕ(n), 뫼비우스 함수 μ(n) 등이 있다. 이러한 함수의 학문적 중요도는 이루 말할 수 없으며, 컴퓨터과학와 PS 분야에도 종종 등장할 정도로 다양하게 활용된다.
글 읽기영 타블로의 조합론적 의미와 알고리즘적 응용 (1)
영 타블로(Young tableaux)는 20세기 초반, 알프레드 영(Alfred Young)이 제안한 객체로, 조합론에서 군(Group)을 표현할 때 유용하게 사용할 수 있는 특수한 형태의 행렬이다.
글 읽기트리를 활용한 새로운 효율적인 수열 쿼리 알고리즘
그래프란 정점과 간선으로 구성된 자료구조로, 버스 노선 설계와 같은 생활속 문제부터 다양한 학술 분야의 이론까지 폭넓게 도입할 수 있다.
글 읽기다양한 생성함수와 그 응용 (2)
본문은 아래의 포스트와 내용이 이어지며, 다음 포스트의 내용을 부가적인 설명 없이 서술한다.
글 읽기다양한 생성함수와 그 응용 (1)
어떤 주어진 성질을 만족하는 것의 가짓수를 세는 문제를 연구하는 학문을 조합론이라 하며, PS 분야 뿐만 아니라 통계학, 수리물리학 등 다양한 분야에서 중요하게 다루어진다.
글 읽기그래프의 간선을 제거할 때 절점의 개수를 세는 효율적인 알고리즘
그래프는 일상생활 뿐만 아니라 대부분의 과학 분야에서 '추상화'를 위해 사용하는 아주 강력한 자료 구조이다. 그래프의 중요한 성질로 여러 가지가 있으며, 이 글은 그 중에서 특히 절점과 절선에 대하여 다룬다.
글 읽기