순열과 조합 그리고 브루트 포스

브루트 포스 (Brute-force) 는 '무차별 대입' 이라는 의미이다. 말 그대로 모든 경우의 수를 대입해보는 것이다. 완전탐색 전략을 사용하여 확실하게 답을 구하는 알고리즘이지만 단점은 시간복잡도에 있다. 모든 경우를 돌아보기 때문에 문제에서 시간초과가 발생 할 수 있다. 다음 문제를 보자.

 

N개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는?

브루트 포스를 사용한다면 2중 for문을 돌면서 두 수를 골라 더해서 최댓값을 갱신하면 '두 수를 뽑는 모든 경우'를 살펴보게 되고, 답을 확실하게 구할 수 있다. 이때 시간 복잡도는 O(N^2)이 된다.

 

버뜨 list 사용해서 최댓값 찾고 그 두개를 더하면 시간복잡도는 O(NlogN)이다. 

브루트 포스로 문제를 풀 때는 반복문을 사용할 때도 있고, 재귀로 풀 때도 있다.

 

---

순열 (Permutation)

순연을 n개의 수 중 r개를 뽑아 줄세우는 경우의 수이다. 뒤에 설명할 조합보다 경우의 수가 더 많다.

표기 방법은 5P2 이렇게 P 대문자로 표기한다. 의미는 5개 중 2개를 뽑아 줄세운다는 의미이다.

파이썬에서 순열은 itertools의 permutations를 import 해서 사용할 수 있다.

from itertools import permutations

arr = [0,1,2,3]

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

# 출력
"""(0, 1, 2, 3)
(0, 1, 3, 2)
(0, 2, 1, 3)
(0, 2, 3, 1)
(0, 3, 1, 2)
(0, 3, 2, 1)
(1, 0, 2, 3)
(1, 0, 3, 2)
(1, 2, 0, 3)
(1, 2, 3, 0)
(1, 3, 0, 2)
(1, 3, 2, 0)
(2, 0, 1, 3)
(2, 0, 3, 1)
(2, 1, 0, 3)
(2, 1, 3, 0)
(2, 3, 0, 1)
(2, 3, 1, 0)
(3, 0, 1, 2)
(3, 0, 2, 1)
(3, 1, 0, 2)
(3, 1, 2, 0)
(3, 2, 0, 1)
(3, 2, 1, 0)"""

조합 (Combination)

n개의 수 중에서 r개를 뽑는것이 조합이다. 

파이썬에선 itertools의 combination을 import  해서 사용할 수 있다.

from itertools import combinations

arr = [0,1,2,3]

for i in combinations(arr, 2):
	print(i)
    
# 출력
"""(0, 1)
(0, 2)
(0, 3)
(1, 2)
(1, 3)
(2, 3)"""