💡 Algorithm
Algorithm - [ 백트래킹 ]
date
Jul 4, 2023
slug
algorithm-06
author
status
Public
tags
Python
Algorithm
summary
‘되돌아가기(backtrack)’를 사용하여 전체 탐색을 수행하면서, 가능한 모든 조합을 확인하는 기법
type
Post
thumbnail
category
💡 Algorithm
updatedAt
Jul 28, 2023 07:29 AM
백트래킹
‘되돌아가기(backtrack)’를 사용하여 전체 탐색을 수행하면서, 가능한 모든 조합을 확인하는 기법
백트래킹 알고리즘의 핵심은 '되돌아가기(backtrack)'이다. 어떤 경로를 따라 탐색하다가 유효하지 않은 상황을 만나면, 이전 단계로 되돌아가서 다른 선택을 시도한다. 이러한 되돌아가기를 반복하면서 모든 가능한 조합을 탐색한다.
그리디와 백트래킹의 차이
- 그리디 알고리즘
- 각 단계에서 가장 유리한 선택을 하는 것을 반복하면서 지역적으로 최적해를 구한다.
- 최적해에 도달하지 못하는 경우와 같이 최적해를 보장하지는 않을 수 있지만, 빠른 솔루션을 제공한다.
- 그리디 알고리즘은 최적 부분 구조와 탐욕 선택 속성을 가진 문제에 적용된다.
- 백트래킹 알고리즘
- 일반적으로 DFS 를 기반으로 하는 재귀 함수를 주로 사용하여 모든 가능한 조합을 탐색하며, 유효한 상황은 계속 진행하고 유효하지 않은 상황에서는 이전 단계로 되돌아가서 다른 선택을 시도한다.
- 백트래킹 알고리즘은 모든 가능한 경우를 고려하기 때문에 일반적으로 더 많은 시간과 계산 자원을 요구한다.
- 백트래킹 알고리즘은 일반적으로 모든 해를 찾거나 특정 조건에 맞는 해를 찾을 때 사용된다.
백트래킹 알고리즘 구조
백트래킹은 3단계로 재귀 호출한다.
- 원소 넣기
- 재귀 호출
- 원소 빼기
경우의 수
- 순열: itertools.permutation()
N개의 원소 리스트에서 중복 없이 M개를 골라 만든 수열
N개에서 M개를 고르기 (순서가 다르면 다른 경우)
- 조합: itertools.combination()
N개의 원소 리스트에서 중복 없이 M개를 골라 만든 수열
순서가 달라도 원소가 동일하면 같은 경우
- 중복 순열: itertools.product()
N개의 원소 리스트 중에서 중복을 허용해서 M개를 골라 만든 수열
N개에서 M개를 고르기 (순서가 다르면 다른 경우)
- 중복 조합: itertools.combinations_with_replacement()
N개의 원소 리스트에서 중복을 허용해서 M개를 골라 만든 수열
순서가 달라도 원소가 동일하면 같은 경우
- 백트래킹 → 순열
# 순열 import sys sys.setrecursionlimit(int(1e6)) n, m = map(int, input().split()) arr = [i for i in range(1, n + 1)] visited = [False] * n # 각 원소가 선택되었는가 selected = [] # 현재 경우에서 선택된 원소들 # depth: 현재 재귀에서 선택된 원소의 개수 def dfs(depth): if depth == m: # 실제로 현재 경우에 대하여 처리하는 부분 for x in selected: print(x, end=" ") print() return for i in range(n): if visited[i]: continue # 백트래킹의 재귀 호출 3단계 # (1) 원소 넣기 selected.append(arr[i]) visited[i] = True # (2) 재귀 호출 dfs(depth + 1) # (3) 원소 빼기 selected.pop() visited[i] = False dfs(0)
참고:
return
문만 사용하여 함수를 종료하는 경우에는 값을 반환하지 않고, 단순히 함수의 실행을 종료한다. 이는 주로 재귀 함수에서 탈출 조건을 만족할 때 함수를 종료하고 이전 단계로 돌아가는 용도로 사용된다.- 백트래킹 → 조합
# 조합 import sys sys.setrecursionlimit(int(1e6)) n, m = map(int, input().split()) arr = [i for i in range(1, n + 1)] visited = [False] * n # 각 원소가 선택되었는가 selected = [] # 현재 경우에서 선택된 원소들 # depth: 현재 재귀에서 선택된 원소의 개수 def dfs(depth, now): if depth == m: # 실제로 현재 경우에 대하여 처리하는 부분 for x in selected: print(x, end=" ") print() return for i in range(now, n): if visited[i]: continue # 백트래킹의 재귀 호출 3단계 # (1) 원소 넣기 selected.append(arr[i]) visited[i] = True # (2) 재귀 호출 dfs(depth + 1, i) # (3) 원소 빼기 selected.pop() visited[i] = False dfs(0, 0)
순열과 달리 조합은 [1, 2, 3, 4, 5]가 있을 때, [1, 2, 4], [1, 2, 5]를 골랐다면 [1, 4, 2], [1, 5, 2]도 고르는 게 안 된다.
⇒ 따라서 현재보다 큰 인덱스만 고를 수 있도록 파라미터에 now 추가
- 백트래킹 → 중복 순열
# 중복 순열 import sys sys.setrecursionlimit(int(1e6)) n, m = map(int, input().split()) arr = [i for i in range(1, n + 1)] # visited = [False] * n # 각 원소가 선택되었는가 selected = [] # 현재 경우에서 선택된 원소들 # depth: 현재 재귀에서 선택된 원소의 개수 def dfs(depth): if depth == m: # 실제로 현재 경우에 대하여 처리하는 부분 for x in selected: print(x, end=" ") print() return for i in range(n): # if visited[i]: # continue # 백트래킹의 재귀 호출 3단계 # (1) 원소 넣기 selected.append(arr[i]) # visited[i] = True # (2) 재귀 호출 dfs(depth + 1) # (3) 원소 빼기 selected.pop() # visited[i] = False dfs(0)
중복 순열은 순열에서 방문 처리만 없으면 된다.
- 백트래킹 → 중복 조합
import sys sys.setrecursionlimit(int(1e6)) n, m = map(int, input().split()) arr = [i for i in range(1, n + 1)] # visited = [False] * n # 각 원소가 선택되었는가 selected = [] # 현재 경우에서 선택된 원소들 # depth: 현재 재귀에서 선택된 원소의 개수 def dfs(depth, now): if depth == m: # 실제로 현재 경우에 대하여 처리하는 부분 for x in selected: print(x, end=" ") print() return for i in range(now, n): # if visited[i]: # continue # 백트래킹의 재귀 호출 3단계 # (1) 원소 넣기 selected.append(arr[i]) # visited[i] = True # (2) 재귀 호출 dfs(depth + 1, i) # (3) 원소 빼기 selected.pop() # visited[i] = False dfs(0, 0)
중복 조합은 조합에서 방문 처리만 없으면 된다.