백트래킹

모든 경우를 만들되, 가망 없는 가지는 미리 잘라내요.

개념

백트래킹은 미로에서 갈림길을 하나씩 시도해 보는 사람과 같아요. 갈림길에 서면 일단 한 길을 골라 들어가 보고, 막다른 곳이 나오면 마지막 갈림길로 되돌아와(백트랙) 방금 고른 길을 지우고 다음 길을 시도해요. 이렇게 하면 모든 길을 빠짐없이 훑을 수 있어요. 여기에 하나만 더 얹으면 백트래킹이에요 — 들어가기도 전에 '이 길은 어차피 막혔다'가 보이면 아예 안 들어가요. 이 '미리 안 들어가기'가 가지치기(pruning)예요.완전 탐색은 가능한 모든 경우를 만들어 보는 방식이에요. 백트래킹은 그것을 재귀로 구현하되, 도중에 답이 될 수 없다고 판단되면 그 아래를 통째로 건너뛰는 기법이에요. 이 '건너뛰기'가 가지치기(pruning)이고, 백트래킹의 전부라고 해도 돼요.구조는 단순해요. 선택하고, 더 깊이 들어가고, 돌아와서 선택을 되돌려요. 이 세 줄이 반복될 뿐이에요.

선택 — 현재 후보를 결과에 넣어요
진행 — 다음 단계로 재귀해요
취소 — 넣었던 것을 빼서 원래 상태로 되돌려요

세 가지 기본 형태

만들 것	개수	다음 후보의 시작	중복 사용
부분집합	2ⁿ	`i + 1`	안 함
조합 (nCk)	nCk	`i + 1`	안 함
순열 (nPn)	n!	처음부터	`used` 배열로 막음

차이는 '다음 재귀에 무엇을 넘기는가' 한 줄이에요. 조합은 자기 다음 인덱스부터 보게 해서 순서가 다른 같은 조합을 만들지 않고, 순열은 전부 다시 보되 이미 쓴 것만 막아요.

직접 따라가 보기: [1,2,3]의 순열

[1,2,3]으로 순열 6개를 만드는 과정을 결정 트리로 따라가 볼게요. 각 단계에서 아직 안 쓴 수 중 작은 것부터 골라요. 끝까지 3개를 다 고르면 순열 하나가 완성돼요(체크). 그러고 나서 한 칸 되돌아와(백트랙) 방금 넣은 걸 빼고 다음 수를 시도해요. 세로줄을 따라 내려가면 선택이고, ← 백트랙이 붙은 줄이 되돌아오는 순간이에요.

[1,2,3] 순열 — 고르고, 완성되면 되돌아와 다음을 시도
고른다 1
  고른다 2
    고른다 3  ->  [1,2,3]  완성
  ← 백트랙: 3 빼고 2 빼기
  고른다 3
    고른다 2  ->  [1,3,2]  완성
← 백트랙: 다 빼고 처음으로
고른다 2
  고른다 1
    고른다 3  ->  [2,1,3]  완성
  고른다 3
    고른다 1  ->  [2,3,1]  완성
← 백트랙: 다 빼고 처음으로
고른다 3
  고른다 1 -> 2  ->  [3,1,2]  완성
  고른다 2 -> 1  ->  [3,2,1]  완성

순열 하나가 완성될 때마다 되돌아와 방금 선택을 지우는 게 보이죠? 이 '지우기'가 코드의 path.pop()이고, used[i] = false로 그 수를 다시 쓸 수 있게 풀어주는 부분이에요. 되돌리기를 빠뜨리면 다음 가지가 이전 가지의 흔적을 그대로 물려받아 엉뚱한 답이 나와요.

가지치기가 실력이에요

N-Queen에서 가지치기 없이 모든 배치를 만들면 8×8에서 약 40억 가지예요. 열과 대각선 충돌을 놓는 즉시 확인하면 2천 가지 정도만 탐색해요. 같은 알고리즘인데 결과가 완전히 달라요.

지금까지의 부분 답이 이미 조건을 어겼다면 즉시 되돌아가요
남은 것을 다 더해도 목표에 못 미친다면 더 볼 필요가 없어요
정렬해두면 '이 후보가 안 되면 뒤도 안 된다'는 판단이 가능해져요

패턴 코드

부분집합

javascript
Copy code
const out = [];
const path = [];
function backtrack(start) {
  out.push([...path]);          // 복사본을 담아요
  for (let i = start; i < nums.length; i++) {
    path.push(nums[i]);         // 선택
    backtrack(i + 1);           // 진행
    path.pop();                 // 취소
  }
}
backtrack(0);

순열조합과 달리 매번 처음부터 보되, used로 이미 쓴 원소를 막아요.

javascript
Copy code
const used = new Array(nums.length).fill(false);
function backtrack() {
  if (path.length === nums.length) {
    out.push([...path]);
    return;
  }
  for (let i = 0; i < nums.length; i++) {
    if (used[i]) continue;
    used[i] = true;
    path.push(nums[i]);
    backtrack();
    path.pop();
    used[i] = false;
  }
}

가지치기를 넣은 조합의 합정렬해두면 후보가 남은 목표보다 클 때 뒤를 전부 버릴 수 있어요.

javascript
Copy code
candidates.sort((a, b) => a - b);
function backtrack(start, remain) {
  if (remain === 0) {
    out.push([...path]);
    return;
  }
  for (let i = start; i < candidates.length; i++) {
    if (candidates[i] > remain) break;   // 가지치기
    path.push(candidates[i]);
    backtrack(i + 1, remain - candidates[i]);
    path.pop();
  }
}

이번 주 문제

이번 주 진행0 / 4

주차 진행률

이번 주 주제로 골라둔 문제예요. 채점은 프로그래머스에서 하고, 풀고 나면 여기에 체크해 두세요. 난이도 순으로 보여줘요.

프로그래머스 진행률

모음사전 푼 문제로 표시
모음사전
Lv. 2풀기

셀프 체크

다음 주로 넘어가기 전에 소리 내어 답해 보세요. 막히면 그 부분이 아직 덜 익은 개념이에요.

결과 목록에 복사본이 아니라 원본을 담으면 무슨 일이 일어나나요?
조합과 순열의 코드에서 실제로 다른 부분은 어디인가요?
'n ≤ 20'이라는 제한이 백트래킹을 시사하는 이유는 무엇인가요? (1주차 표)

← 16주차 · BFS 최단 거리와 격자 탐색 18주차 · 힙과 우선순위 큐 →