브루트 포스(무차별 대입)알고리즘에 대한 정리 - 세기무민

안녕하세요 세기무민입니다. 

이번 포스팅은 브루트포스 알고리즘에 대해 다뤄보겠습니다. 

---

브루트포스?

 

브루트 포스는 무차별 대입을 통해 값을 도출하는 방법입니다. 

브루트 포스 알고리즘은 암호 해독에 유명한 알고리즘 중 하나입니다.

브루트 포스는 조합 가능한 모든 문자열을 하나씩 대입해보는 완전 탐색 기법이라고 생각하면 됩니다. 

 

브루트포스 알고리즘 장단점?

조합 가능한 모든 문자열을 대입하기 때문에 정확도가 100%를 도출합니다.

단, 모든 경우의 수를 찾아가기 때문에  조금만 알고리즘이 복잡해져도 알고리즘의 시간 복잡성은 올라갑니다.

 

 

예시 알고리즘 문제

위의 문제는 가장 대표적인 브루트 포스 알고리즘 중 하나입니다. 

3개의 숫자를 합했을 때 M의 크기와 가장 가까운 값을 찾는 문제인데 

해당 문제는 순열을 통해서 문제를 풀면 됩니다. 

[코드]

from itertools import combinations

x, y = input().split()
arr = list(map(int, input().split()))
maxs = 0

for i in combinations(arr, 3):
    tmp = sum(i)
    if tmp <= int(y):
        if maxs < tmp:
            maxs = tmp

print(maxs)

순열을 이용하여 3개의 값을 더한 경우가 M보다는 작으며 max값보다는 큰 값을 구해주면 됩니다. 

위의 문제도 브루트 포스 문제로 풀 수 있다. 

말 그대로 키와 몸무계를 하나씩 비교하면서 가장 큰 경우를 제외하고 하나씩 rank를 매기면 됩니다. 

[코드]

N = int(input())

arr = []

for i in range(N):
    arr.append(list(map(int, input().split())))
    

for i in arr:
    rank = 1
    for j in arr:
        if i[0] < j[0] and i[1] < j[1]:
            rank += 1
            
    print(rank, end = ' ')

코드는 위와 같습니다. 

몸무계와 키의 크기를 비교하면서 등수를 매기면 됩니다. 

마치며

브루트 포스는 사실 암호 알고리즘을 공부했을 때 많이 접했던 알고리즘 중 하나였습니다.

하지만 알고리즘 문제로 접했을 때와 이론은 확실히 달랐고..

알고리즘 문제로 푸는건 쉽지 않았던거 같습니다.

완전 탐색이라고 하는 것처럼 모든 경우의 수를 탐색하면 된다고 생각하지만 

때로는 시간 복잡도를 고려했을 때 이렇게 푸는 것이 맞는지도 의문이 들때가 있다.

그만큼 아직 내가 알고리즘 공부가 미흡한 것이라는 생각도 들었고 

좀 더 열심히 해야겠다고 생각하게 되었습니다.