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

[08강] 브루트 포스 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 브루트 포스 알고리즘에 대해 알아보겠습니다. 목차 브루트 포스 알고리즘 실제 문제에서 브루트 포스 알고리즘 접근 방식과 알고리즘 접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다. 접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고, 알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다. 구체적인 예를 들어 설명해보겠습니다. 에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고, 그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다. 에라토스테네스의 체 알고리즘은 언제 쓰면 될까요? → 소수(prim..

https://gliver.tistory.com/17

1. 브루트 포스 알고리즘

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

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

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



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

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까지의 소수를 모두 구할 수 있다.
• 시간 복잡도:
python

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, 수학과 관련된 문제일 가능성이 높음