728x90
순열과 조합의 차이는 순서에 상관이 있는지 없는지이다. 조합에서는 순서가 없기 때문에 시작점보다 작은 위치는 다시 방문하지 않는다. 그러나, 순열은 순서가 있기 때문에 시작점보다 작은 위치 또한 방문해야 한다.
라이브러리없이 구현하는 방법은 dfs 알고리즘을 이용하는 것인데, 그 중에도 재귀를 이용하여 구현할 수 있다.
순열(permutation)이란, 서로 다른 n개 중에서 순서에 상관하여 r개를 뽑는 경우의 수이다.
arr = [1, 2, 3, 4]
select = [False for _ in range(4)]
result = []
def dfs(cnt):
if cnt == 3:
print(*result)
return
for i in range(4):
if not select[i]:
select[i] = True
result.append(arr[i])
dfs(cnt + 1)
result.pop()
select[i] = False
dfs(0)
조합(combination)이란, 서로 다른 n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수이다.
arr = [1, 2, 3, 4]
select = [False for _ in range(4)]
result = []
def dfs(idx, cnt):
if cnt == 3:
print(*result)
return
for i in range(idx, 4):
if not select[i]:
select[i] = True
result.append(arr[i])
dfs(i + 1, cnt + 1)
result.pop()
select[i] = False
dfs(0, 0)
728x90
'알고리즘' 카테고리의 다른 글
알고리즘의 성능 분석(시간 복잡도, 공간 복잡도, 빅오 표기법) (0) | 2023.04.10 |
---|---|
0-1 BFS(0-1 Breadth First Search) 알고리즘 (0) | 2023.02.08 |
★ 코딩 테스트에 나오는 알고리즘/문제 유형 총정리 (0) | 2023.02.01 |
6가지 대표적인 정렬 알고리즘(Sorting Algorithm) (1) | 2022.12.29 |
10진수를 2진수로 - 파이썬 (0) | 2022.12.22 |