개요 이 알고리즘은 회문(팰린드롬, palindrome)에 관해서 빠른 시간 안에 강력한 솔루션을 제공한다. 여기서 회문이란 $ abcba $처럼 뒤집어서 읽어도 똑같은 문자열을 뜻한다. 여기에 Manacher 알고리즘을 통해 문자열의 모든 위치에 대해서 그 위치를 중심으로 하는 최대 회문의 한쪽 길이를 $ O(n) $안에 구할 수 있다. READ MORE

문자열 매칭 문자열을 다루는 문제가 여러 종류가 있지만 그 중 가장 널리 쓰이는 것이 긴 문자열($ data $)에서 어떤 문자열($ query $)가 속해있는지 확인하는 문자열 매칭을 활용하는 것이다. 쉽게 말하면 우리가 인터넷 서핑이나 에디터에서 문서 작업을 할 때 ctrl + f로 단어를 찾는 작업을 구현한다고 생각하면 된다. READ MORE

문제를 해결하는 방법 우리가 어떤 문제를 접했을 때 이를 해결하는 방법에는 크게 두 가지가 있다. 첫 번째는 문제의 조건을 가지고 잘 계산을 해서 답을 도출해내는 것이고, 두 번째는 그 문제를 결정문제로 변형을 해서 이분탐색을 활용하여 해결하는 방법이다. READ MORE

개요 이 자료구조는 point update와 range query를 해야 하는 상황에서 사용된다. 더 자세히 말하자면 길이가 $ n $인 수열에 $ a $ 대해 point update: ($ i $, $ x $) => $ a[i] $를 $ x $로 치환 range query: ($ l $, $ r $) => $ a[l] \sim a[r] $ 중 sum/max/min 등 구하기. READ MORE