[알고리즘] 05. 완전탐색이 필요한 상황

[알고리즘] 05. 완전탐색이 필요한 상황

지난 글에서는 입력 크기별 알고리즘 선택법에 대해 정리했습니다. 이번 글에서는 알고리즘 문제에서 자주 등장하는 완전탐색에 대해 알아보겠습니다.

완전탐색은 이름 그대로 가능한 경우를 하나씩 모두 확인하는 방법입니다. 처음 알고리즘을 공부할 때 가장 먼저 익숙해져야 하는 풀이 방식이기도 합니다.

완전탐색은 가능한 모든 경우를 직접 확인해서 정답을 찾는 방법입니다.

---

1. 완전탐색이란?

완전탐색은 문제에서 가능한 모든 경우를 하나씩 확인하는 방식입니다. 특별한 규칙이나 빠른 방법을 찾기 어렵다면, 가장 단순하게 모든 경우를 검사해볼 수 있습니다.

예를 들어 배열에서 가장 큰 값을 찾는 문제를 생각해보겠습니다.

int[] arr = {3, 7, 2, 9, 5};

int max = arr[0];

for (int i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}

System.out.println(max);

위 코드는 배열의 값을 처음부터 끝까지 모두 확인합니다. 모든 값을 검사한 뒤 가장 큰 값을 찾기 때문에 완전탐색의 기본적인 형태라고 볼 수 있습니다.

---

2. 완전탐색이 필요한 이유

알고리즘 문제를 풀다 보면 처음부터 효율적인 방법이 바로 떠오르지 않을 때가 많습니다. 이럴 때 완전탐색은 문제를 이해하는 출발점이 됩니다.

• 가능한 경우의 수가 많지 않을 때
• 문제의 규칙을 아직 찾기 어려울 때
• 정답 후보를 모두 확인해야 할 때
• 입력 크기가 작아서 모든 경우를 확인해도 괜찮을 때
• 더 효율적인 풀이를 만들기 전 기준 풀이가 필요할 때

완전탐색은 단순하지만 강력합니다. 모든 경우를 확인하기 때문에 조건만 제대로 작성하면 정답을 놓칠 가능성이 낮습니다.

완전탐색은 가장 세련된 풀이가 아닐 수 있지만, 문제를 정확히 이해하는 데 매우 좋은 시작점입니다.

---

3. 완전탐색이 가능한지 먼저 판단해야 합니다

완전탐색을 사용할 때 가장 중요한 것은 입력 크기입니다. 모든 경우를 확인하는 방식이기 때문에 입력이 커지면 시간이 오래 걸릴 수 있습니다.

입력 크기	완전탐색 가능성	예상 풀이
N ≤ 100	대체로 가능	이중 반복문 가능
N ≤ 1,000	문제에 따라 가능	O(N²) 정도 검토
N ≤ 100,000	주의 필요	O(N²)은 위험
N이 매우 큼	대부분 부적합	정렬, 해시, 이분 탐색 고려

완전탐색은 입력 크기가 작을 때는 좋은 선택이지만, 입력 크기가 커지면 시간 초과가 발생할 수 있습니다.

---

4. 예제 1 — 두 수의 합 찾기

배열에서 두 수를 골라 합이 target이 되는 경우를 찾는 문제를 생각해보겠습니다.

배열 arr에서 서로 다른 두 수를 골랐을 때, 합이 target이 되는 쌍이 있는지 확인하라.

가장 단순한 방법은 모든 두 수의 조합을 직접 확인하는 것입니다.

int[] arr = {2, 4, 7, 11, 15};
int target = 9;

boolean found = false;

for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        if (arr[i] + arr[j] == target) {
            found = true;
        }
    }
}

System.out.println(found);

이 코드는 가능한 모든 두 수의 조합을 확인합니다. 배열 길이가 N이라면 시간복잡도는 O(N²)입니다.

N이 작다면 충분히 사용할 수 있지만, N이 100,000처럼 크다면 더 효율적인 방법을 고민해야 합니다.

---

5. 예제 2 — 비밀번호 찾기

완전탐색은 가능한 후보를 전부 만들어 확인하는 문제에서도 자주 사용됩니다. 예를 들어 000부터 999까지의 숫자 중 정답 비밀번호를 찾는 상황을 생각해보겠습니다.

String answer = "527";

for (int i = 0; i <= 999; i++) {
    String password = String.format("%03d", i);

    if (password.equals(answer)) {
        System.out.println("비밀번호 찾음: " + password);
        break;
    }
}

이 코드는 000부터 999까지 가능한 모든 비밀번호를 확인합니다. 후보가 1,000개밖에 없기 때문에 완전탐색으로 충분히 해결할 수 있습니다.

