브루트포스(Brute Force)

1. 브루트포스(Brute Force)란

- 문제의 가능한 모든 경우의 수를 하나씩 전부 시도(완전 탐색)하여 정답을 찾는 기법이다.

- 최적화된 해법이 존재하지 않거나 문제의 크기가 작아 모든 경우를 탐색해도 충분할 때 사용된다.

- 경우의 수가 많아지면 시간복잡도가 기하급수적으로 증가하므로 다른 방식을 찾아야한다.

- 재귀 또는 반복을 통해 구현한다.

 

2. 브루트포스 구현

- 주어진 문자열의 모든 부분 문자열을 출력하는 문제

2-1. 모든 부분 문자열 구하기(반복)

- 이중 반복문을 사용하여 시작 인덱스와 끝 인덱스를 결정하고 그 구간의 부분 문자열을 출력하는 방식이다.

public class AllSubstringsIterative {
    public static void main(String[] args) {
        // 예제 데이터
        String s = "abc";

        // 시작 인덱스: 0부터 s.length()-1 까지
        for(int i = 0; i < s.length(); i++) {
            // 끝 인덱스: i+1부터 s.length()까지 
            for(int j = i+1; j <= s.length(); j++) {
            	// 출력: a, ab, abc, b, bc, c
                System.out.println(s.substring(i, j));
            }
        }
    }
}

 

2-2. 모든 부분 문자열 구하기(재귀)

- 재귀를 이용해 현재 인덱스에서 시작하는 부분 문자열을 길이를 1씩 늘려가며 출력하고 시작 인덱스를 변경하는 방식이다.

public class AllSubstringsRecursive {
    public static void printSubstrings(String s, int start, int end) {
        // 기저 조건
        if(start == s.length()) {
            return;
        }

        // 끝 인덱스가 문자열 길이보다 크면 
        if(end > s.length()) {
            printSubstrings(s, start+1, start+2);
            return;
        }

        // 출력: a, ab, abc, b, bc, c
        System.out.println(s.substring(start, end));

        // 현재 시작 인덱스에서 끝 인덱스를 한 칸 늘려서 재귀 호출
        printSubstrings(s, start, end + 1);
    }

    public static void main(String[] args) {
        String s = "abc";
        printSubstrings(s, 0, 1);
    }
}