완전 탐색 - 2. 완전 탐색 기본 패턴

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;
}

✅ 설명

• for 반복문을 사용하여 1부터 100까지 모든 숫자를 하나씩 확인합니다.
• if (i % 3 == 0) 조건을 사용하여 3의 배수인지 검사합니다.
• 3의 배수라면 출력합니다.

🔹 실행 결과

3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99

---

예제 2: 배열에서 특정 값을 찾기

배열을 탐색하여 특정 값을 포함하는지 찾는 문제입니다.

#include <stdio.h>

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 30;
    int found = 0;

    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            found = 1;
            break;
        }
    }

    if (found) {
        printf("찾는 숫자 %d가 배열에 존재합니다.\n", target);
    } else {
        printf("찾는 숫자가 없습니다.\n");
    }

    return 0;
}

✅ 설명

• 배열의 모든 요소를 하나씩 검사하면서 target 값이 존재하는지 확인합니다.
• found 변수를 이용하여 값을 찾았는지 여부를 저장하고, 찾으면 break 문으로 탐색을 중단합니다.

🔹 실행 결과

찾는 숫자 30가 배열에 존재합니다.

---

예제 3: 1부터 N까지의 합 계산하기

반복문을 이용하여 1부터 N까지의 합을 계산하는 문제입니다.

#include <stdio.h>

int main() {
    int n, sum = 0;
    
    printf("N 값을 입력하세요: ");
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        sum += i;
    }

    printf("1부터 %d까지의 합: %d\n", n, sum);
    return 0;
}

✅ 설명

• for 반복문을 사용하여 1부터 n까지의 모든 숫자를 더합니다.
• sum += i 문장을 통해 누적 합을 계산합니다.

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

1부터 10까지의 합: 55

---

정리

✅ 반복문을 이용한 완전 탐색은 가장 기본적인 탐색 방법으로, 특정 범위 내에서 조건을 만족하는 값을 찾는 데 유용합니다.
✅ 모든 경우를 하나씩 확인하기 때문에 반드시 정답을 찾을 수 있지만, 경우의 수가 많아지면 성능이 떨어질 수 있습니다.
✅ 시간 복잡도는 일반적으로 O(N)이며, 경우에 따라 중첩 반복문을 사용하면 O(N²)까지 증가할 수 있습니다.