코딩테스트 문제를 매일 풀면서 순열과 조합 문제가 나오면, 전혀 접근을 못 하는 것 같아 다시 정리합니다.
유튜버 딩코딩님의 강의를 보고 참고했습니다.

순열(permutation)

서로 다른 n개의 원소에서 r개를 중복없이 순서대로 선택하고 나열하는 것을 순열이라 한다.

순열의 특징은 같은 원소더라도, 순서가 다르면 경우의 수로 추가할 수 있다는 것 이다.

원리는 정말 쉽지만, 생각보다 실제 구현은 정말 어렵다. 재귀를 통한 DFS 트리와 체크리스트를 이용하면 된다.

# 직접 구현
def DFS(L) :
	if L == r :# 종료 조건
		print(result)
	else :
		for i in range(len(n)) :
			if checklist[i] == False :
				result[L] = n[i]
				checklist[i] = True
				DFS(L + 1)
				checklist[i] = False

n = [1, 2, 3]
r = 2

result = [0] * r # 출력할 리스트
checklist = [False] * len(n) # 체크리스트

DFS(0)

# 모듈 이용
from itertools import permutations

for i in permutations([1, 2, 3], 2):
    print(i, end=" ")

조합(Combination)

서로 다른 n개 중에서 r개를 선택하는 경우의 수를 조합이라 한다. 순열과는 다르게 순서가 상관이 없어 중복을 허용하지 않는다.

조합도 DFS를 이용하면 되는데, 체크리스트가 필요 없고 다음 시작점을 반환해야한다.

# 직접 구현
def DFS(L, BeginWith) :
    if L == r :
        print(result)
    else :
        for i in range(BeginWith, len(n)) :
            result[L] = n[i]
            DFS(L + 1, i + 1)

n = [1, 2, 3]
r = 2

result = [0] * r
DFS(0, 0) # level : 깊이 , BeginWith : 다음 시작점

# 모듈 이용
from itertools import combinations

for i in combinations([1, 2, 3], 2):
    print(i, end=" ")

중복 순열

중복 순열은 순열과 같은 방식이지만, 원소를 중복으로 사용하여 사용할 수 있다.

중복이 가능하니, 위에서 구현한 순열에서 체크리스트 처리를 안해주면 된다.

def DFS(L) :
    	# 종료 조건
	if L == r :
		print(result)
	else :
		for i in range(len(n)) :
			result[L] = n[i]
			DFS(L + 1)
	
n = [1, 2, 3]
r = 2

result = [0] * r # 출력할 리스트

# 모듈 이용
from itertools import product

for i in product([1,2,3], repeat=2):
    print(i, end=" ")

중복 조합

중복 조합도 마찬 가지로 원소들의 중복을 허용하는 조합이다.

조합에서는 다음 시작점을 반환하는데, 중복 조합에서는 시작점을 현재 위치로 반환해주면 된다.

def DFS(L, BeginWith) :
    if L == r :
        print(result)
    else :
        for i in range(BeginWith, len(n)) :
            result[L] = n[i]
            DFS(L + 1, i)

n = [1, 2, 3]
r = 2

result = [0] * r
DFS(0, 0) # level : 깊이 , BeginWith : 다음 시작점

# 모듈 이용
from itertools import combinations_with_replacement

for i in combinations_with_replacement([1,2,3], 2):
    print(i, end=" ")

---

풀어볼 문제들

백준 - 완전검색-순열조합