조합 알고리즘이란?
n개의 숫자 중 r개의 수들을 뽑는 모든 경우의 수를 구하는 것입니다.
순열 알고리즘과 다른 점은 수를 뽑는 경우의 수를 구하는 것이기 때문에 [1, 3, 2]와 [2, 1, 3]의 경우의 수를 동일하게 하나로 보고 센다는 것입니다.
공식 :
예시 : [1, 2, 3, 4, 5] 5개 중 3개를 뽑는 조합은 으로 나타낼 수 있습니다. 경우의 수들은 아래와 같습니다.
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]
의 계산 과정을 통해 총 10개의 결과가 나옵니다.
문제
각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다.
각 테스트 케이스마다 6개의 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.
풀이
풀이1. 재귀함수 활용하여 직접 구현
함수 이해하기
재귀함수를 활용하여 배열의 조합들을 구한 과정에 대해 이해해야 합니다. 아래 예시 함수를 확인해봅시다.
R = 5
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
choose = [] # 선택한 원소를 보관
def combination(index, level):
if level == R:
# 선택한 R 개의 원소를 출력
print(choose)
return
# for문
for i in range(index, len(lst)):
choose.append(lst[i]) # 인덱스가 i인 원소를 선택(추가)
combination(i+1, level+1) # 다음 for 문으로 들어가는 역할
choose.pop() # (넣었던) 인덱스가 i인 원소를 제거
combination(0, 0)이해해보기
조합을 구하기 위해선 구하고 싶은 요소의 개수만큼(저 위 코드에선 R만큼) for문을 중첩해서 써야합니다.
하지만 R이 몇이 잡힐지도 모르는데 해당 방법으로 구현하면 구현이 불가능하기 때문에, 재귀함수를 활용합니다.
index은 배열에서 탐색할 맨 처음 인덱스이고, level은 중첩된 단계입니다. 위의 경우에선 중첩이 R번째만큼 되어 choose배열에 요소가 5개 append되었을 때 조합 하나를 다 구한것이 되어 구해진 조합을 출력하고 이전 단계의 함수로 돌아가게 됩니다.
그리고 R개만큼 되지 않았을 때는 현재 Index의 다음 부터 탐색하여 현재 함수를 다시 호출해야하기 때문에 결과적으로 combination(i+1, level+1)를 재귀적으로 호출하게 됩니다.
문제 풀이 결과
count = 6
choose = []
def combination(index, level):
global S
if level >= count:
print(" ".join(map(str, choose)))
return
for i in range(index, len(S)):
choose.append(S[i])
combination(i+1, level+1)
choose.pop()
while True:
ipt = list(map(int, input().split()))
k = ipt[0]
S = ipt[1:]
if k == 0:
break
combination(0, 0)
print()위에서 설명한 조합 알고리즘 함수를 적용하였고, 입력에 0이 오기 전까지 배열을 입력받아 combination()함수를 실행하도록 설정하였습니다.
풀이2. combinations 라이브러리 사용하기
combinations 함수 알아보기
파이썬의 itertools 모듈에 포함된 함수이며 조합을 생성해주는 함수입니다.
combinations(arr, num)arr: 배열을 의미num: 뽑을 개수를 의미
문제 풀이 결과
from itertools import combinations
while True:
ipt = list(map(int, input().split()))
k = ipt[0]
S = ipt[1:]
if k == 0:
break
for choose in combinations(S, 6):
print(" ".join(map(str, choose)))
print()편하게 조합을 구할 순 있지만 조합을 구하는 과정에 커스텀이 필요한 문제가 있을 수도 있어서 직접 구현 방법도 잘 알아뇌야 합니다.