파이썬의 장점으로 itertools와 같은 라이브러리를 불러와서 사용할 수 있지만, 알고리즘적으로 순수 구현해보려고 한다.
파이썬에서 순열과 조합을 직접 구현하는 방법은 주로 DFS(깊이 우선 탐색) 기반으로 작성된다.
* 순열은 순서가 중요한 경우, 조합은 순서가 중요하지 않은 경우를 의미
1. 순열 (Permutation)
- 순열은 주어진 리스트에서 순서대로 나열하는 모든 경우의 수를 생성
1. 빈 리스트에서 시작하여, 각 단계에서 아직 사용하지 않은 요소를 하나씩 선택해 추가
2. 요소를 선택할 때마다 그 요소를 제외한 나머지 요소들로 계속해서 탐색을 진행
3. 길이가 n인 리스트에서 n개의 요소를 모두 선택했을 때, 해당 경우의 수를 완성
def perm(arr):
result = []
def dfs(path, used):
if len(path) == len(arr):
result.append(path[:])
return
for i in range(len(arr)):
if not used[i]:
used[i] = True
path.append(arr[i])
dfs(path, used)
path.pop()
used[i] = False
dfs([], [False]*len(arr))
return result
arr = [1, 2, 3]
print(perm(arr))
위 코드의 dfs(path, used)는 재귀적으로 현재 경로(path)와 사용 여부 리스트(used)를 통해 탐색을 진행한다.
각 재귀 호출에서 아직 선택되지 않은 요소를 선택하고, 그 다음 깊이로 들어가 탐색을 계속함
탐색을 끝낸 후에는 선택했던 요소를 다시 원래 상태로 되돌려주어야 다음 경로에서 다른 선택을 할 수 있다!
2. 조합 (Combination)
- 조합은 주어진 리스트에서 순서와 상관없이 정해진 개수만큼 선택하는 경우의 수
1. 리스트의 요소를 선택할 때, 앞에서 선택한 요소보다 뒤에 있는 요소들만 선택
2. 순서가 상관없으므로 중복되지 않도록, 현재 선택한 요소의 이후에 있는 요소들만 재귀적으로 탐색
3. 원하는 개수만큼 선택했을 때, 조합이 완성됨
def combinations(arr, r):
result = []
def dfs(start, path):
if len(path) == r: # 원하는 개수만큼 선택되었을 때
result.append(path[:]) # 결과에 추가
return
for i in range(start, len(arr)):
path.append(arr[i]) # 요소 추가
dfs(i + 1, path) # 그 다음 요소부터 탐색 (start → i + 1)
path.pop() # 되돌리기 (백트래킹)
dfs(0, []) # 처음에는 0번째 요소부터 선택
return result
# 예시
arr = [1, 2, 3, 4]
print(combinations(arr, 2))
dfs(start, path)는 재귀적으로 선택된 요소 리스트 (path)와 탐색 시작 인덱스(start)를 통해 진행된다.
start 는 중복된 선택을 방지하기 위해 사용되며, 현재 선택한 요소의 다음 요소부터 탐색하도록 설정됨
요소를 선택한 후에는 다음 요소를 탐색하기 위해 재귀적으로 호출하고, 탐색이 끝나면 이전 상태로 되돌려줌 (백트래킹)
'Python' 카테고리의 다른 글
[백준/Python] 1213 : 펠린드롬 만들기 (0) | 2024.09.08 |
---|---|
[백준/Python] 11478 : 서로 다른 부분 문자열의 개수 (0) | 2024.09.07 |
[백준/Python] 2960 : 에라토스테네스의 체 (0) | 2024.08.25 |
[백준/Python] 1929 : 소수 구하기 (0) | 2024.08.25 |
[Python] 파이썬 random 모듈 내장 함수 정리 (0) | 2024.08.25 |