알고리즘, Search, Naive String Search

Naive String Search는 문자열 내에서 특정 패턴을 찾기 위한 단순하고 직관적인 검색 알고리즘입니다. 이 알고리즘은 텍스트의 각 위치에서 패턴이 일치하는지 확인하는 방식으로 동작합니다. 이 과정은 매우 직관적이지만, 비효율적일 수 있습니다. 특히 긴 텍스트와 패턴의 경우 더 효율적인 알고리즘을 사용하는 것이 좋습니다.

기본 개념

Naive String Search의 기본 개념은 다음과 같습니다:

1. 텍스트의 각 위치에서 패턴 확인: 텍스트의 첫 번째 문자부터 시작하여, 패턴의 길이만큼의 문자가 패턴과 일치하는지 확인합니다.
2. 일치 여부 판단: 일치하는 경우 해당 위치를 기록하고, 일치하지 않는 경우 다음 위치로 이동하여 다시 확인합니다.
3. 반복: 텍스트의 끝까지 이 과정을 반복합니다.

예제

다음은 자바스크립트로 구현한 Naive String Search의 예제입니다.

function naiveStringSearch(longer, shorter) {
  let cnt = 0;

  for (let i = 0; i < longer.length; i++) {
    for (let j = 0; j < shorter.length; j++) {
      if (shorter[j] !== longer[i + j]) break;
      if (j === shorter.length - 1) cnt++;
    }
  }

  return cnt;
}

naiveStringSearch('omaomggfaomg', 'omg'); // 1

시간 복잡도

Naive String Search의 시간 복잡도는 다음과 같습니다:

• 최악의 경우 시간 복잡도: O(n * m)
  • 여기서 n은 텍스트의 길이, m은 패턴의 길이입니다.

특징

1. 단순함: 구현이 매우 간단하고 직관적입니다.
2. 비교 기반 검색: 패턴의 각 문자와 텍스트의 각 위치를 비교합니다.
3. 정렬 필요 없음: 텍스트가 정렬되어 있을 필요가 없습니다.
4. 제자리 검색: 추가적인 메모리 공간을 거의 사용하지 않습니다.

장점

1. 간단한 구현: 알고리즘이 매우 직관적이고 이해하기 쉽습니다.
2. 보편적 사용: 텍스트가 정렬되어 있을 필요가 없어 다양한 경우에 사용할 수 있습니다.

단점

1. 비효율성: 긴 텍스트와 패턴에 대해서는 매우 비효율적입니다.
2. 시간 복잡도: 최악의 경우 시간 복잡도가 O(n * m)으로, 더 효율적인 알고리즘에 비해 느릴 수 있습니다.

개선된 알고리즘

긴 텍스트나 패턴을 다룰 때 더 효율적인 문자열 검색 알고리즘이 필요할 수 있습니다. 다음과 같은 알고리즘들이 있습니다:

1. Knuth-Morris-Pratt (KMP) 알고리즘: 패턴 내에서의 부분 일치를 이용하여 검색 속도를 향상시킵니다.
2. Boyer-Moore 알고리즘: 패턴을 뒤에서 앞으로 검색하여 불일치가 발생했을 때 더 큰 폭으로 검색 범위를 이동합니다.
3. Rabin-Karp 알고리즘: 해시 함수를 사용하여 패턴과 텍스트의 서브스트링을 비교합니다.

결론

Naive String Search는 단순하고 구현이 쉬운 문자열 검색 알고리즘입니다. 짧은 텍스트와 패턴의 경우 사용하기에 적합하지만, 긴 텍스트와 패턴을 다룰 때는 더 효율적인 알고리즘을 사용하는 것이 좋습니다. 효율적인 문자열 검색을 위해 KMP, Boyer-Moore, Rabin-Karp와 같은 알고리즘을 공부하고 사용하는 것을 권장합니다.