Brute-Force법

오늘 백준 Brute-force 알고리즘에 관련한 문제를 풀다 한번 정리 하고 싶다는 생각이 들어 글을 작성한다.

아래 글은 reference에도 남기겠지만, 'Do it! 자료구조와 함께 배우는 알고리즘 입문'을 정리한 글이다.

 

1. 브루트-포스(Brute-force)법

완전탐색 알고리즘이다. 모든 경우의 수를 탐색하면서, 요구 조건에 충족되는 결과만을 가져 온다.

선형 검색을 확장한 알고리즘이다.

 

예시로 문자열을 검색하는 알고리즘을 들어 보자.

문자열에 특정 문자열이 들어 있는지 조사하고, 들어 있따면 그 위치 index 값을 반환하는 프로그램을 작성한다 생각해보자.

텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트포스법을 이용해 검색하는 순서는 다음과 같다.

(1) 문자열의 첫 문자 'A'부터 시작하는 3개의 문자와 패턴 "ABC"가 일치하는지 검사한다. C가 다르다.

(2) 패턴을 한칸 뒤로 옮겨 다시 검사한다. 처음부터 다르다.

(3) 다시 패턴을 한칸 뒤로 옮긴다.  다시 검사한다.

 

즉, 문자열의 인덱스 0번부터 패턴 "ABC"와 한 글자씩 일치하는지 확인하고, 일치하지 않는 순간 index를 1 증가시켜 다시 패턴 "ABC"와 한 글자 씩 비교한다. 셋 모두가 같으면 해당 인덱스를 출력한다.

이를 코드로 작성해본다면 다음과 같다.

 

import java.util.Scanner;

public class BruteForceMatch {
    public static int matching(String text, String pattern){
        int textIndex = 0;
        int patternIndex = 0;
        // 인덱스가 문자길이랑 같아지면 탈출.
        while (textIndex != text.length() && patternIndex != pattern.length()){
            if (text.charAt(textIndex) == pattern.charAt(patternIndex)){
                textIndex++;
                patternIndex++;
            } else {
                textIndex = textIndex - patternIndex + 1;
                patternIndex = 0;
            }
        }
        // 검색 성공
        if (patternIndex == pattern.length()) return textIndex - patternIndex;
        // 검색 실패
        return -1;
    }
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        // 텍스트용 문자열
        System.out.println("텍스트를 입력하세요 : ");
        String text = sc.next();
        // 검사할 패턴용 문자열
        System.out.println("패턴을 입력하세요 : ");
        String pattern = sc.next();
        // 텍스트용 문자열에서 패턴용 문자열을 검색
        int index = matching(text, pattern);
        if (index == -1) System.out.println("텍스트에 패턴이 없습니다.");
        else {
            // 패턴이 있을때, 길이와 인덱스 출력
            
            // length = index + pattern 길이 
            int length = 0;
            for (int i = 0; i < index ; i++) {
                length += text.substring(i, i + 1).getBytes().length;
            }
            length += pattern.length();

            System.out.println((index + 1) + "번째 문자부터 일치합니다.");
            System.out.println("텍스트 : " + text);
            System.out.printf(String.format("패턴 : %%%ds\n", length), pattern);
            System.out.println(length);
//            System.out.printf("패턴 : %5s\n", pattern);
        }
    }
}

 

* String.format()에 관련하여

 : 문자열의 형식을 설정해주는 메소드로, 형식에 맞게 조정하여 결과값을 String 타입으로 return한다.

public static String format(String format, Object... args);

위와 같은 형식으로, String.format(형식, 수 or 문자열) 을 넣어준다. String.format의 형식에서 %%는 %로 변환된다고 한다. 그러면 위의 코드가 이해 될 수 있을 것이다. 

Length가 5일때, 아래 코드는 동일한 코드가 되는 것이다.

System.out.printf(String.format("패턴 : %%%ds\n", length), pattern);
System.out.printf("패턴 : %5s\n", pattern);

https://blog.jiniworld.me/68#a03

[Java] String.format 을 이용한 문자열 형식 설정하기

 

* getBytes() 메소드란?

String(문자열)을 바이트 순서대로 부호화(default charset으로 인코딩) 하여 byte 배열로 반환해주는 것이다.

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

        String word = sc.nextLine();
        for (int i = 0; i < word.length(); i++) {
            System.out.println(Arrays.toString(word.substring(i,i+1).getBytes()));
        }
    }
}

 

위의 코드로 확인해 보니, 영어와 숫자의 경우 String.getBytes()는 String을 문자 하나 마다의 아스키코드를 배열로 반환하는 것을 확인 할 수 있었다. 하지만 한글과 한자의 경우 3바이트로 표현 하기 때문에, 한글/한자 한 글자 당 3바이트 배열로 출력하게 된다.

 

그냥 length = index + pattern.length()로 하면 되는거 아닌가. 무슨 의미가 있는지 모르겠다... 한글과 한자 구분을 위한 것인가 ...?(나의 한계) 이해할 수가 없다.

 

 

Reference :

 'Do it! 자료구조와 함께 배우는 알고리즘 입문', 이지스퍼블리싱

https://blog.jiniworld.me/68#a03

https://ssdragon.tistory.com/32