백트래킹
백트래킹(backtracking)은 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙)해 정답을 찾아가는 기법이다.
백트래킹 기법은 Promising(유망성 판단)과 Pruning(가지치기) 두 가지 요소를 가지고 있다.
보통 유망성 판단은 is_promising() 함수를 활용해서 판단하기도 하고 가지치기는 is_promising() 함수에서 유망하지 않다고 판단되면 return을 해서 가지치기를 하는 것이다.
원래 정의는 위의 정의가 맞지만, dfs에서 visited를 철회해서 모든 경우의 수를 탐색하는 것을 백트래킹이라고 하기도 하는 것 같다.
n = int(input())
ans = 0
row = [0] * n
def is_promising(x):
for i in range(x):
if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i):
return False
return True
def n_queens(x):
global ans
if x == n:
ans += 1
return
else:
for i in range(n):
row[x] = i
if is_promising(x):
n_queens(x + 1)
n_queens(0)
print(ans)순열
순열이란 순서와 상관없이 나올 수 있는 모든 조합의 수를 말한다.
10 ~ 12번째 라인이 백트래킹을 이용해서 visited를 철회하고 예를 들어서 첫 번째 백트래킹에서 1을 시작으로 하는 순열을 구했다면 두 번째 백트래킹에서 1을 제외하고 2를 시작으로 하는 순열을 구하는 것이다.
def main(nums:list) :
def backtracking(cur) :
# base case
if len(cur) == nums_len :
result.append(cur[:])
return
for num in nums :
if num not in cur :
cur.append(num)
backtracking(cur)
cur.pop()
result = []
backtracking([])
return result
print(main([1,2,3,4]))위의 코드에서 result.append(cur[:]) 부분을 result.append(cur)로 바꾸면 result에 빈 리스트들이 다수 들어가게 된다.
이는 깊은 복사와 얕은 복사의 차이 때문인데, cur[:]는 얕은 복사를 의미하며 cur의 값들을 모두 복사해서 새로운 cur2를 만든다고 생각하면 되고
result.append(cur)은 깊은 복사를 의미하는데 cur의 주소값을 recurssion을 하면서 계속 바꾸다가 결국 마지막에는 cur.pop()으로 인해서 빈 리스트가 되기 때문에 빈 리스트가 다수 들어가게 되는 것이다.
조합
Q. nums = [1,2,3,4] 일 때, 2개의 숫자로 이루어진 조합을 구하시오.
def main(nums:list, k:int) :
nums_len = len(nums)
def backtracking(cur, i) :
# base case
if len(cur) == k :
result.append(cur[:])
return
for j in range(i, nums_len) :
cur.append(nums[j])
backtracking(cur, j + 1)
cur.pop()
result = []
backtracking(cur=[], i=0)
return result
print(main(nums=[1,2,3,4], k=2))부분집합
부분집합은 순열의 코드에서 K를 0~len(nums) + 1까지 전부를 구해서
0개인 집합, 1개입 집합, 2개인 집합, ... len(nums)개인 집합을 구하는 것이다.
def main(nums:list) :
nums_len = len(nums)
def backtracking(cur, i) :
# base case
if len(cur) == k :
result.append(cur[:])
return
for j in range(i, nums_len) :
cur.append(nums[j])
backtracking(cur, j + 1)
cur.pop()
result = []
for k in range(0, len(nums) + 1) :
backtracking(cur=[], i=0)
return result
print(main(nums=[1,2,3,4]))예시 문제
Q. nums = [4,9,7,5,1] 일 때, 2개의 숫자로 이루어진 조합 중에서 합이 12가 될 수 있나요?
여기서 중요한 점은 ret이라는 변수에 result를 return 해줌으로써 재귀함수를 끝내는 것이다.
cnt = 0
def main(nums, k) :
len_nums = len(nums)
def backtracking(cur, idx) :
global cnt
cnt += 1
if len(cur) == 2 :
if sum(cur) == k :
ans = True
return cur
for i in range(idx, len_nums) :
cur.append(nums[i])
ret = backtracking(cur=cur, idx=i+1)
if ret :
return ret
cur.pop()
return None
result = backtracking(cur=[], idx=0)
if result :
print(f"될 수 이따아아ㅏ result : {result} cnt : {cnt}")
else :
print("안된다 이놈아아ㅏ{cnt}")
main(nums=[4,9,7,5,1],k=12)