완전 탐색 - 4. 시간 복잡도와 최적화

4. 시간 복잡도와 최적화

완전 탐색(Brute Force)은 모든 경우의 수를 하나하나 확인하는 방식이므로, 경우의 수가 많아질수록 실행 시간이 기하급수적으로 증가할 수 있습니다.
따라서 시간 복잡도를 분석하고, 필요할 경우 최적화 기법을 적용하는 것이 중요합니다.

---

4.1 시간 복잡도 개념

시간 복잡도는 입력 크기 N에 따라 알고리즘이 얼마나 많은 연산을 수행하는지를 나타냅니다.
완전 탐색의 대표적인 시간 복잡도를 살펴보겠습니다.

✅ 완전 탐색의 대표적인 시간 복잡도

시간 복잡도	의미	예제
O(N)	입력 크기만큼 반복	1부터 N까지의 합 구하기
O(N²)	두 개의 반복문 사용	배열에서 두 숫자의 합 찾기
O(N³)	세 개의 반복문 사용	세 수의 조합을 확인하는 문제
O(2ⁿ)	모든 부분 집합 탐색	부분 집합을 찾는 문제
O(N!)	모든 순열 탐색	N개의 숫자로 만들 수 있는 모든 순열

완전 탐색을 사용할 경우, 일반적으로 O(N²) 이상의 시간 복잡도를 가지는 경우가 많습니다.
N이 작을 때는 문제가 없지만, N이 커지면 실행 시간이 너무 길어질 수 있습니다.
따라서 가능한 경우 최적화 기법을 활용해야 합니다.

---

4.2 개선 방법

완전 탐색의 단점을 보완하기 위해 다양한 최적화 기법을 사용할 수 있습니다.
대표적으로 백트래킹, 비트마스킹, 동적 계획법(DP)과의 조합이 있습니다.

---

✅ 1. 백트래킹 (Backtracking)

✔ 불필요한 탐색을 줄이는 기법
백트래킹은 가능성이 없는 경로를 미리 차단(가지치기, pruning) 하여 탐색 범위를 줄이는 기법입니다.

📌 적용 예시: 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[] 배열을 사용하여 중복을 방지
• 순열을 만들 때, 이미 선택한 숫자는 탐색하지 않음 → 불필요한 탐색 제거 (가지치기)
• 시간 복잡도를 O(N!)에서 더 효율적으로 줄일 수 있음

---

✅ 2. 비트마스킹 (Bitmasking)

✔ 숫자 조합을 효율적으로 표현하는 기법
비트마스킹을 사용하면 부분 집합을 탐색할 때 반복문을 줄이고 빠르게 연산할 수 있습니다.

📌 적용 예시: 부분 집합 구하기

#include <stdio.h>

void print_subsets(int arr[], int n) {
    int subset_count = 1 << n; // 2^n 개의 부분 집합

    for (int i = 0; i < subset_count; i++) {
        printf("{ ");
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) { // j번째 요소가 포함되는지 확인
                printf("%d ", arr[j]);
            }
        }
        printf("}\n");
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    print_subsets(arr, n);
    return 0;
}

✅ 설명

• 비트마스킹을 사용하여 O(2ⁿ)의 복잡도로 모든 부분 집합을 생성
• 반복문을 줄일 수 있어 실행 속도가 개선됨
• 특정 원소의 포함 여부를 O(1)에 확인 가능

🔹 실행 결과

{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }

---

✅ 3. 동적 계획법(DP) + 완전 탐색 조합

✔ 중복 계산을 줄여 효율적으로 탐색
완전 탐색은 같은 연산을 여러 번 수행하는 경우가 많기 때문에 DP를 활용하면 불필요한 계산을 줄일 수 있습니다.
DP를 사용하면 한 번 계산한 결과를 저장하고 재활용하여 속도를 개선할 수 있습니다.

📌 적용 예시: 피보나치 수열 (DP 적용)

#include <stdio.h>

#define MAX 100
int dp[MAX] = {0};

int fibonacci(int n) {
    if (n <= 1) return n;
    if (dp[n] != 0) return dp[n]; // 이미 계산된 값이면 재사용
    return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

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

✅ 설명

• 메모이제이션을 활용하여 이미 계산한 값은 다시 계산하지 않음
• 기존 재귀 방식(O(2ⁿ)) → O(N) 으로 최적화
• 완전 탐색과 DP를 결합하면 탐색 속도를 획기적으로 향상 가능

---

🔎 정리

✅ 완전 탐색의 시간 복잡도는 O(N²), O(N³), O(2ⁿ), O(N!) 등으로 커질 수 있으며, 최적화가 필요함
✅ 백트래킹(Backtracking): 불필요한 탐색을 줄여 경우의 수를 최소화
✅ 비트마스킹(Bitmasking): 특정 문제(부분 집합 탐색 등)에서 연산을 빠르게 수행
✅ 동적 계획법(DP) + 완전 탐색 조합: 중복 연산을 줄여 계산 속도를 최적화