-
coconut99's profile image
coconut99
February 25, 2025
LCS 알고리즘 최적화
개요 LCS(Longest Common Subsequence) 문제는 두 문자열의 공통 부분 수열 중 가장 긴 것을 찾는 문제로, 컴퓨터과학에서 가장 고전적이면서 중요한 문제 중 하나입니다. 이 글에서는 이 문제를 해결하는 간단한 Dynamic Programming 해법부터, 이것의 공간 복잡도를 개선한 Hirschberg 알고리즘과, 일반적인 문자열에서 더 효율적인 Hunt-Szymanski 알고리즘을 소개할 것입니다. 그리고 이들을 비트 집합을 이용해 더욱 최적화하는 방법을 다룰 것입니다. 간단한 DP 해법 $DP[i][j]$를 $A$의 길이 $i$인 접두사와 $B$의 길이 $j$인 접두사의 LCS 길이로 정의하면 다음과 같은 점화식으로 $A$와...
-
coconut99's profile image
coconut99
March 27, 2024
Polya's Enumeration Theorem을 이용한 카운팅 문제 해결
개요 Polya’s Enumeration Theorem(포여 열거 정리)는 어떤 작용에 대한 equivalence class의 개수를 구할 때 사용됩니다. 대표적인 예시로 돌리거나 뒤집어서 같은 것을 하나로 볼 때, 서로 다른 목걸이의 개수를 구하는 문제가 있습니다. 이 글에서는 Burnside Lemma와 그것의 일반화인 Polya’s Enumeration Theorem을 소개한 후 이를 적용하여 문제를 해결하는 과정을 서술하겠습니다. 관련 문제는 백준 문제집 또는 알고리즘 분류에서 찾아볼 수 있습니다. 해당 태그를 가진 문제가 9문제에 불과한 만큼 CP에서 자주 등장하는 주제는 아닙니다. 그렇지만 특정 형태의 카운팅 문제를...