브루트-포스 법

선형 검색과 이진 검색 두가지 방식은 대게 숫자와 같은 요소들을 검색하는데 편리한 방식이었습니다. 하지만 문자열에 이 방식들을 대입하기엔 쉽지 않습니다. 그래서 문자열들을 검색할 수 있는 몇 가지 방법들을 소개하려고 합니다.

---

1. 브루트 포스 법

브루트 포스 법(Brute Force Method)는 마치 선형 검색처럼 모든 요소에 대해 일일히 비교하는 방식입니다.

한 문자열에서 'aba'라는 문자열을 찾으려고 한다면 다음과 같이 나타낼 수 있습니다.

 

우선 문자열의 인덱스 0과 키의 인덱스 0을 비교합니다. 이때 그 요소가 일치했다면 그 다음 인덱스와 키의 두번째 인덱스를 비교합니다.

 

비교한 결과가 일치했다면 3번째 인덱스를 다시 검사하겠지만 여기서는 불일치했기 때문에 키를 이동시켜 원 문자열 배열의 1번 인덱스와 키의 0번 인덱스를 비교합니다.

 

이런식으로 키와 원 문자열을 끝까지 비교했을 때 완전히 동일하다면 검색에 성공한 것입니다.

즉, 브루트 포스 법은 선형 검색처럼 모든 요소를 하나씩 전부 검사하는 방식이라고 할 수 있습니다.

 

 

2. 브루트 포스 법 구현

export const bruteForceMethod = (str, key) => {
    //문자열을 검사할 인덱스
    let strIndex = 0;

    //str[strIndex]가 유효할 동안 검사 반복
    //undefined === false이므로, 문자열 끝을 넘어서면 반복 종료
    while (str[strIndex]) {
        //문자열과 비교할 키 문자열 인덱스
        let keyIndex = 0;

        //현재 인덱스와 첫 키 인덱스가 같으면
        if (str[strIndex] === key[keyIndex]) {
            //문자열의 현재 인덱스(시작위치) 저장
            let currentIndex = strIndex;

           //그 이후로 다음 인덱스를 계속해서 비교
            while (str[strIndex] === key[keyIndex]) {
                //키 인덱스 끝까지 갔을 때 검색에 성공
                if (keyIndex === key.length - 1) {
                    return console.log("검색 성공, 인덱스: " + currentIndex);
                }
                strIndex++;
                keyIndex++;
            }
        }
        strIndex++;
    }

    return console.log("검색 실패");
};

import {bruteForceMethod} from './study-code/search/brute-force-method.js';

const str = ('theworldserieschampion');

bruteForceMethod(str, 'champ');

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/search/brute-force-method.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록