완전 탐색 - 3. 완전 탐색을 이용한 대표적인 문제

3. 완전 탐색을 이용한 대표적인 문제

완전 탐색(Brute Force)은 모든 경우의 수를 확인하여 정답을 찾는 방식이므로 다양한 문제에 적용될 수 있습니다.
대표적인 문제 유형과 실전 예제를 살펴보겠습니다.

---

3.1 브루트 포스로 해결할 수 있는 문제 유형

완전 탐색이 적절한 경우는 보통 경우의 수가 적거나, 모든 경우를 반드시 확인해야 하는 문제입니다.
대표적인 문제 유형을 살펴보겠습니다.

✅ 문제 유형 예시

1️⃣ 비밀번호 조합 찾기

• 예: 3자리 숫자로 이루어진 비밀번호(000~999)를 찾는 문제
• 방법: 000부터 999까지 모든 경우를 하나씩 확인하여 올바른 비밀번호인지 검사
• 시간 복잡도: O(10³) = O(1000) (빠르게 해결 가능)

#include <stdio.h>

int main() {
    for (int i = 0; i < 1000; i++) {
        printf("%03d\n", i); // 000~999까지 출력
    }
    return 0;
}

---

2️⃣ 배열에서 두 수의 합 찾기

• 예: 주어진 배열에서 두 숫자의 합이 특정 값이 되는 쌍을 찾는 문제
• 방법: 모든 두 수의 조합을 확인(O(N²))
• 시간 복잡도: O(N²) (N이 작을 때 유용)

#include <stdio.h>

int main() {
    int arr[] = {1, 3, 5, 7, 9, 2, 8, 4, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 10;

    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (arr[i] + arr[j] == target) {
                printf("(%d, %d)\n", arr[i], arr[j]);
            }
        }
    }

    return 0;
}

📝 설명:
모든 (i, j) 쌍을 확인하여 합이 target과 같은 경우를 출력합니다.

---

3️⃣ 모든 순열/조합 만들기

• 예: N개의 숫자로 만들 수 있는 모든 순열 또는 조합 생성
• 방법: 백트래킹(Backtracking)이나 재귀를 사용하여 구현 가능
• 시간 복잡도: 순열 → O(N!), 조합 → O(2ⁿ) (N이 크면 비효율적)

#include <stdio.h>

#define MAX 10

int used[MAX] = {0};
int arr[MAX];
int n;

void generate_permutation(int level) {
    if (level == n) {
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = 1;
            arr[level] = i;
            generate_permutation(level + 1);
            used[i] = 0;
        }
    }
}

int main() {
    printf("Enter a number: ");
    scanf("%d", &n);
    generate_permutation(0);
    return 0;
}

📝 설명:
순열을 생성하여 모든 경우를 확인하며, 사용한 숫자를 used 배열로 관리합니다.

---

3.2 실전 문제 예제

완전 탐색을 활용한 실제 문제를 살펴보겠습니다.

예제 4: 숫자 야구 게임

📝 문제 설명

• 사용자에게 3자리 숫자를 입력받았을 때,
  가능한 모든 3자리 숫자 중 각 자리 숫자가 중복되지 않는 경우를 출력하는 문제입니다.
• 3자리 숫자는 100부터 999까지이며, abc에서 a ≠ b ≠ c인 숫자만 출력해야 합니다.

🔹 C 코드 구현

#include <stdio.h>

void check_number(int num) {
    for (int i = 100; i <= 999; i++) {
        int a = i / 100;       // 백의 자리
        int b = (i / 10) % 10; // 십의 자리
        int c = i % 10;        // 일의 자리

        if (a != b && b != c && a != c) {
            printf("%d\n", i);
        }
    }
}

int main() {
    check_number(123);
    return 0;
}

✅ 설명

• 100부터 999까지 모든 숫자를 하나씩 검사합니다.
• a, b, c를 추출하여 각 자리 숫자가 중복되지 않는지 확인합니다.
• 중복이 없으면 출력합니다.

🔹 실행 결과 (일부)

102
103
104
105
106
107
108
109
120
123
124
...
987

---

🔎 정리

✅ 완전 탐색을 사용할 수 있는 대표적인 문제 유형

1. 비밀번호 조합 찾기: 000~999까지 모든 조합 확인
2. 배열에서 두 수의 합 찾기: O(N²)으로 모든 쌍을 확인
3. 모든 순열/조합 만들기: 백트래킹을 활용하여 N! 또는 2ⁿ 탐색

✅ 실전 문제 예제

• 숫자 야구 게임: 각 자리 숫자가 중복되지 않는 3자리 숫자 출력
• 완전 탐색을 활용하여 모든 경우를 확인하는 방식으로 해결 가능

✅ 시간 복잡도 고려

• 경우의 수가 적다면 완전 탐색이 유용하지만, 경우의 수가 많다면 최적화가 필요할 수 있음.
  (예: O(N²), O(N!)의 복잡도를 가질 경우 데이터 크기 제한을 고려해야 함)

✅ 완전 탐색은 직관적이며 반드시 정답을 찾을 수 있는 강력한 방법이지만, 실행 속도를 고려해야 한다!