1. 조합 알고리즘
•
조합과 순열의 차이
◦
조합은 순서라는 개념이 존재하지 않음.
◦
순열은 순서라는 개념이 존재함
조합과 순열 예시
•
조합 알고리즘이란?
◦
조합 알고리즘: n개의 원소 중에서 r개를 뽑는 모든 경우를 살펴보는 알고리즘
◦
조합 알고리즘을 구현하는 방법
1.
for문을 이용 
: for 문을 이용하면 for문을 r개 사용해야 하므로 확장성이 좋지 않다.
2.
재귀함수를 이용
: 재귀함수를 이용하면 r을 인자로 받아 처리할 수 있어 확장성이 좋다.
◦
조합 알고리즘의 시간 복잡도
▪
조합 알고리즘은 n개의 원소 중에서 r개를 뽑는 모든 경우를 살펴본다.
▪
따라서, 시간 복잡도는 이라고 할 수 있다.
2. 조합 알고리즘 구현 (재귀함수)
•
재귀함수를 이용하여 조합 알고리즘 구현
N = 10
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, N):
choose.append(lst[i]) # 인덱스가 i인 원소를 선택(추가)
combination(i+1, level+1) # 다음 for 문으로 들어가는 역할
choose.pop() # (넣었던) 인덱스가 i인 원소를 제거
combination(0, 0)
Python
복사
◦
index: ‘이전에 선택한 원소 인덱스 + 1’을 의미
◦
level: 현재 선택한 원소의 개수 (깊이를 의미)
◦
현재 선택한 원소(level)가 R이면, 그때 R만큼 고른 것이니 처리해 주면 된다.