백트래킹 - "완전 탐색 + 가지치기" 완전 탐색을 하되, "답이 될 수 없는 방향" 을 조기에 포기하고 되돌아가는 기법 완전 탐색: 재귀 트리의 모든 잎(leaf)까지 내려간다. - 무조건 끝까지. 백트래킹: 트리의 중간 에서 "이 아래는 볼 필요 없다"고 판단하면 가지를 잘라낸다. × = "답이 될 수 없다" → 이 아래 전체를 건너뛴다는 의미 백트래킹의 핵심 두 요소 1) 유망성 판단 (Promising) :"현재 상태에서 더 진행해도 답이 될 가능성이 있는가? " - 제약 조건을 검사하는 단계 2) 가지치기 (Pruning) :유망하지 않으면 그 가지 전체를 건너뜀 - 아래로 더 내려가지 않는다. = 백트래킹 이란 가능성, 유망성을 보고 안되면 그 가지를 잘라내는 것 이다. 부분합 문제 - 같은 문제, 더 똑똑하게. 문제: 배열 {3,7,1,8,4} 에서 합이 11 인 부분집합 을 찾아라. 완전 탐색 방법: 부분집합 2^5 = 32개 를 모두 만든 뒤 각각의 합을 확인 → 11인 것 찾기 백트래킹: 부분집합을 만드는 도중 에 "이미 합이 11 초과" 라면 → 가지치기 ※ 합은 원소(양수)를 추가할 수록 커지기만 하므로 합이 목표를 넘으면 더 깊이 들어갈 필요가 없음 부분합 추적 회색: 탐색한 루트 / 녹색: 정답 루트 / 주황색: 오답 루트 / 희미한 색: 탐색하지 않은 루트 배열 {3,7,1,8,4}의 부분집합 은 사진의 모든 구슬의 개수와 같다. ( 완전탐색 시 탐색횟수 2^5 = 32회 ) 백트래킹 을 통해 부분합 11을 만족하는 부분집합을 구하기 위해 위에서부터 가지 아래로 내려가면서 만나는 숫자를 모두 합 해서 11을 만족하면 결과에 포함 하고, 11을 초과하면 그 아래의 탐색은 중단 한다. ( 위 사진에서 백트래킹 으로 탐색한 횟수 14 + 8 + 3 = 25회 ) 정렬이 가지치기를 효율적으로 만든다 배열을 ...
