브루트 포스 알고리즘 [개념]

https://gliver.tistory.com/17

1. 브루트 포스 알고리즘

• 브루트 포스 알고리즘은 모든 경우를 살펴봄으로써 답을 구하는 알고리즘이다.

• 따라서, 항상 답을 구할 수 있지만 수행 시간이 오래 걸릴 수 있다.

• 예시1) 브루트 포스 알고리즘 사용 가능

  

  • 브루트 포스적인 방법으로 2중 for문을 이용하여 해결할 수 있다.
  • 시간 복잡도: $O(N^2)$
    • 약수를 구하는 과정을 $\sqrt{N}$에 수행하면 $O(N \cdot \sqrt{N})$ 풀이도 가능 (링크)

N = 1000
result = 0

for i in range(1, N + 1):  # O(N)
    if i == 1:  # 1은 예외 처리
        continue

    is_prime = True

    for j in range(2, i):  # O(i)
        if i % j == 0:
            is_prime = False

    if is_prime:
        result += 1

print(result)

• 예시2) 브루트 포스 알고리즘 사용 불가능

  

  • 위에서 살펴 봤던 브루트 포스적인 풀이는 시간 초과가 나기 때문에 사용할 수 없다.
  • 에라토스테네스의 체 알고리즘을 이용하여 1부터 N까지의 소수를 모두 구할 수 있다.
  • 시간 복잡도: $O(N \cdot log(logN))$

from math import sqrt

N = int(1e6)
result = 0
is_prime = [True for _ in range(N + 1)]
# is_prime[k] 가 true이면 k는 소수임을 나타냄.
# is_prime[k] 가 false이면 k는 소수가 아님을 나타냄.
is_prime[1] = False

for i in range(2, int(sqrt(N)) + 1):
    if is_prime[i]:
        for j in range(2 * i, N + 1, i):
            is_prime[j] = False

for i in range(1, N + 1):
    result += is_prime[i]

print(result)

2. 실제 문제에서 브루트 포스 알고리즘

• 문제를 보고 브루트 포스적인 풀이가 가능한지 파악하기
  • 모든 경우의 수를 쉽게 살펴 볼 수 있는 구조인지 파악
  • 모든 경우의 수를 살펴 보는 풀이가 시간 초과가 나지 않는지 파악
  • 조합, 순열, 부분 순열 은 모든 경우의 수를 살펴보는 알고리즘
• 브루트 포스적으로 풀면 시간 초과가 나는 경우
  • 브루트 포스적인 풀이 최적화
    • 어떻게 하면 더 효율적으로 답의 후보를 살펴볼 수 있을까 생각
  • 도저히 해도 안 되는 경우
    • 그리디, DP, 수학과 관련된 문제일 가능성이 높음