4.3 Brute Force Search(완전 탐색)

4. String Search and Manipulations - 4.3 Brute Force Search

Brute Force Search

Brute force search is a simple algorithm that checks for a pattern in a string by comparing each character of the string with the first character of the pattern. If the first character matches, it then compares the next character of the string with the next character of the pattern and so on. If all the characters of the pattern match, then the pattern is found. If the first character does not match, then the algorithm compares the second character of the string with the first character of the pattern and so on.

완전 탐색

완전 탐색은 문자열의 각 문자를 패턴의 첫 번째 문자와 비교하여 문자열에서 패턴을 확인하는 간단한 알고리즘입니다. 첫 번째 문자가 일치하면 문자열의 다음 문자를 패턴의 다음 문자와 비교하는 방식으로 패턴을 찾습니다. 패턴의 모든 문자가 일치하면 패턴을 찾습니다. 첫 번째 문자가 일치하지 않으면 알고리즘은 문자열의 두 번째 문자를 패턴의 첫 번째 문자와 비교하는 등의 방식으로 비교합니다.

 

 

완전 탐색(Brute Force Search)은 가장 기본적인 검색 알고리즘 중 하나로, 모든 가능성을 검토하는 방식을 말합니다. 이 알고리즘은 문자열 검색에서도 사용되며, 이 경우에는 대상 문자열을 처음부터 끝까지 순차적으로 검사하면서 패턴과 일치하는 부분을 찾는 방식을 사용합니다.

 

완전 탐색 문자열 검색 알고리즘의 작동 방식은 다음과 같습니다

1. 대상 문자열의 첫 문자부터 시작하여, 검색하려는 패턴의 첫 문자와 비교합니다.
2. 일치하면, 대상 문자열의 다음 문자와 패턴의 다음 문자를 비교합니다.
3. 이를 패턴의 끝까지 반복합니다. 만약 패턴의 모든 문자가 대상 문자열에서 연속적으로 일치한다면, 그 위치에서 패턴이 발견된 것입니다.
4. 만약 어느 지점에서 불일치가 발생하면, 대상 문자열에서 다음 위치로 이동하고, 패턴과의 비교를 처음부터 다시 시작합니다.
5. 대상 문자열의 끝까지 이 과정을 반복합니다.

 

def brute_force_search(main_string, pattern):
    len_main = len(main_string)  # 대상 문자열의 길이 계산
    len_pattern = len(pattern)  # 패턴 문자열의 길이 계산
    
    # 대상 문자열을 처음부터 끝까지 순회. 패턴 문자열의 길이를 고려하여 불필요한 검사를 줄임
    for i in range(len_main - len_pattern + 1):
        j = 0  # 패턴 문자열의 인덱스 초기화
        
        # 패턴 문자열의 길이만큼 대상 문자열과 패턴 문자열을 비교
        while(j < len_pattern):
            
            # 대상 문자열과 패턴 문자열이 일치하지 않으면 루프를 빠져나감
            if main_string[i + j] != pattern[j]:
                break
            
            j += 1  # 다음 문자를 비교하기 위해 인덱스 증가
            
        # 패턴 문자열의 모든 문자가 대상 문자열과 일치하면, 그 위치를 반환
        if j == len_pattern:
            return i
        
    # 패턴 문자열을 찾지 못했으면 -1 반환
    return -1

 

 

활용

 

1. 텍스트 검색

컴퓨터에서 특정 문자열이 어디에 위치하는지 찾거나, 특정 단어나 문구가 문서 내에 몇 번 등장하는지 찾을 때 사용됩니다.

 

2. 패턴 매칭

특정 패턴을 찾는다거나, DNA 서열 같은 복잡한 문자열에서 특정 서열을 찾는데 사용될 수 있습니다.

 

3. 암호학

브루트 포스 알고리즘은 암호를 해독하는 방법 중 하나로 사용됩니다.

 

 

 

 

장점은 역시 구현이 간단하고, 모든 경우의 수를 다루므로 항상 정확한 결과를 보여줍니다.

단점은 비효율적 입니다. 모든 경우의 수를 검사하기 때문에 데이터의 크기가 클수록 처리 시간이 길어집니다. 따라서 데이터가 크거나 복잡한 경우에는 다른 알고리즘을 사용하는 것이 더 효율적입니다.