코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
알고리즘 — 문제 해결의 체계적 접근 → 문제 해결
문자열 알고리즘은 프로그래밍에서 가장 실용적인 분야 중 하나예요.
여러분이 구글에서 검색할 때, 수십억 개의 웹페이지에서 원하는 단어를 찾아야 해요.
생물정보학에서는 30억 개의 DNA 염기쌍에서 특정 유전자 서열을 찾아야 하고요.
에디터에서 Ctrl+F를 누르면 실시간으로 모든 {매칭→매칭}을 하이라이팅해줘야 해요.
왼쪽 네 개의 상자를 보세요. 검색 엔진, 생물정보학, 에디터, 보안 분야에서 모두 핵심이에요.
가장 단순한 방법인 브루트 포스는 텍스트의 모든 위치에서 {패턴→패턴}을 비교하는 거예요.
아래쪽 빨간 막대를 보시면, O(nm)이에요. n은 텍스트 길이, m은 {패턴→패턴} 길이죠.
텍스트가 10억 글자이고 {패턴→패턴}이 100만 글자면, 10의 15승 번 비교해야 해요.
이건 슈퍼컴퓨터로도 현실적이지 않은 시간이에요.
그래서 똑똑한 알고리즘이 필요한 거예요. {KMP→케이엠피} 알고리즘은 이미 비교한 정보를 재활용해요.
{Rabin-Karp→라빈카프}는 {hash→해시} 함수를 써서 문자열을 숫자로 변환하고 비교해요.
파란색과 녹색 막대를 보세요. 둘 다 O(n+m)에 해결할 수 있어요.
브루트 포스보다 백만 배 빠른 거죠! 오른쪽 화살표가 그 차이를 보여줘요.
오른쪽 점선 상자에 이 레슨의 학습 로드맵이 있어요.
{접미사 배열→서픽스 어레이}은 텍스트의 모든 접미사를 정렬해서 이진 탐색으로 {패턴→패턴}을 찾아요.
Z 알고리즘, 문자열 {해싱→해싱}, {Aho-Corasick→아호코라식} 같은 고급 기법도 배울 거예요.
이 레슨에서는 실제 코드와 함께 각 알고리즘의 핵심 아이디어를 체험해볼 거예요.
특히 "왜 이 알고리즘이 빠른가"를 직관적으로 이해하는 게 목표예요.
하단의 결론 문장을 보세요. 핵심은 이미 비교한 정보를 재활용하는 거예요.
먼저 브루트 포스의 한계를 정확히 이해하고, 거기서 {KMP→케이엠피}가 어떻게 개선되는지 볼게요.
그 다음 {해시→해시} 기반 접근법, {Trie→트라이}, {접미사 배열→서픽스 어레이} 순서로 진행할 거예요.
각 알고리즘마다 실제 문자열로 직접 손으로 따라가볼 거예요.
자, 그러면 브루트 포스부터 시작해볼까요?