🎥드라마로 보는 코딩 #1 - 🍱문자열 찾기 알고리즘

문자열 찾기 알고리즘의 매력

코딩을 공부하다 보면, 알고리즘이라는 단어가 좀 무섭게 느껴질 수 있어요. 그런데 문자열 찾기 알고리즘은 정말 실생활과 가까워서, 초보자분들도 금방 흥미를 가질 거예요. 쉽게 말하면, 긴 문장이나 텍스트 속에서 특정 단어나 패턴을 찾아내는 거예요. 영상에서처럼 "해당 문장에서 '한번'이라는 단어를 모두 찾아라" 같은 문제가 나오면, PDF 파일에서 Ctrl+F로 검색하는 기능이 떠오르시죠? 이게 바로 문자열 찾기 알고리즘의 기본이에요.

먼저, 왜 이 알고리즘이 중요한지 알아볼게요. 상상해 보세요. 여러분이 DNA 연구소를 운영한다면, 수억 개의 염기서열(A, T, G, C) 중 특정 유전자를 찾아야 해요. 단순히 눈으로 훑는 건 불가능하니, 컴퓨터가 효율적으로 검색해야 하죠. 실제로 구글 검색 엔진이나 바이오 인포매틱스에서 이 알고리즘을 써요. 초보자분들을 위해 설명드리면, 문자열은 그냥 문자들의 배열(예: "hello world"는 h-e-l-l-o- -w-o-r-l-d)로 보시면 돼요. 찾을 패턴은 "hello"처럼 짧은 부분이에요.

이 문제의 매력을 더하는 건, 다양한 난이도예요. 영상에서 드라마처럼 "자, 덤벼라!" 하며 도전하는 장면이 나오는데, 실제 코딩 인터뷰나 코테(코딩 테스트)에서 자주 나와요. 예를 들어, "ababcabcabababd"라는 문자열에서 "abab" 패턴을 찾는다면, 위치 0, 2, 6에서 매치돼요. 이걸 수동으로 하면 피곤하지만, 알고리즘으로 하면 컴퓨터가 순식간에 해줘요. 배경 지식으로, 이 개념은 1970년대부터 연구됐어요. 컴퓨터 과학의 고전 문제라서, 배우면 자부심이 생길 거예요.

이제 기본 예시를 들어볼게요. 문장: "정말 재미있는 코딩 세계예요." 패턴: "재미". 이걸 찾는다면, "재미있는" 부분에서 매치돼요. 초보자 팁으로, 파이썬에서 str.find() 메서드를 써보세요. 코드: text = "정말 재미있는 코딩 세계예요"; pattern = "재미"; position = text.find(pattern); print(position) – 결과는 3(0부터 세면)이 나와요. 이걸 실행해 보시면 바로 느껴질 거예요. 하지만 이건 내장 함수라서, 직접 구현해야 할 때가 많아요. 왜 직접 짜야 하냐면, 코테에서 "O(nm) 시간 복잡도"를 요구하거든요. n은 문장 길이, m은 패턴 길이예요. brute force는 nm 비교를 하니, n=100만, m=100이면 1억 번 비교 – 느려요!

비교해 보자면, 단순 검색 vs. 알고리즘: 단순은 매번 처음부터 비교하지만, 스마트한 건 불필요한 비교를 건너뛰어요. 수치로 보면, 1MB 텍스트에서 패턴 찾을 때 brute force는 1초 걸릴 수 있지만, 고급 알고리즘은 0.1초로 줄어요. 실전 팁: VS Code에서 새 파일 만들어 위 코드 입력하고 F5 누르세요. 에러 나면 print("Hello")부터 테스트해 보세요. 이 섹션에서 얻는 건, 문자열 찾기 알고리즘이 코딩의 문을 여는 키라는 거예요. 다음으로, 가장 기본적인 brute force 방법을 자세히 파보죠. 이걸 알면 고급 기법이 왜 필요한지 이해가 쏙 될 거예요.

Brute Force: 간단하지만 느린 방법

Brute force, 한국어로 "무식한 힘" 방법이라고 해요. 영상에서 "한 칸씩 이동하며 비교"하는 장면처럼, 직관적이에요. 초보자분들을 위해 설명드리면, 문장을 배열로 보고, 패턴의 시작 위치를 0부터 n-m+1까지 하나씩 옮기면서 매번 모든 문자를 비교하는 거예요. 예: 문장 "abcde", 패턴 "bc"라면, 위치 0: a==b? No. 위치 1: b==b, c==c Yes. 위치 2: c==b? No. 이렇게요.

