본문 바로가기
카테고리 없음

Do it! 알고리즘 입문 자바 - Week 7

migi111 2026. 2. 14. 23:39
이번에는 문자열 알고리즘에 대해 학습할 예정이다.
다양한 기법에 대해 알아보자

 

브루트 - 포스법

문자열 검색의 기초

 

문자열 검색: 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어 있다면 그 위치를 찾아내는 것이다.

 

ex) STRING , KING 에서 IN을 검색하면 문자열 검색에 성공한다.
      QUEEN 에서 IN을 검색하면 문자열 검색에 실패한다.

 

검색할 문자열을 패턴이라 하고 문자열 원본을 텍스트라고 하자!

 

 

  • ABABCDRFGHA 에서 패턴 ABC를 찾아보자
    • '패턴'이 텍스트의 첫 문자와 겹치도록 두 줄로 놓고 1번째 문자부터
      순서대로 일치하는지 검사한다.
    • 문자가 일치하면 계속해서 패턴과 텍스트의 문자를 검사한다.
    • 그러다가 다른 문자가 나타나면 검사를 중단한다.
    • 검사할 텍스트의 위치를 1칸 뒤로 이동한다.

 

검사 위치를 텍스트의 2번째 위치까지 했음에도 불구하고 
이미 검사를 진행한 위치를 기억하지 못하므로 브루트-포스법의 효율은 좋지 않다고 할 수 있다.

 

import java.util.Scanner;
import java.util.SimpleTimeZone;

public class BFmatch {
    static int bfMatch(String txt, String pat){
        int pt = 0; //텍스트 커서
        int pp = 0; //패턴 커서

        while(pt != txt.length() && pp != pat.length()){
            if(txt.charAt(pt) == pat.charAt(pp)){
                pt++;
                pp++;
            }
            else{
                pt = pt - pp + 1;
                pp = 0;
            }
        }
        if(pp == pat.length()){
            return pt - pp;
        }
        return -1;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        System.out.print("텍스트 : ");
        String s1 = sc.next();

        System.out.print("패턴 : ");
        String s2 = sc.next();

        int idx = bfMatch(s1, s2);

        if(idx == -1){
            System.out.println("텍스트에 패턴이 없습니다.");
        }else{ //일치하는 문자 바로 앞까지의 길이를 구한다.
            int len = 0;
            for(int i = 0; i < idx; i++){
                len += s1.substring(i, i+1).getBytes().length;
            }
            len += s2.length();

            System.out.println((idx+1) + "번째 문자부터 일치합니다.");
            System.out.println("텍스트 : " + s1);
            System.out.printf(String.format("패턴 : %%%ds\n", len), s2);
        }
    }
}

 

  • String.indexOf 메서드
    • 이진 검색 메서드 binarySearch 처럼 문자열 검색 메서드가 있다.
      java.lang.String 클래스에 선언되어 있는 메서드이다.
    • str이 포함되어 있는지 검색한다! 
      • indexOf(String str): 모든 문자열에 대해 검색한다.
      • indexOf(String str, int fromIndex): fromIndex부터의 문자열에 대해서 검색한다.

KMP법

브루트-포스법과 다르게 중간 검사 결과를 효율적으로 사용하는 알고리즘이다.

APPLE에서 APP이라는 패턴을 검색할 때 'A'를 찾은 다음에 텍스트의 'P'를 찾으려면

패턴 APP 의 'A'부터 다시 검사한다. 이렇게 하면 비효율적이다.

 

KMP는 검사했던 위치 결과를 버리지 않고 활용한다.

패턴을 최소 횟수로 옮겨 알고리즘의 효율을 높인다.

 

 

그림처럼 이미 검사를 마친 부분을 제외하고 일치하는지 검사한다.

몇 번째 문자부터 다시 검색할 지 찾아서 시작하는 것은 효율적이지 못하다.

따라서 이를 위해 표를 만들어 이 문제를 해결한다.

 

KMP표는 브루트-포스법보다 복잡하고 성능이 별로라 실제 프로그램에서 사용하지 않는다...

 

Boyer - Moore 법

실제 문자열 검색에 널리 사용하는 알고리즘이다.

패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서
일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다.

 

 

이 알고리즘도 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표(건너뛰기 표)를 만들어야 한다.

패턴의 크기가 n 일 때

  • 패턴에 들어 있지 않은 문자를 만난 경우
    • 패턴을 옮길 크기는 n 이다.
  • 패턴에 들어 있는 문자를 만난 경우
    • 패턴에 들어 있는 문자가 패턴에서 마지막에 나오는 위치의 인덱스가 k이면
      n - k - 1 칸 옮긴다. ex) A는 패턴의 두 곳에 들어있으므로 4 - 2 - 1 = 1 칸 옮긴다.
    • 같은 문자가 중복해서 들어있지 않으면 n 만큼 옮긴다. (C는 1개만 패턴에 들어있다.)
