[알고리즘/Python] 브루트포스 알고리즘

유댕이·2024년 12월 26일

python 브루트포스 알고리즘 완전탐색

Algorithms

목록 보기

3/12

브루트 포스 (Brute Force)

Brute : 무식한

Force : 힘

브루트 포스를 직역하면 '무식한 힘'으로, 무식하게 힘으로 해결하는 방법이다. 이는 완전탐색 알고리즘 이라고도 하는데, 가능한 모든 경우의 수를 탐색하면서 요구 조건에 충족되는 결과만 가져온다.

문제를 어떻게 풀어야 할지 모를 때 브루트 포스로 먼저 접근을 하여 풀다보면 해결할 방법이 보일 수도 있고, 코딩테스트에서 부분점수를 얻을 수 있기 때문에 처음 알고리즘 문제를 풀 때는 이 방식으로 풀어보는 것을 추천한다.

단점

문제의 복잡도에 매우 민감하다.
탐색하고자 하는 값의 범위가 넓을 경우, 알고리즘 실행시간이 오래 걸린다.

문제 해결 방법

주어진 문제를 선형 구조로 구조화한다.

구조화된 문제 공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.

구성된 해를 정리한다.

여기서 사용할 수 있는 방법으로는 노가다성으로 다 해보기, 조합, 순열, 재귀호출, 비트마스크 등이 있다.

조합

조합은 n개 중에서 r개를 선택하는 경우의 수인데, 순서를 고려하지 않는다.

아래는 A, B, C 3개의 음식이 있는데 친구와 2개를 주문할 수 있는 조합을 구하는 예시를 반복문으로 구현한 것이다.

arr = ['A', 'B', 'C']
N = len(arr)

my_comb = []
for i in range(N - 1):
    for j in range(i + 1, N):
        my_comb.append((arr[i], arr[j]))

print(my_comb) # [('A', 'B'), ('A', 'C'), ('B', 'C')]

아래는 for 반복문을 사용하지 않고, itertools 내에 combinations라는 내장함수를 이용하여 구현한 것이다.

from itertools import combinations

arr = ['A', 'B', 'C']
print(list(combinations(arr, 2))) # [('A', 'B'), ('A', 'C'), ('B', 'C')]

순열

순열은 순서를 고려하여 나열하는 경우의 수이다.

위의 조합의 예시와 같이 A, B, C 3개의 음식이 있을 때, 친구와 각자 어떤 음식을 먹을지 고를 모든 경우의 수를 구해보자.

먼저 반복문으로 구현한 것이다. 조합에서는 j의 범위를 i + 1로 하여 i 번째 선택된 항목이 다시 선택 되지 않게 했다. 하지만 순열에서는 (A, B)와 (B, A)가 다르기 때문에 j도 처음부터 반복문을 돌아야 한다. 그래서 i, j 를 반복할 때 i + 1 이 시작이 아닌 처음부터 반복하도록 했다.

arr = ['A', 'B', 'C']
N = len(arr)

my_permu = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        my_permu.append((arr[i], arr[j]))

print(my_permu) 
# [('A', 'B'), ('A', 'C'), ('B', 'A'), 
#  ('B', 'C'), ('C', 'A'), ('C', 'B')]

순열도 itertools 내에 permutations라는 내장함수가 있다. 이를 이용해서 구현하면 아래와 같다.

from itertools import permutations
arr = ['A', 'B', 'C']

print(list(permutations(arr, 2)))
# [('A', 'B'), ('A', 'C'), ('B', 'A'), 
#  ('B', 'C'), ('C', 'A'), ('C', 'B')]