2. Naive 알고리즘 (고지식한 탐색 알고리즘)

Reference:
- 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어
- 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님
- https://inuplace.tistory.com/314 / 이누의 개발성장기

고지식한 탐색 알고리즘 (Naive Search or Brute Force Search Algorithm)

: 본문의 앞에서부터 끝까지 차근차근 탐색하는 알고리즘

 

본문 : 'ABCABACDC'

패턴 : 'BA'

 

=> 이 알고리즘은 이름 그대로 요령 부리지 않고 우직하게 일하는 일꾼처럼 동작한다

 

본문 길이 : N

패턴 길이 : M

 

• 패턴을 찾기 위해 최악의 경우 N x M 번의 비교를 수행 => 굉장히... 느림
• 일치하는 경우 해당 경우의 끝나는 값에 1을 표기한다
• 1의 갯수가 정답의 갯수가 될 것이다
• 시간복잡도 : O(MN), for문 2번
• 공간복잡도 : O(N) (or O(1)), 출력사이즈

---

고지식한 탐색 알고리즘 예제

int naivematch(char T[], int n, char P[], int m, int output[]) {
    int i, j, k; 
    
    for (i=1; i<=n; i++) output[i] = 0; // output 초기화
    
    for (i=1; i<n-m+1; i++) {
        for (j=i, k=1; k<=m; j++, k++) 
        // j를 피검색 대상 문자열의 인덱스, k를 검색 대상 문자열의 인덱스로 활용한다.
            if (T[j] != P[k]) break;
        if (k == m+1) output[j-1] = 1; 
        // for문을 다 돌았을 때 k가 m+1이 된 것은 다 매칭되었다는 것. 
        // j-1이 매칭된 마지막 문자이므로 1로 매칭여부 표시
    }
}