완전탐색 (Exhaustive Search) - 반복문을 활용한 접근

완전탐색은 가능한 모든 경우를 하나하나 확인하여 정답을 찾는 방법이다. 정답이 반드시 존재하고 경우의 수가 제한적인 경우라면 가장 확실한 해결책이 될 수 있다.

완전탐색 vs 브루트포스

완전탐색과 브루트포스는 모두 가능한 모든 해를 탐색한다는 공통점이 있지만, 약간의 뉘앙스 차이가 있습니다.

• 완전탐색: 체계적이고 논리적인 구조로 모든 해를 찾는 접근
• 브루트포스: 말 그대로 무식하게 모든 경우를 다 시도하는 방식

일반적으로 두 용어는 구분 없이 혼용되며, 실전에서는 동일한 의미로 다루는 경우가 많다.

1. 반복문을 활용한 완전탐색

1-1. 이중 반복문을 이용한 두 수의 합

두 수를 골라 합이 특정 값이 되는 쌍을 찾는 예시

public class TwoSumPairs {
    public static void twoSum(int[] arr, int target) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] + arr[j] == target) {
                    System.out.println("(" + arr[i] + ", " + arr[j] + ")");
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 7, 4, 9, 1};
        int target = 10;
        twoSum(arr, target);
    }
}

• 시간복잡도: O(n^2)
• 모든 두 수의 조합을 확인

1-2. 삼중 반복문을 이용한 세 수의 합

이번에는 세 수를 골라 합이 특정 값이 되는 조합을 찾는다.

public class ThreeSumPairs {
    public static void threeSum(int[] arr, int target) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (arr[i] + arr[j] + arr[k] == target) {
                        System.out.println("(" + arr[i] + ", " + arr[j] + ", " + arr[k] + ")");
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 7, 8};
        int target = 15;
        threeSum(arr, target);
    }
}

• 시간복잡도: O(n^3)
• 세 수의 조합을 모두 확인

2. 반복문 기반 완전탐색의 활용

2-1. 두 요소 선택

• 두 수를 선택하는 문제에서 자주 사용
• 예시: 두 수의 합, 가장 가까운 두 점

2-2. 세 요소 이상 선택

• 세 수의 합, 삼각형 조건 만족 여부 등을 판단할 때 사용
• 반복문이 세 겹 이상 필요

2-3. 격자형 문제

2차원 배열에서의 좌표 탐색에도 반복문 완전탐색이 활용된다.

public class NestedLoopExample {
    public static void main(String[] args) {
        int n = 5;
        int m = 5;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.println("Processing position: (" + i + ", " + j + ")");
            }
        }
    }
}

• 예시: 미로 탐색, 체스판 탐색

3. 완전탐색의 한계와 최적화 방법

1. 정렬을 활용한 탐색 범위 축소

• 데이터를 정렬한 후 조건을 만족하지 못할 경우 더 이상 탐색하지 않도록 설계
• 예: 투 포인터, 이진 탐색

2. 가지치기 (Pruning)

• 불필요한 경우의 수를 조기에 제거

if (현재값 > 목표값) {
    break;
}

3. 메모이제이션 (Memoization)

• 이미 계산한 값을 저장하여 반복 계산 방지
• 재귀 또는 동적 프로그래밍과 함께 활용