-
karuna's profile image
karuna
March 19, 2023
Introduction to Hardness Proofs and 3SUM Conjecture
Introduction to Hardness Proofs and 3SUM Conjecture Introduction 어떤 문제를 푸는 가능한 한 빠른 알고리즘을 찾아내는 것은 이론전산학 분야의 주된 관심사 중 하나입니다. 어떠한 문제든 우리가 원하는 만큼 빠른 알고리즘이 존재한다면 좋겠지만, 아쉽게도 이는 사실이 아닙니다. 예를 들어, $N$개의 정수를 크기 순으로 정렬하는 데에는 적어도 $\mathcal{O}(N\log N)$ 시간이 필요하다는 사실이 알려져 있습니다. 그렇다면 질문을 바꿔서, 어떤 문제를 해결하는 알고리즘의 시간 복잡도의 하한을 알 수는 있을까요? 이를 다른 말로 해당 문제의 hardness을 알아낸다고 말하는데, 이 역시도...
-
karuna's profile image
karuna
February 19, 2023
A Tree Representation for Failure Function of a String
A Tree Representation for Failure Function of a String Introduction KMP(Knuth-Morris-Pratt) 알고리즘은 주어진 문자열에서 패턴 문자열을 검색하는 전통적인 선형 시간 알고리즘이다. 알고리즘 대회 분야에서도 KMP 알고리즘을 응용하여 해결할 수 있는 문제는 꾸준히 출제되고 있으며, 한국 리저널만 보더라도 2017 Preliminary J번, 2021 Regional K번 등에서 등장한 바가 있다. KMP 알고리즘을 응용하여 해결하는 문제들은 많은 경우 KMP 알고리즘의 중간 단계에서 등장하는 실패 함수(Failure function)에 대한 깊은 이해를 바탕으로 한다. 따라서, 실패 함수가 해당 문자열의 구조에 대해 어떤...