완전탐색 - 브루트 포스

완전탐색

모든 경우의 수를 다 살펴보기 때문에 반드시 답을 찾을 수 있고, 답이 없다면 답이 존재하지 않는다는 사실 자체를 알아낸 것이다.
하지만, 리소스를 많이 잡아먹기 때문에 오래걸리게 된다.

Brute force search (무차별 대입)

• 이름 그대로 모든 경우의 수를 무차별적으로 대입하며 예외없이 100%의 확률로 답을 구한다.
• 가장 확실하게 답을 구하는 방법이기 때문에 생각외로 많이 쓰이고 있다.
• 선형 구조에서는 순차 탐색이 가장 기본이다.
• 비선형 구조에서는 DFS, BFS가 대표적이다.
• 알고리즘 문제에 시간 제한이 있을 경우, 다른 방법을 찾아야 할 수 있다.
  

예제 및 알고리즘

N개의 수에서 두 수를 뽑았을때 가장 큰 합은? (Combination)

• 순서가 상관없기 때문에 nCr(조합)이다. n * n-1 / r * r-1
  => n=8, r=2 👉🏻 8 * 7 / 2 * 1 경우의 수는 28가지 이다.
• 시간제한이 1초에 입력값이 2 < N < 1,000,000이라면 완전 탐색으로 풀 수 없다. (대략 1초에 1억개로 계산할 수 있다.)
  => 정렬(O(n log n))을 한 뒤, 마지막 두 요소를 더하는 방법이 있다.
  

brute-force 방법

arr = [30, 40, 20, 13, 28, 49, 10, 18]
res = []

# 첫번째 반복문에서 arr의 끝까지 간다면 마지막 요소가 겹치게 된다.
# 그렇기 때문에 첫번째 반복문에서 arr의 마지막 요소 앞까지만 이용한다.
for i in range(len(arr)-1):
    for j in range(i+1, len(arr)):
        res.append(arr[i] + arr[j])

print(res) # [70, 50, 43, 58, 79, 40, 48, 60, 53, 68, 89, 50, 58, 33, 48, 69, 30, 38, 41, 62, 23, 31, 77, 38, 46, 59, 67, 28]
print(len(res)) # 28
print(max(res)) # 89

Python - itertools

파이썬에서는 내장 모듈로 순열과 조합을 구할 수 있는 함수가 있다.

permutations (순열)

from itertools import permutations

arr = [0, 1, 2, 3]

# 첫번째 인자로 배열을 두번째 인자로 조합할 개수를 넣어주면 되고, 숫자 n개를 이용하여 만들 수 있는 모든 경우의 수가 나온다.
# 순열이기 때문에 순서가 달라도 다른 경우의 수가 된다. (순서 중요!)
for i in permutaions(arr, 4):
	print(i)
    
# 아래의 출력을 확인 한다면 리스트에 튜플로 모든 조합이 담긴것을 볼 수 있다.
print(list(permutations(arr,3)))
# [(0, 1, 2), (0, 1, 3), (0, 2, 1) ...]

combinations (조합)

from itertools import combinations

arr = [0, 1, 2, 3]

# 첫번째 인자로 배열을 두번째 인자로 조합할 개수를 넣어주면 된다.
# 순서가 달라도 같은 경우 이기 때문에 중복되는 수로 형성된 조합은 포함되지 않는다.

for i in combinations(arr, 4):
	print(i)

# 순서가 바뀌어도 같은 경우이기 때문에 경우의 수가 순열에 비해 훨씬 적다.
print(list(combinations(arr, 3)))
# [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]