퇴각 검색(BackTracking)

반복하는데 귀신인 컴퓨터에 적당한 방법이다. 가능한 경우를 모두 검사(exhaustive search)하는 무식한(?)방법이다.

답 내는 것이 문제가 아니라 얼마 만큼의 빠른 시간에 작업을 끝낼수 있는 가를 고민해야 되는 파트.

가능성이 없는 것은 미리 잘라버리는 것이 관건이다. 예를 들어, 3 번의 시합에서 2 번 우승하면 이기는 게임에서 미리 2 번 이기면 나머지 한 번은 할 필요가 없다. 이런 가능성을 생각해서 미리 많이 잘라버리면 그 만 큼의 실행시간이 빨라진다.

가능한 경우를 모두 검사하는 방법에는 보통 두 가지 유형의 문제로 나뉠수가 있다.

• 부분집합형 백트래킹
• 팩토리얼형 백트래킹

예를 들어 , 주머니 속에 7 개의 공이 있고 , 각 공에는 번호가 부여되어 있다.

부분집합형

주머니에서 몇 개의 공을 꺼내어 합이 13 이 공들을 찾는 경우에는 2^7 가지의 부분집합을 모두 검사해야 한다.

한 개 뽑는 경우

• 6
• 2
• 9
• ..

두 개 뽑는 경우

• 6 , 2
• 6 , 9
• 6 , 8
• ...

세 개 뽑는 경우

• 6 , 2 , 9
• 6 , 2 , 8
• ...

...

7 개 모두 뽑는 경우

• 6, 2, 9 , 8 , 3 , 4 , 7

팩토리얼 형

7 개의 공을 임의로 나열했을 때 인접한 수의 곱이 최대 인 경우는 어떤 경우인가를 알고자 할 때 7! 가지의 모든 경우를 생각해야 하므로 이는 팩토리얼 형 문제라고 생각할 수 있다.

• 6 2 9 8 3 4 7
• 6 2 9 8 3 7 4
• ...

(문제) sum of subset 

6 , 1 , 9 , 8 , 3 , 4 , 7

총 합은 38 , 합은 반은 19 이다.

이 수들을 적절히 뽑아 19 를 만들 수 있는 방법의 수를 구하는 문제.

부분 집합형 문제의 기본 틀

첫째 원소, 둘째 원소 2 개 있을 때 부분집합의 수는 4 개이다.

• 2 가지 모두 포함하는 경우 (o o)
• 첫 원소 포함 , 둘째 원소 포함하지 않는 경우 (o x)
• 첫 원소 포함하지 않고 , 둘째 원소 포함하는 경우(x o)
• 2 가지 모두 포함하지 않는 경우 (x x)

o 를 1 로 x 를 0 으로 놓으면 ,

• 1 , 1
• 1 , 0
• 0 , 1
• 0 , 0

원소의 수가 2 개 일 때

이를 구현하기 위해 배열(배열명을 include[] 라 하자)을 사용하여

원소의 수가 3 개일 때

(샘플 문제)수의 부분합 문제로 조금씩 실행 속도를 높여 보기로 하자. 문제는 전제 합의 반 50 이되는 원소를 골라내는 문제이다. 
주어지는 데이터는 40 20 30 10 (수의 부분합 풀이)

int data[]={0,40,20,30,10}; int include[5]; int promising(int total,int remaining) // 이 함수를 유망함수라 함 { if (total > 50||total+ remaining < 50) return 0; return 1; } void process(int i,int total,int remaining) { int k; if (promising(total,remaining)) if (i==4){ if (total==50){ for(k=1;k<=4;k++) if (include[k]==1) printf("%d ",data[k]); printf("\n"); } }else{ include[i+1]=1; process(i+1,total+data[i+1],remaining-data[i+1]); include[i+1]=0; process(i+1,total,remaining-data[i+1]); } } main() { process(0,0,100); }