import java.util.Scanner;

public class BMmatch {
    static int bmmatch(String txt, String pat) {
        int pt;
        int pp;
        int textLen = txt.length();
        int patLen = pat.length();
        int[] skip = new int[Character.MAX_VALUE + 1];

        for(pt = 0; pt <= Character.MAX_VALUE; pt++){
            skip[pt] = patLen;
        }
        for(pt = 0; pt < patLen; pt++){
            skip[pat.charAt(pt)] = patLen - pt - 1;
        }

        while(pt < textLen){
            pp = patLen - 1;

            while(txt.charAt(pt) == pat.charAt(pp)){
                if(pp == 0){
                    return pt;
                }
                pp--;
                pt--;
            }
            pt += (skip[txt.charAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp;
        }
        return -1;
    }
}

 

정리

1. Brute-Force (단순 비교)

"가장 멍청한 방법이 아니라, 대부분의 경우 가장 빠른 방법입니다."

놀랍게도 Java의 java.lang.String.indexOf() 메서드는 기본적으로 Brute-Force 방식을 사용합니다. (OpenJDK 구현 기준)

  • 실전 사용처:
    • 웹 개발, 앱 개발 일반: 사용자 이름, 이메일 주소, 짧은 JSON 파싱 등 우리가 다루는 데이터의 90%는 길이가 매우 짧습니다.
    • 표준 라이브러리: 짧은 문자열에서는 복잡한 알고리즘을 위한 '전처리 과정(테이블 생성)' 비용이 검색 시간보다 더 큽니다.
    • CPU 최적화: 단순 비교는 메모리 접근 패턴이 규칙적이라 CPU 캐시 적중률(Cache Hit)이 높고, 최신 CPU의 SIMD 명령어(AVX 등) 최적화를 받기 유리합니다.

결론: 문자열 길이가 수천 자 이하라면 Brute-Force가 가장 효율적입니다.

2. KMP (Knuth-Morris-Pratt)

"데이터를 되돌아갈 수 없는 상황에서 빛을 발합니다."

KMP의 핵심은 검색에 실패했을 때, 본문(Text)의 포인터를 뒤로 돌리지 않는다는 점입니다. 이 특성 때문에 특수한 환경에서 사용됩니다.

  • 실전 사용처:
    • 스트리밍 데이터: 네트워크 패킷 감청이나 로그 분석처럼 데이터가 끊임없이 흘러들어오고, 지나간 데이터를 다시 메모리에 올리기 힘든 경우에 사용합니다.
    • 바이오인포매틱스 (DNA 분석): DNA 염기서열(A, G, C, T)처럼 사용되는 문자의 종류는 적고 패턴의 반복이 심한 경우, Brute-Force는 최악의 성능을 내지만 KMP는 안정적입니다.
    • 사이버 보안 (WAF/IPS): 들어오는 트래픽에서 악성 코드 패턴(Signature)을 실시간으로 감지할 때 유용합니다.

3. Boyer-Moore (보이어-무어)

"Ctrl+F의 왕, 긴 글일수록 압도적으로 빠릅니다."

실무에서 대용량 텍스트 검색에 가장 많이 쓰이는 알고리즘의 기반입니다. 패턴의 뒷부분부터 문자를 비교하며 불일치 시 최대한 많이 건너뛰는(Skip) 방식입니다.

  • 실전 사용처:
    • 텍스트 에디터/IDE: 메모장, VS Code, IntelliJ 등의 "찾기(Ctrl+F)" 기능은 대부분 Boyer-Moore 혹은 그 변형(Boyer-Moore-Horspool)을 사용합니다.
    • grep (리눅스 명령어): 대용량 로그 파일에서 특정 문자열을 찾을 때 사용하는 GNU grep은 Boyer-Moore 방식을 고도로 최적화하여 사용합니다.
    • 데이터베이스 & 검색 엔진: 전체 텍스트 검색(Full-text search)의 일부 단계에서 원문 매칭을 빠르게 수행할 때 활용됩니다.

 

제미나이에 검색해서 활용 방법까지 살펴보았다. 실제로 개발하면서 구현할 일은 드물어서 가볍게 살펴봤지만

자바 메서드나 원리를 잘 체득해야 유용하게 사용할 수 있을 거 같다.

 

 

 

티스토리툴바