[Coding Test Grammar]완전탐색 (Java)

완전탐색(Brute-Force Search) 개념과 Java 예시

완전탐색(Brute-Force Search)은 가능한 모든 경우의 수를 하나하나 다 탐색하여 문제의 해를 찾는 방법입니다. 이 방식은 매우 단순하지만, 문제의 정답을 확실히 찾을 수 있다는 장점이 있습니다. 그러나 모든 경우의 수를 탐색하기 때문에, 경우에 따라 시간 복잡도가 매우 높아질 수 있습니다.

완전탐색의 기본 개념

완전탐색은 아래와 같은 문제에 사용됩니다:

• 모든 경우의 수를 다 조사해야 할 때: 예를 들어, 여러 선택지가 있을 때 그 중에서 가장 좋은 답을 찾기 위해 모든 경우를 다 시도하는 방법입니다.
• 문제의 입력 크기가 작을 때: 완전탐색은 경우의 수가 많아질수록 시간이 오래 걸리기 때문에, 작은 문제에서 주로 사용합니다.

완전탐색의 기본 절차

1. 모든 가능한 경우를 구한다.
2. 각 경우에 대해 조건을 확인한다.
3. 조건에 맞는 정답을 찾으면 멈추거나, 최적의 해를 찾을 때까지 계속한다.

Java 예시: 두 수의 합이 주어진 값을 만족하는 쌍 찾기

문제 설명

 

정수 배열이 주어졌을 때, 두 수의 합이 target 값이 되는 모든 쌍을 출력하는 완전탐색 알고리즘을 구현.

코드 구현

public class BruteForceExample {
    // 두 수의 합이 target이 되는 모든 쌍을 출력하는 메서드
    public static void findPairs(int[] arr, int target) {
        int n = arr.length;  // 배열의 길이
        
        // 완전탐색: 모든 두 숫자 쌍을 확인
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] + arr[j] == target) {
                    // 두 수의 합이 target과 일치하는 경우 출력
                    System.out.println(arr[i] + " + " + arr[j] + " = " + target);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {2, 7, 11, 15, 1, 8, 3};  // 예시 배열
        int target = 10;  // 찾고 싶은 합
        
        System.out.println("Target = " + target + "인 쌍을 찾습니다:");
        findPairs(numbers, target);
    }
}

코드 설명

1. 이중 반복문 사용:
   • 두 개의 반복문을 사용해 배열 내의 모든 두 숫자 쌍을 확인합니다. i는 첫 번째 숫자를, j는 두 번째 숫자를 나타냅니다.
2. 조건 확인:
   • 각 쌍의 합이 target 값과 같으면, 해당 쌍을 출력합니다.
3. 시간 복잡도:
   • 이 알고리즘의 시간 복잡도는 O(n²)입니다. 이는 배열의 모든 두 숫자 쌍을 비교하기 때문에 발생하는 시간 복잡도입니다.

실행 결과

예를 들어, 위 코드가 배열 {2, 7, 11, 15, 1, 8, 3}와 target = 10으로 실행되면 다음과 같은 결과를 얻을 수 있습니다: