# 완전 탐색

**완전 탐색**이란 모든 경우의 수를 다 따져가며 정답을 찾는 방식을 의미합니다.

**브루트포스(brute-force) 알고리즘**이라고도 하며, "무식하게 푸는 방법"이라고 생각해도 좋습니다.

4자리 수의 자물쇠를 푸는데는 오랜 시간이 걸립니다. 운이 좋지 않으면 총 10,000(10x10x10x10)번의 시도를 해야 합니다. 하지만 컴퓨터의 빠른 계산 능력을 빌린다면, 이러한 문제는 아주 적은 시간만에 풀어낼 수 있습니다.

이처럼 컴퓨터의 빠른 속도를 믿고 "전부" 해보는 방식이 바로 **완전 탐색**입니다.

즉, 완전 탐색은 N개의 경우를 모두 살펴본다고 하였을 때, **O(N)** 만큼의 시간 복잡도를 가집니다.

하지만, 대부분의 알고리즘 문제는 **시간 제한**이 있습니다. 안타깝게도 **완전 탐색**은 이러한 시간 제한에 자유롭지 못합니다.\
백준 문제의 좌측 상단에서 **시간 제한**을 찾아볼 수 있는데, 보통 **1초**에 약 **1억 번**의 연산을 할 수 있다고 생각하시면 됩니다.

예를 들어 컴퓨터가 1부터 10억까지의 수 중 하나를 고르고, 제가 그 수를 **1초** 안에 맞춰야 하는 상황을 가정하겠습니다.\
최악의 경우에는 10억 번의 시도가 필요합니다. 즉, 약 10초가 소요되는 이러한 경우에는 **완전 탐색**을 사용할 수 없습니다.

결론적으로 모든 문제를 풀 때는

1️⃣ **시간 복잡도를 계산하고**

**2️⃣ 이를 기반으로 완전 탐색 가능 여부를 판단한다**

의 순서로 접근하셔야 합니다.\
시간 제한으로 완전탐색이 어렵다고 판단이 되면, 다른 알고리즘을 고안하시면 됩니다.

## 연습문제

### BOJ 13423

{% embed url="<https://www.acmicpc.net/problem/13423>" %}

간단히 말해서, 입력받은 N개의 점 중 간격이 동일한 세 개의 점의 **조합**이 총 몇 개인지 구하는 문제입니다.

3중 반복문을 통해 3개의 점을 골라내거나, itertools의 combinations 을 생각해볼 수 있습니다.

여기서는 combinations를 사용해보도록 하겠습니다.

```python
from itertools import combinations as cb

t = int(input())
for _ in range(t):
    n = int(input())
    li = list(map(int, input().split()))
    li.sort()
    ans = 0
    for i in cb(li, 3):
        if i[2] - i[1] == i[1] - i[0]:
            ans += 1
    print(ans)
```

시간 제한이 없다면 이 방식으로 풀어도 문제가 없습니다.

하지만 점이 최대 1,000개이기 때문에, 약 1,000 \* 1,000 \* 1,000 만큼의 연산이 필요하고 이는 1초의 시간 제한을 훌쩍 넘어가게 됩니다.

그렇다면 다른 방법을 생각해야 합니다.

동일하게 완전 탐색 풀이지만, **defaultdict**을 사용하면 시간 초과에서 자유로워질 수 있습니다.

```python
from collections import defaultdict

t = int(input())
for _ in range(t):
    n = int(input())
    li = sorted(list(map(int, input().split())))
    spotList = defaultdict(int)
    for i in range(len(li)):              # 모든 점을 defaultdict에 담기
        spotList[li[i]] = 1               # True를 의미함

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            first = li[i]
            second = li[j]
            third = li[j] + (li[j] - li[i]) # 임의의 세번 째 점
            if spotList[third] == 1:      # 임의의 세번 째 점이 존재하는지 확인
                ans += 1
    print(ans)
```

일단, defaultdict(int)을 하나 생성하여 모든 점을 담아줍니다.&#x20;

'점이 존재한다'는 의미로 defaultdict을 사용할 것이므로, 존재하는 점(key)의 값(value)은 모두 임의의 값 1로 넣어줍니다.

그 후에 이중 반복문을 통해 defaultdict에 담긴 두 점을 선택합니다.

<figure><img src="/files/V11nlXqhsFlZuFH1GJ7G" alt=""><figcaption></figcaption></figure>

first와 second를 선택하고, 이 두 점 사이의 거리와 동일한 third를 임의로 설정합니다.

임의의 third가 만약 defaultdict에 존재한다면 동일한 거리의 세 점이 모두 존재한다는 의미가 됩니다.

위와 같은 경우에 ans의 값을 1씩 올리면서 반복문을 돌면, 최종 정답을 구할 수 있습니다.

처음에, 나쁜 예로 **combinations** 활용 코드를 보여드렸습니다.

문제를 보고 **3중 반복문** 혹은 **combinations**을 사용해야겠다는 아이디어가 떠올랐다면 잘하신겁니다.&#x20;

하지만 코드를 작성하기 이전에 시간 복잡도 계산이 우선시 되었다면, 해당 코드를 작성하며 시간을 낭비하는 일이 없었겠죠?

다시 한 번 강조하겠습니다.

1️⃣ **시간 복잡도 계산**

**2️⃣** 이를 기반으로 **완전탐색** vs. **완전탐색에서 조금 더 최적화**&#x20;

3️⃣ **그 외 알고리즘** 선택

## 풀어볼 문제

시간복잡도를 살펴보며 문제를 풀어봅시다.

{% embed url="<https://www.acmicpc.net/problem/19532>" %}
\[백준] 수학은 비대면 강의입니다
{% endembed %}

{% embed url="<https://www.acmicpc.net/problem/1895>" %}
\[백준] 필터
{% endembed %}

{% embed url="<https://www.acmicpc.net/problem/17614>" %}
\[백준] 369
{% endembed %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://koalas-organization.gitbook.io/koala_codingtest_study/search/brute_force.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.