[Java] 완전 탐색 알고리즘 (Brute Force)

가능한 모든 경우의 수를 전부 시도해보는 알고리즘

✅ 장점 : 정확성 100% 보장

❌ 단점 : 경우의 수가 많으면 시간이 오래 걸림

---

언제 사용하는가?

• 경우의 수가 충분히 작을 때 (보통 1,000만 이하)
• 더 효율적인 알고리즘이 떠오르지 않을 때
• 정답을 먼저 구한 뒤 최적화할 때

---

시간복잡도 기준

• 반복문 1개 : O(n) → n이 1억이면 약 0.1초
• 반복문 2중 : O(n²) → n이 1만이면 약 0.1초
• 반복문 3중 : O(n³) → n이 500이면 약 0.1초

---

예제 1) 3자리 영문 소문자 비밀번호

3자리 영문 소문자 (a ~ z)를 완전 탐색으로 모두 출력하라. 총 몇 가지인지도 출력하라.

코드

public class BruteForcePractice {
    static void main(String[] args) {
        int count = 0;
        for (char i = 'a'; i <= 'z'; i++) {
            for (char j = 'a'; j <= 'z'; j++) {
                for (char k = 'a'; k <= 'z'; k++) {
                    count++;
                    if (count <= 3) {
                        System.out.println("" + i + j + k);
                    } else if (count == 4) {
                        System.out.println("...");
                    } else if (count == 17576) {
                        System.out.println("" + i + j + k);
                    }
                }
            }
        }
        System.out.println("총 : " + count + "가지");
    }
}

출력

aaa
aab
aac
...
zzz
총 : 17576가지

동작 원리

완전탐색은 가능한 모든 경우의 수를 다 구하는 방법이다.
3자리 비밀번호를 구해야 하므로 반복문을 3중으로 중첩해서 처음(a)부터 끝(z)까지 모든 경우를 순회하면 된다.

---

예제 2) 두 수의 합

배열 {1, 7, 11, 15, 3, 6} 에서 두 수의 합이 9가 되는 쌍을 찾아라.

코드

int[] arr = {1, 7, 11, 15, 3, 6};
int sumCount = 0;
for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] + arr[j] == 9) {
            sumCount++;
            System.out.println(arr[i] + " + " + arr[j] + " = " + (arr[i] + arr[j]));
        }
    }
}
System.out.println("총 : " + sumCount + "가지");

출력

3 + 6 = 9
총 : 1가지

동작 원리

두 수의 합이 9가 되는 쌍을 찾아야 하기에 반복문은 2중으로 사용하였다.
j를 i+1로 설정한 이유는 j가 항상 i보다 크기 때문에 (3, 6)과 (6, 3) 같이 순서만 다른 중복 쌍이 생기지 않는다.

---

예제 3) 두 수의 차이

배열 {3, 10, 2, 8, 5, 1} 에서 두 수의 차이가 가장 큰 쌍을 찾아라.

코드

int[] arr2 = {3, 10, 2, 8, 5, 1};
int answer = Integer.MIN_VALUE;
int indexI = 0;
int indexJ = 0;

for (int i = 0; i < arr2.length; i++) {
    for (int j = 0; j < arr2.length; j++) {
        if (i != j && arr2[i] - arr2[j] > answer) {
            indexI = i;
            indexJ = j;
            answer = arr2[i] - arr2[j];
        }
    }
}
System.out.println("두 수의 차이가 가장 큰 쌍 : "
        + arr2[indexI] + " - " + arr2[indexJ] + " = " + answer);

출력

두 수의 차이가 가장 큰 쌍 : 10 - 1 = 9

동작 원리

두 수의 차이가 가장 큰 쌍을 찾아야 하므로 2중 반복문으로 처음부터 끝까지 두 수의 차이값을 구한다. 현재 차이값이 answer보다 크면 answer를 현재값으로 갱신하고 인덱스도 저장한다.

이번엔 안쪽 변수 j의 초기값을 0으로 한 이유는 뺄셈의 경우 숫자 위치에 따라 값이 완전히 달라지기 때문이다. 예를 들어 3 - 10과 10 - 3은 완전히 다른 값이다.