13.5 요약¶
1. 핵심 정리¶
- 백트래킹은 본질적으로 모든 경우를 열거하는 방법이다. 해 공간을 깊이 우선으로 순회하여 조건에 맞는 해를 찾고 기록하며, 모든 해를 찾거나 순회가 끝나면 종료한다.
- 백트래킹의 탐색 과정은 시도와 되돌리기로 이루어진다. 깊이 우선 탐색으로 여러 선택을 시도하고, 제약 조건을 만족하지 않으면 직전 선택을 취소하여 이전 상태로 돌아간 뒤 다른 선택을 계속 시도한다. 시도와 되돌리기는 서로 반대 방향의 연산이다.
- 백트래킹 문제에는 보통 여러 제약 조건이 있고, 이를 가지치기에 사용할 수 있다. 가지치기는 불필요한 탐색 가지를 일찍 종료하여 효율을 크게 높인다.
- 백트래킹은 주로 탐색 문제와 제약 만족 문제에 사용한다. 조합 최적화 문제도 해결할 수 있지만, 더 효율적이거나 더 좋은 결과를 내는 풀이가 있는 경우가 많다.
- 모든 순열 문제는 주어진 집합 원소들의 가능한 모든 순열을 찾는 것이 목표다. 배열로 각 원소의 선택 여부를 기록하고 동일 원소를 중복 선택하는 가지를 잘라 내어 각 원소를 한 번만 선택하도록 한다.
- 모든 순열 문제에서 집합에 중복 원소가 있으면 결과에 중복된 순열이 생긴다. 각 차례에서 같은 값의 원소를 한 번만 선택하도록 제한해야 하며, 보통 해시 집합으로 구현한다.
- 부분 집합 합 문제는 주어진 집합에서 합이 목표 값인 모든 부분 집합을 찾는다. 집합은 원소 순서를 구분하지 않지만 탐색은 모든 순서의 결과를 출력하므로 중복이 생긴다. 백트래킹 전에 데이터를 정렬하고 각 차례의 순회 시작점을 변수로 지정하여 중복 부분 집합을 만드는 가지를 잘라 낸다.
- 부분 집합 합 문제에서는 배열의 같은 값 원소가 중복 집합을 만들 수 있다. 배열이 정렬되어 있다는 전제를 이용해 인접 원소의 값이 같은지 확인하여 가지치기하고, 같은 값을 매 차례 한 번만 선택하도록 한다.
- \(n\)-퀸 문제는 \(n \times n\) 체스판에 퀸 \(n\) 개를 서로 공격하지 않게 배치하는 문제다. 행, 열, 주대각선 방향, 부대각선 방향의 제약이 있다. 행 제약을 만족하려고 행별 배치 전략을 사용하여 각 행에 퀸 하나를 놓는다.
- 열 제약과 대각선 제약은 비슷하게 처리한다. 열 제약은 배열에 각 열의 퀸 존재 여부를 기록하여 선택한 칸이 유효한지 판단한다. 대각선 제약은 두 배열로 각 방향 대각선의 퀸 존재 여부를 기록한다. 핵심은 같은 주대각선(부대각선) 방향 대각선의 칸들이 만족하는 행과 열 인덱스의 규칙을 찾는 것이다.
2. Q & A¶
Q: 백트래킹과 재귀의 관계는 어떻게 이해하면 되는가?
백트래킹은 '알고리즘 전략'이고, 재귀는 '도구'에 더 가깝다.
- 백트래킹은 보통 재귀로 구현한다. 백트래킹은 재귀의 활용 사례 중 하나이며, 탐색 문제에 재귀를 적용한 것이다.
- 재귀의 구조는 '부분 문제로 분해'하는 풀이 패턴을 보여 주며, 분할 정복, 백트래킹, 동적 계획법(메모이제이션을 이용한 재귀) 등의 문제에 자주 사용한다.