[SW Expert Academy] 파이썬 SW문제해결 응용_구현 - 05 백트래킹

* 본 글은 SW Expert Academy에서 제공하는 강의를 요약한 것입니다.

 

백트래킹(Backtracking)은 '퇴각검색'으로도 불리며, 위키백과에서는 '한정  조건을 가진 문제를 푸는 전략'으로 정의하고 있다. 이 알고리즘은 선택지를 트리 구조로 표현하고, 이를 탐색하는 방식으로 해를 찾게 된다.

 

백트래킹을 통해 풀 수 있는 문제로는 최적화(Optimization), 결정(Decision) 문제가 있다. 최적화 문제는 주어진 조건 내에서 목표 값을 가장 좋게 만드는 해를 찾는 문제이며, 결정 문제는 해의 존재 여부가 해가 된다.

 

이 알고리즘을 통해 문제해결을 하기 위해 선택지를 트리 구조로 표현하게 되는데, 이 때 만들어진 트리를 '상태공간트리'라고 한다. 상태공간트리의 노드는 다음을 표현한다.

 

• 노드(leaf 제외): 최종 상태로 가는 중간 상태. 해로서 활용될 수 있는 값이 부분적으로만 나타남
• leaf 노드: 최종 상태. 해로서 활용될 수 있는 값

백트래킹은 깊이 우선 탐색 방법을 차용하여 알고리즘이 수행되나, 내려가던 중 중간 상태의 노드가 해로서 활용될 수 없다 판단이 되면 더이상 내려가지 않는다.(Prunning)

 

탐색의 빈도는 모든 경우를 탐색하는 깊이우선탐색보다 적지만, 여전히 지수적(exponential)한 특성을 가지고 있다.

 

백트래킹 알고리즘을 코드로 표현하면 다음과 같다.

def checknode(v): #node
	if promising(v):
    	if there is a solution at v:
        	write the solution
        else:
        	for u in each child of v:
            	checknode(u)

 

---

강의에서 제시한 관련 예시 문제들은 다음과 같다.

 

1. n-Queen

n-퀸 문제는 n x n의 체스판에서 n개의 퀸이 서로를 위협하지 않는 위치에 배치하는 문제이다. 퀸이 서로를 위협하지 않는다는 것은 퀸을 중심으로 둘러싸고 있는 8개의 칸에 배치되지 않는 것을 의미한다.

 

2. 부분집합

부분집합 문제에서는 'power set'이란 개념을 제시하고 있다. power set은 임의의 집합에 대해 공집합과 자기 자신을 포함한 모든 부분집합을 의미한다. 이 때, n개의 원소를 가진 집합의 부분집합은 2^n개 이다. 상태공간트리에서는 이를 0과 1을 통해 표현하며, 이는 부분집합이 해당 깊이에서 고려하는 원소를 포함하는지 여부를 나타낸다.

#a[0,,,n-1]: 집합에 대한 비트 표현 저장, 크기는 원소의 수
#k: 선택한 횟수(guswo shemdml shvdl), n: 모든 선택 수(트리의 높이)

def subset(a,k,n):
    if k==n:
        process_solution(a,n)
    else:
        a[k]=0
        subset(a,k+1,n)
        a[k]=1
        subset(a,k+1,n)

 

 

3. 순열

상태공간트리에서 각각의 높이는 순서를 의미한다. 해당 순서에서 어떤 원소를 선택하느냐의 문제가 되어, 각 노드에서 분기(branching)되는 개수는 (선택가능한 원소의 수) -  (결정된 원소의 수) 가 된다.

#order[]: 순열의 순서를 저장하는 리스트
def permuation(order, k, n):
    if k==n:
        print_order_array(order,n)
    else:  
        check=[False] * n
        for i in range(k):
            check[order[i]] = True

        for i in range(n):
            if check[i]==False:
                order[k]=i
                permuation(order, k+1, n)

 

4. 동전 거스름돈 문제

가장 적은 동전의 개수로 거스름돈을 나타낼 수 있는 해를 찾는 문제이다.

 

예를 들어, 800원의 거스름돈을 가장 적은 동전의 개수로 거슬러 줘야한다고 할 때, 최초의 노드는 800원에서 시작하며, 각각의 리프는 동전의 종류에 따라 나뉘어지게 된다.

 

# coin[]: 동전의 금액을 저장, choice[]: 선택한 동전들 집합
# best: 거스름돈에 대한 최소 동전 개수
def CoinChange(choice, N, money):
    global best
    if best <= N:
        return
    elif money == 0:
        best = N
    else:
        for i in range(len(coin)):
            if money - coin[i] >= 0:
                choice[N] = coin[i]
                CoinChange(choice, N+1, money - coin[i])

 

이 외에도 한정된 해의 범위를 갖는 문제를 해결하는데 백트래킹 알고리즘을 활용할 수 있다.