완전 탐색 - 5. 실전 문제 풀이

5. 실전 문제 풀이

완전 탐색(Brute Force)을 학습한 후에는 직접 문제를 풀어보면서 실력을 키우는 것이 중요합니다.
아래의 연습 문제를 풀면서 완전 탐색의 기본 원리를 익히고, 도전 문제를 통해 백준(BOJ)과 같은 온라인 저지에서 응용력을 키워봅시다.

---

✅ 연습 문제

완전 탐색을 활용하여 해결할 수 있는 기본적인 문제들을 소개합니다.

---

1️⃣ 1부터 100까지의 숫자 중에서 7의 배수 출력하기

문제 설명
1부터 100까지 숫자 중에서 7의 배수를 찾아 출력하는 프로그램을 작성하세요.

#include <stdio.h>

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

✅ 설명:

• 1부터 100까지 반복하며, 7의 배수인지 검사합니다.
• 조건문 if (i % 7 == 0)을 사용하여 7의 배수를 판별합니다.

🔹 실행 결과

7 14 21 28 35 42 49 56 63 70 77 84 91 98

---

2️⃣ 주어진 숫자 리스트에서 두 개의 숫자를 선택해 합이 특정 값이 되는 쌍 찾기

문제 설명
주어진 숫자 리스트에서 두 개의 숫자를 선택하여 합이 특정 값이 되는 모든 쌍을 출력하세요.

#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) 쌍을 탐색(O(N²)) 하면서 합이 target과 같은 경우 출력합니다.

🔹 실행 결과

(1, 9)
(3, 7)
(4, 6)

---

3️⃣ 1부터 N까지 숫자의 모든 순열을 출력하는 프로그램

문제 설명
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[] 배열을 활용하여 중복을 방지합니다.

🔹 실행 결과 (N=3 입력 시)

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

---

4️⃣ 세 자리 숫자 중 각 자리 숫자가 다른 경우만 출력하는 문제

문제 설명
100부터 999까지의 숫자 중에서, 각 자리 숫자가 중복되지 않는 경우만 출력하세요.

#include <stdio.h>

void check_number() {
    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();
    return 0;
}

✅ 설명:

• 각 자리 숫자가 중복되지 않는 경우만 출력합니다.
• a != b && b != c && a != c 조건을 사용하여 중복 여부를 확인합니다.

---

5️⃣ 비밀번호 조합 (000~999까지 모든 경우를 검사)

문제 설명
비밀번호가 000~999까지 존재한다고 가정할 때, 모든 가능한 조합을 생성하여 출력하세요.

#include <stdio.h>

int main() {
    for (int i = 0; i < 1000; i++) {
        printf("%03d\n", i); // 3자리 숫자로 출력
    }
    return 0;
}

✅ 설명:

• printf("%03d\n", i); → 3자리로 출력 (앞에 0을 포함)
• 000부터 999까지 모든 숫자를 출력합니다.

🔹 실행 결과 (일부)

000
001
002
...
998
999

---

✅ 도전 문제 (백준 BOJ 문제 추천)

✅ 1. BOJ 2231 - 분해합

• 자연수 N이 주어졌을 때, 가장 작은 생성자를 찾는 문제
• 완전 탐색을 활용하여 1부터 N까지 확인 가능
  🔗 문제 링크: https://www.acmicpc.net/problem/2231

✅ 2. BOJ 14500 - 테트로미노

• 4개의 블록을 연결하여 만들 수 있는 테트로미노 모양을 찾고, 최댓값을 구하는 문제
• 완전 탐색 + 백트래킹 기법 필요
  🔗 문제 링크: https://www.acmicpc.net/problem/14500

✅ 3. BOJ 1182 - 부분수열의 합

• 주어진 배열에서 부분 수열의 합이 특정 값이 되는 경우의 수 찾기
• 비트마스킹 + 백트래킹 활용 가능
  🔗 문제 링크: https://www.acmicpc.net/problem/1182

---

🔎 정리

✅ 기본 연습 문제

• 7의 배수 찾기 (O(N))
• 두 수의 합 찾기 (O(N²))
• 모든 순열 생성 (O(N!))
• 중복 없는 세 자리 숫자 출력 (O(N))
• 000~999 비밀번호 조합 생성 (O(10³))

✅ 도전 문제 (백준)

• BOJ 2231: 분해합 (완전 탐색)
• BOJ 14500: 테트로미노 (백트래킹)
• BOJ 1182: 부분수열의 합 (비트마스킹 활용 가능)