이 방법의 장점은 구현이 쉽다는 거예요. 코드로 보자면, for i in range(len(text) - len(pattern) + 1): if text[i:i+len(pattern)] == pattern: print(i). 파이썬에서 바로 써보세요. 영상처럼 "여기서 한번, 저기서 한번" 하며 모든 가능성을 체크하니, 놓치는 게 없어요. 하지만 단점도 커요. 비교 횟수가 n*m이라, 큰 데이터에서 느려요. 예를 들어, 1000자 문장과 10자 패턴이면 최대 9990번 비교 – 괜찮지만, 1억 자면 폭발해요.

개선 아이디어를 더해 볼게요. 영상에서 ASCII 코드로 숫자 변환해 합을 미리 계산하는 팁이 나와요. 쉽게 말하면, 패턴 "abc"는 a=97, b=98, c=99로 합 294예요. 문장의 3자 슬라이딩 윈도우 합이 294가 아니면 스킵! 이건 해싱(rabin-karp 스타일)의 기본이에요. 수치 비교: brute force 100% 비교 vs. 해싱 10%만 비교 – 10배 빨라요. 실제 예시: "banana"에서 "ana" 찾기. 위치 1: b-a-n sum=98+97+110=305 != a+n+a=97+110+97=304 No. 위치 2: a-n-a=304 Yes.

실전 팁: 이걸 C++로 구현해 보세요. string text = "banana"; string pat = "ana"; for(int i=0; i<=text.size()-pat.size(); i++) { bool match=true; for(int j=0; j<pat.size(); j++) if(text[i+j]!=pat[j]) {match=false; break;} if(match) cout<<i; } 컴파일 후 실행하면 위치 1,3 출력돼요. 주의: 오버플로우 피하세요. 대안으로, 자바의 String.indexOf() 써보지만, 직접 짜는 게 학습이에요. 왜 중요한가? 이 방법 알면, 왜 효율이 필요할지 깨달아요. 영상에서 "너무 쉽다" 하듯, 과소평가 말고 테스트해 보세요. 다음 섹션에서 KMP로 업그레이드할게요.

KMP 알고리즘: 스마트하게 문자열 찾기

KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 찾기의 고급 버전이에요. 영상에서 "접미사 분석으로 점프"하는 부분처럼, 패턴의 중복을 이용해 불필요한 백트래킹을 피해요. 초보자분들을 위해 설명드리면, 패턴 "abab"의 prefix table(부분 일치 테이블)을 미리 만들어요. 예: a b a b – 위치 0: '', 1: a (접두사 a와 접미사 a 매치, 값 1? 아니, 테이블 [0,0,1,2]).

테이블 만드는 법: 패턴 길이 m만큼 배열 pi[0..m-1], pi[0]=0. i=1부터, len=0 시작. 패턴[i]==패턴[len]이면 len++, pi[i]=len. 아니면 len=pi[len-1]로 백트랙. "abab" 예: i=1 b!=a, len=0, pi[1]=0. i=2 a==a (len=0->1), pi[2]=1. i=3 b==b (len=1->2), pi[3]=2. 이 테이블로 검색 시, 매치 실패해도 pi[j-1]만큼 점프해요. 시간 복잡도 O(n+m) – brute의 O(n*m)보다 훨씬 빨라요!

예시: 텍스트 "ababababc", 패턴 "abab". 테이블 [0,0,1,2]. 검색: i=0~3 매치, 위치 0. 실패 시 j=pi[3]=2부터 재시작 – "ab"부터. 위치 2: abab 매치. 위치 4: abab 매치. 위치 6: c 실패. 총 비교 적어요. 수치: n=100만, m=1000 brute 10억 vs KMP 100만1천 – 1000배 차이!

실전 팁: 파이썬 구현. def compute_pi(pat): m=len(pat); pi=[0]*m; j=0; for i in range(1,m): while j>0 and pat[i]!=pat[j]: j=pi[j-1]; if pat[i]==pat[j]: j+=1; pi[i]=j; return pi. 검색: def kmp(text, pat): pi=compute_pi(pat); n=len(text); m=len(pat); j=0; for i in range(n): while j>0 and text[i]!=pat[j]: j=pi[j-1]; if text[i]==pat[j]: j+=1; if j==m: print(i-m+1); j=pi[j-1]. "ababcabcabababd"에서 "abab" 하면 0,2,6 출력. 주의: 테이블 오류 시 디버깅으로 print(j) 추가. 대안: Boyer-Moore (역방향 검색, 더 빠를 수 있음). 왜 KMP? 대용량 데이터(로그 파일 분석)에서 필수예요. 영상처럼 "O(n+m)" 속도로 마스터하세요!