[python] 백트래킹(backtracking)

0. 들어가면서

 일단, 개념위주가 아니라 실전 문제 푸는 스킬위주로 적을예정이다. 그리고 백트래킹에 대해 가능한 모든 내용을 담을 예정이다. 즉, 계속 업데이트가 될 것이며, 쭉 이해만 하면 관련문제는 풀 수 있을 것이다. 따라서  python 을 활용한 코드뿐만아니라 알고리즘과 관련된 모든 유형의 문제에 관련된 풀이들도 추가할 예정이다. 일단, 기본적으로 재귀를 쓰기 때문에 DFS와 BFS를 구현하지 못한다면 이부분이 어려울 수 있다. 시작해보도록 하자.

 

1. 백트래킹

 백트래킹 기법은 해를 찾는 도중에 '막히면' 되돌아가서 다시 해를 찾아 가는 기법이다. 일명 가지치기라고도 한다.

=> 재귀를 이용한 완전 검색을 하고 가지치기를 추가하는 기법

 

백트래킹으로 최적화문제(optimization)와 결정문제(decision)를 해결 할 수있다. 여기서 결정문제란 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes/no로 답하는 문제이다.

ex_ 미로찾기, n-Queen 문제, Map coloring, 부분집합의 합 문제 등에서 활용된다.

 

 

정리_

- 백트래킹은 완전검색과 가지치기이다.

- 백트래킹은 재귀를 사용한다.

- 순열(일반순열, 중복순열), 조합(중복조합, 일반조합), 부분집합 부분은 기본으로 코드 구현이 필요하다.

 

 

 

 

 

2. 백트래킹에서 부분집합

 우선은 완전검색부터 하자.

 

#부분집합 기본코드
def printSet(n):
    for i in range(n):
        if A[i] == 1:
            print(data[i], end = " ")
    print()
    
def powerset(k, n):            # k는 A배열의 k인덱스의 포함 유무를 판별한다.
    if n == k:
        printSet(k)
    else:
        A[k] = 1
        powerset(k+1, n)       # 배열 A에 체크하고 다음 인덱스로 넘어간다
        A[k] = 0               # 재귀로 되돌아와서 체크 했던걸 다시 원상복귀시킨다
        powerset(k+1, n)

data = 구하려는 리스트
n = len(data)                  # 부분집합을 구하는 리스트의 수
A = [0]* n                     # 포함 유무를 체크할 리스트 (0이 미포함, 1이 포함)

 

백트래킹은 완전검색에서 가지치기를 한 것이다. 아래는 가지치기를 하는 코드이다.

# 부분집합의 합
def powerset(k, n, sum):
    if sum > 10:          # 부분집합의 합을 구하는 문제에서 구하고자하는 값인 10을 넘는다면 더이상 계산할 필요가 없으므로 return해버린다.(가지치기)
        return
    if n == k:
        printSet(k, sum)
    else:
        A[k] = 1
        powerset(k+1, n, sum+data[k])       
        A[k] = 0               
        powerset(k+1, n, sum)

 

사실 쉽게 말해서 백트래킹은 불필요한 계산낭비를 방지한는 방식이라고 할 수 있다.

 

 

 

 

 

 

_코딩테스트 유형별 마스터하기

[코딩테스트] 문자열 유형 완벽 정리_1

[코딩테스트] 문자열 유형 완벽 정리_2