완전 탐색 (Brute Force) 요약

완전 탐색 (Brute Force)

완전 탐색(Brute Force)은 가능한 모든 경우의 수를 하나씩 전부 검사하여 정답을 찾는 방법입니다.

---

1. 완전 탐색(Brute Force)란?

1.1 개념 이해

• 완전 탐색은 모든 경우의 수를 직접 탐색하여 해답을 찾는 알고리즘입니다.
• 장점: 간단하고 직관적이며, 모든 경우를 확인하므로 정확한 답을 찾을 수 있음.
• 단점: 경우의 수가 많아지면 시간이 오래 걸릴 수 있음. (시간 복잡도 고려 필요)

1.2 언제 사용할까?

• 가능한 경우의 수가 작을 때 (예: 100만 이하)
• 최적의 해를 찾는 것이 아니라, 모든 경우를 확인하는 것이 중요한 문제
• 더 효율적인 알고리즘이 떠오르지 않을 때 기본적으로 시도해볼 수 있음

---

2. 완전 탐색 기본 패턴

2.1 반복문을 이용한 완전 탐색

예제 1: 1부터 100까지의 숫자 중에서 3의 배수 찾기

#include <stdio.h>

int main() {
    for (int i = 1; i <= 100; i++) {
        if (i % 3 == 0) {
            printf("%d ", i);
        }
    }
    return 0;
}

✅ 설명: 모든 숫자를 하나씩 확인하면서, 3의 배수인지 검사합니다.

---

2.2 중첩 반복문을 이용한 완전 탐색

예제 2: 두 수의 합이 특정 값이 되는 쌍 찾기

• 배열에서 두 개의 수를 골라 합이 10이 되는 경우를 찾는 문제

#include <stdio.h>

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

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

    return 0;
}

✅ 설명: 모든 가능한 (arr[i], arr[j]) 조합을 확인하면서 합이 10이 되는 경우를 출력합니다.

---

2.3 재귀를 이용한 완전 탐색

예제 3: 1부터 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 배열을 이용해 중복을 방지하며, 숫자를 선택하는 모든 경우의 수를 확인합니다.
• generate_permutation() 함수가 재귀적으로 호출되면서 순열을 생성합니다.

---

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

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

✅ 문제 유형 예시

• 비밀번호 조합 찾기: 000~999까지 모든 경우를 확인
• 배열에서 두 수의 합 찾기: O(N²) 브루트 포스 가능
• 모든 순열/조합 만들기: N! 또는 2^N 경우의 수를 고려

---

3.2 실전 문제 예제

예제 4: 숫자 야구 게임

• 사용자가 3자리 숫자를 입력했을 때, 모든 가능한 숫자 조합을 탐색하여 결과를 확인하는 문제

#include <stdio.h>

void check_number(int num) {
    for (int i = 100; i <= 999; i++) {
        int a = i / 100, b = (i / 10) % 10, c = i % 10;
        if (a != b && b != c && a != c) {
            printf("%d\n", i);
        }
    }
}

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

✅ 설명:

• 모든 3자리 숫자(100~999)를 확인하면서, 각 자리 숫자가 중복되지 않는 경우를 출력합니다.

---

4. 시간 복잡도와 최적화

4.1 시간 복잡도 개념

• 완전 탐색은 보통 O(N), O(N²), O(N³), O(N!) 등의 복잡도를 가짐
• 데이터 크기가 크면 실행 시간이 매우 길어질 수 있음

4.2 개선 방법

• ✅ 백트래킹 (Backtracking): 가지치기를 하여 불필요한 탐색을 줄임
• ✅ 비트마스킹: 특정 경우에 유용하게 활용 (예: 부분집합 문제)
• ✅ DP + 완전 탐색 조합: 메모이제이션을 활용하여 중복 계산 줄이기

---

5. 실전 문제 풀이

✅ 연습 문제

1. 1부터 100까지의 숫자 중에서 7의 배수 출력하기
2. 주어진 숫자 리스트에서 두 개의 숫자를 선택해 합이 특정 값이 되는 쌍 찾기
3. 1부터 N까지 숫자의 모든 순열을 출력하는 프로그램
4. 세 자리 숫자 중 각 자리 숫자가 다른 경우만 출력하는 문제
5. 비밀번호 조합 (000~999까지 모든 경우를 검사)

✅ 도전 문제

• 백준(BOJ) 문제 추천:
  • BOJ 2231 - 분해합
  • BOJ 14500 - 테트로미노
  • BOJ 1182 - 부분수열의 합

---

6. 마무리 및 심화 학습

• 완전 탐색은 모든 경우의 수를 확인하는 직관적인 방법이지만, 경우의 수가 많아지면 비효율적일 수 있음
• 백트래킹, 분할 정복, DP 등의 기법과 조합하여 성능을 개선할 수 있음
• 초보자는 먼저 반복문과 재귀를 익히고, 점진적으로 최적화 방법을 익히면 좋음