나이브 패턴 검색(Naïve Pattern Search) 알고리즘 완벽 정리: 개념부터 C++ 구현까지

나이브 패턴 검색(Naïve Pattern Search)이란?

나이브 패턴 검색은 여러 문자열 패턴 검색 알고리즘 중 가장 단순하고 직관적인 방법입니다. 주 문자열(텍스트)의 처음부터 끝까지 한 칸씩 이동하며, 각 위치에서 패턴의 문자들을 하나하나 대조해 일치 여부를 확인합니다.

이 알고리즘은 다음과 같은 특징을 가집니다.

전처리 과정이 필요 없습니다. KMP, 보이어-무어 같은 알고리즘과 달리 별도의 사전 준비 단계가 없습니다.
구현이 매우 간단합니다. 중첩 반복문만으로 손쉽게 작성할 수 있습니다.
추가 메모리를 사용하지 않습니다. 탐색 과정에서 별도의 저장 공간이 필요하지 않습니다.
짧은 텍스트에 적합합니다. 문자열이 길어지면 성능이 크게 떨어질 수 있습니다.

시간 복잡도는 O(m×n)입니다. 여기서 m은 패턴의 길이, n은 주 문자열의 길이를 의미합니다. 최악의 경우 모든 시작 위치에서 패턴 전체를 비교해야 하므로, 긴 텍스트에서는 비효율적일 수 있다는 점을 유의해야 합니다.

입력 및 출력 예시

입력:
주 문자열: "ABAAABCDBBABCDDEBCABC", 패턴: "ABC"

출력:
패턴이 발견된 위치: 4
패턴이 발견된 위치: 10
패턴이 발견된 위치: 18

알고리즘 동작 원리

함수 호출 형태는 다음과 같습니다.

naivePatternSearch(pattern, text)

입력 − 텍스트(주 문자열)와 패턴

출력 − 텍스트 안에서 패턴이 나타나는 위치들

시작
    patLen ← 패턴의 길이
    strLen ← 문자열의 길이

    for i ← 0 to (strLen − patLen):
        for j ← 0 to patLen:
            if text[i+j] ≠ pattern[j]:
                반복문 탈출

        if j == patLen:
            위치 i에서 패턴이 발견되었음을 출력
종료

핵심 아이디어는 간단합니다. 텍스트의 인덱스 0부터 (n − m)까지 각 위치 i에 대해 패턴의 첫 문자부터 끝 문자까지 순서대로 비교합니다. 중간에 한 문자라도 일치하지 않으면 즉시 다음 위치로 넘어가고, 모든 문자가 일치하면(j가 patLen에 도달하면) 해당 위치를 결과에 기록합니다.

C++ 구현 예제

위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.

#include<iostream>
using namespace std;

void naivePatternSearch(string mainString, string pattern, int array[], int *index) {
    int patLen = pattern.size();
    int strLen = mainString.size();

    for(int i = 0; i<=(strLen - patLen); i++) {
        int j;
        for(j = 0; j<patLen; j++) {      // 패턴의 각 문자가 일치하는지 검사
            if(mainString[i+j] != pattern[j])
                break;
        }

        if(j == patLen) {   // 패턴을 찾은 경우 위치를 배열에 저장
            (*index)++;
            array[(*index)] = i;
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;
    naivePatternSearch(mainString, pattern, locArray, &index);

    for(int i = 0; i <= index; i++) {
        cout << "Pattern found at position: " << locArray[i]<<endl;
    }
}

실행 결과

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

주 문자열 "ABAAABCDBBABCDDEBCABC"에서 패턴 "ABC"는 인덱스 4, 10, 18의 세 위치에서 발견되며, 프로그램은 이를 차례대로 출력합니다.

마무리

나이브 패턴 검색은 단순하지만 O(m×n)의 시간 복잡도 때문에 대용량 텍스트에는 부적합합니다. 실무에서는 KMP, 보이어-무어, 라빈-카프 같은 알고리즘이 더 나은 성능을 제공합니다. 그러나 알고리즘의 기본기를 다지고 다른 패턴 검색 기법과 비교하는 출발점으로는 가장 좋은 학습 대상이라 할 수 있습니다.