완전탐색은 이렇게 경우의 수가 제한적일 때 매우 직관적이고 안정적인 풀이가 됩니다.

---

6. 예제 3 — 가장 좋은 경우 찾기

완전탐색은 여러 후보 중에서 가장 좋은 값을 찾는 문제에도 자주 사용됩니다. 예를 들어 배열에서 두 수를 골랐을 때 만들 수 있는 가장 큰 합을 구해보겠습니다.

int[] arr = {5, 1, 9, 3, 7};

int maxSum = 0;

for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        int sum = arr[i] + arr[j];

        if (sum > maxSum) {
            maxSum = sum;
        }
    }
}

System.out.println(maxSum);

이 코드는 가능한 모든 두 수의 조합을 확인하면서 가장 큰 합을 찾습니다. 정답 후보를 모두 비교해야 하는 상황에서는 완전탐색이 자연스럽게 사용됩니다.

---

7. 완전탐색이 위험한 경우

완전탐색은 모든 경우를 확인한다는 장점이 있지만, 그만큼 경우의 수가 많아지면 매우 느려질 수 있습니다.

특히 아래 상황에서는 주의해야 합니다.

• 입력 크기 N이 매우 큰 경우
• 반복문이 3중 이상으로 중첩되는 경우
• 가능한 조합의 수가 폭발적으로 증가하는 경우
• 문제 제한 시간이 짧은 경우
• 같은 계산을 반복해서 수행하는 경우

예를 들어 N이 100,000인데 이중 반복문을 사용하면 대략 10,000,000,000번에 가까운 연산이 발생할 수 있습니다. 이런 경우에는 시간 초과가 날 가능성이 매우 높습니다.

N	O(N²) 연산 수
100	10,000
1,000	1,000,000
10,000	100,000,000
100,000	10,000,000,000

그래서 완전탐색을 사용하기 전에는 항상 입력 크기와 시간복잡도를 함께 확인해야 합니다.

---

8. 완전탐색을 개선하는 방향

완전탐색으로 풀 수 없을 것 같다면, 모든 경우를 확인하지 않고도 정답을 찾을 수 있는 방법을 생각해야 합니다.

상황	개선 방향
값을 빠르게 찾아야 함	HashSet, HashMap
정렬 후 범위를 좁힐 수 있음	정렬, 투 포인터
구간 합을 반복해서 구함	누적합
가능성이 없는 경우를 줄일 수 있음	백트래킹
정답 범위를 절반씩 줄일 수 있음	이분 탐색

중요한 것은 완전탐색을 무조건 나쁘게 보는 것이 아닙니다. 먼저 완전탐색으로 생각해보고, 입력 크기 때문에 어렵다면 개선 방향을 찾는 것이 좋습니다.

완전탐색은 실패한 풀이가 아니라, 더 좋은 풀이로 가기 위한 기준점이 될 수 있습니다.

---

9. 완전탐색 문제를 풀 때 체크할 것

완전탐색 문제를 풀 때는 아래 순서로 확인하면 좋습니다.

1. 가능한 경우의 수가 몇 개인지 계산한다.
2. 입력 크기 N의 최댓값을 확인한다.
3. 반복문이 몇 번 중첩되는지 확인한다.
4. 대략적인 시간복잡도를 계산한다.
5. 제한 시간 안에 가능한지 판단한다.
6. 불가능하다면 정렬, 해시, 누적합, 이분 탐색 등을 고려한다.

이 과정을 거치면 무작정 코드를 작성하다가 시간 초과가 나는 일을 줄일 수 있습니다.

---

10. 정리

이번 글에서는 완전탐색이 필요한 상황을 정리했습니다.

• 완전탐색은 가능한 모든 경우를 직접 확인하는 방법이다.
• 입력 크기가 작으면 가장 단순하고 안정적인 풀이가 될 수 있다.
• 정답 후보를 모두 확인해야 할 때 완전탐색을 사용할 수 있다.
• 입력 크기가 커지면 시간 초과가 발생할 수 있다.
• 완전탐색이 어렵다면 해시, 정렬, 투 포인터, 누적합, 이분 탐색 등을 고려해야 한다.

완전탐색은 알고리즘 공부의 기본입니다. 처음부터 어려운 기법을 찾기보다, 먼저 모든 경우를 확인하는 방법을 생각해보면 문제 구조를 더 잘 이해할 수 있습니다.

좋은 알고리즘은 완전탐색을 이해한 뒤, 불필요한 탐색을 줄이는 방향으로 발전합니다.

---

다음 글 예고

다음 글에서는 알고리즘 문제 풀이 순서에 대해 알아보겠습니다.

문제를 읽고 바로 코드를 작성하는 것이 아니라, 입력, 출력, 조건, 예외 케이스를 어떤 순서로 정리해야 하는지 차근차근 살펴보겠습니다.