출처: https://straightfromamovie.com/tenet-movie-analysis/
회문이란?
위의 이미지는 2020년 8월 개봉한 영화 테넷의 포스터입니다. 테넷의 제목인 TENET 이 회문의 좋은 예라서 가져왔습니다.
회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다.
위키백과에서는 회문을 다음과 같이 정의하고 있습니다. 여러 유명한 회문의 예가 궁금하시다면 나무위키에서 찾아보실 수 있습니다. 회문공포증이라는 뜻을 가진 영단어 "Aibohphobia" 도 회문이라고 하네요.
회문 알고리즘
거꾸로 읽어도 제대로 읽는 것과 같다고 하는 독특한 특징 덕분에 회문은 알고리즘 문제로 출제되기도 합니다. 자료를 검색해보니 아예 영문 위키백과에는 "Longest palindromic substring" 라는 제목으로 컴퓨터과학에서의 회문과 관련한 문제 및 그 알고리즘들을 정리해두었더라구요.
위키백과에서는 회문과 관련한 알고리즘을 2 가지로 나누어 소개하고 있습니다. 시간복잡도가 O(N2) 이 Slow algorithm 이 있구요. 시간복잡도가 O(N) 인 Manacher's algorithm 이 있습니다. Manacher's 알고리즘이 더 좋은 성능을 보여주고 있지만, 알고리즘을 이해하기 위해 slow 알고리즘부터 단계별로 올라가는 것을 권장한다고 되어있네요.
참고로 위키백과에서 소개하고 있는 algorithm 의 경우 길이가 홀수인 회문에만 적용 가능한 알고리즘으로 되어있어서, 짝수의 경우도 판별하기 위해 유령 문자(bogus character) 를 삽입한다는 특이점이 있으니 참고하실 때 주의할 필요가 있겠습니다. slow 알고리즘이나 Manacher's 알고리즘 둘 다 마찬가지입니다.
다음 주가 HA 인 관계로 알고리즘의 풀이는 차후로 미뤄둘 생각입니다. 오늘은 회문에 대해 간략히 소개하고 참고자료를 남기는 것으로 블로깅을 마치겠습니다.
