[알고리즘] 순열 & 조합 알고리즘(Python)

* 개요

순열과 조합 알고리즘은 대표적인 완전 탐색 알고리즘으로, 경우의 수를 구할 때 사용하는 알고리즘이다. 순열과 조합은 실제 코딩 테스트에서 필요한 경우가 많기 때문에, 어떻게 사용할 수 있는지를 알고 있어야 한다. 사실 순열과 조합은 재귀 함수 혹은 반복문을 이용해서 직접 구현할 수도 있지만, 실제 코딩 테스트에서 이를 직접 구현하는 것은 매우 번거롭다. 먼저 순열에 대해서 확인해보자. 순열이란 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것을 의미한다. 그렇다면 조합은 무엇인가? 조합이란, 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것을 의미한다.순열에서는 [1, 2, 3]에서 서로 다른 2개의 원소를 뽑아 나열할 때 가능한 모든 순서를 고려하기 때문에, [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]가 존재한다. 하지만 조합에서는 [1, 2], [1, 3], [2, 3]만 존재한다.

 

* 파이썬으로 구현한 순열 알고리즘

코딩 테스트에서는 경우의 수 값만 출력하는 것이 아니라 모든 경우를 다 출력하도록 요구하기도 한다. 이럴 때는 파이썬의 itertools 라이브러리를 이용한다. 순열은 itertools의 함수들 중 permutations 함수를 사용하여 구현한다.

from itertools import permutations

data = [1, 2, 3]

# data에서 2개를 뽑아 일렬로 나열하는 경우의 수
result = list(permutations(data, 2))

print(result) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

 

* 파이썬으로 구현한 조합 알고리즘

파이썬에서 조합을 이용하기 위해서는 itertools의 combinations 함수를 이용하면 된다.

from itertools import combinations

data = [1, 2, 3]

# data에서 2개를 뽑지만 순서와는 관계없는 경우의 수
result = list(combinations(data, 2))

print(result) # [(1, 2), (1, 3), (2, 3)]