[SW Expert Academy] Advanced-5 백트래킹
백트래킹기법은 해가 아니면 되돌아가서 다시 해를 찾아가는 기법을 말한다. 기존에 잘 알려진 DFS(깊이 우선 탐색)에 가지치기를 접목한 것이다. 여기서 해를 찾기 위한 과정을 트리로 표현한 것을 상태 공간 트리라고 한다. 가지치기를 잘 하면 일반적으로 경우의 수가 줄어 처리가 가능해진다. 여기서 부분집합, 순열은 완전 탐색에서 배운 내용과 연결된다.
플로우 1.8queens 문제 2. 부분 집합 3. 순열 4. 동전 거스름돈 문제
플로우 1.8queens 문제 2. 부분 집합 3. 순열 4. 동전 거스름돈 문제
1. 8queens 문제
-8*8 체스판에 8개의 퀸을 배치하되, 서로를 위협하지 않도록 배치하는 문제
1) 각 퀸은 서로 다른 row를 가지므로, 각 row에 하나씩 배치
2) 백트래킹기법을 이용하여 col의 위치를 고려함
-> 상태 공간 트리를 탐색하다가, 후보가 될 수 없는 경우의 수에는 탐색을 멈춤 (가지치기)
-일반적인 백트래킹 알고리즘
checknode (node v):
if promising (v):
if there is a solution at v:
write the solution
else
for each child u of v:
checknode(u)
-> 일반적으로 promising을 윗줄이 아닌, 아래의 checknode()직전에 체크한다.
2. 부분집합
-Power set: 어떤 집합의 공집합과 자기자신을 포함한 모든 부분 집합 (2^n개)
-n개의 비트열을 이용해 부분 집합 표현이 가능함
-부분 집합 알고리즘
//bit[0, ... , n-1] : 집합에 대한 비트 표현 저장, 크기는 원소의 수
//k : 선택한 횟수(현재 노드의 높이), n: 모든 선택의 수(트리의 높이)
subset(bit[], int k, int n):
if(k==n):
print_bit_array
else:
bit[k] <- 0
subset(bit, n, k+1)
bit[k+1] <- 1
subset(bit, n, k+1)
->솔직히 이게 무슨 의미의 코드인지 이해 못함
->결국 비트가 점진적으로 증가하는 것을 배열에 표현한 것에 불가하지 않은가?
->for문으로 비트를 증가시키면서 탐색하는것이랑 다를 게 있나?
3. 순열
-수도 코드
//order[]: 순열의 순서를 저장하는 배열
permutation(order[], k, n):
if k = n:
print_order_array
else
check[] <- { false }
for i <- 0 to k-1:
check[order[i]] = true
for i <- 0 to n-1:
if(check[i] = false):
order[k] = i
permutation(order, k+1, n)
4. 동전 거스름돈 문제
-수도 코드
//coins[]: 동전의 금액 저장
//choices[]: 선택한 동전들 집합
//best: 거스름돈에 대한 최소 동전 갯수
//COIN_NUM: 돈전의 가짓수
CoinChange (choices[], N, money):
if(money = 0):
if(best > N):
best <- N
else:
for i <- 0 to COIN_NUM -1:
if(money - coin[i] >= 0):
choices[N] <- coin[i];
CoinChange(choices, N+1, money-coin[i])
댓글
댓글 쓰기