[알고리즘] 백트래킹(Backtracking)

백트래킹(Backtracking)은 문제를 해결하기 위해 가능한 모든 경우의 수를 탐색하는 알고리즘 기법이다.

 

하지만 단순히 모든 경우를 다 시도하는 '완전탐색'과는 다르다.

백트래킹은 불필요한 탐색을 줄이는 데 초점을 맞추고 있다.

---

백트래킹의 과정

1. 결정: 문제를 해결하기 위해 한 단계씩 선택(결정)을 진행한다.
2. 유효성 검사: 현재 선택이 문제의 조건을 만족하는지 확인한다.
   • 만족하지 않으면 "가지치기(Pruning)"를 하고 탐색을 종료한다.
3. 되돌아가기: 만족하지 않거나 이미 해결된 경우, 이전 단계로 돌아가 다른 선택을 시도한다.

이 '되돌아가는 과정'이 백트래킹이라는 이름의 유래이다.

---

백트래킹의 기본 틀

백트래킹은 두 부분으로 구분한다.

void backtracking(int depth, int m) {
	if (depth == m) {
		// 2. 선택한 원소를 기반으로 결과를 계산하는 부분
	}
	else {
		// 1. 원소를 선택하는 부분
	}
}

 

보통 원소를 선택하는 부분에서 재귀 함수를 이용하게 된다.

 

이후의 원소 선택을 어떻게 할 것이냐에 따라 함수의 파라미터(매개변수)가 달라질 것이다.

---

원소 선택

원소를 선택하는 것은 두 가지 유형으로 구분된다.

1. 단계가 기준이 되는 유형
2. 원소가 기준이 되는 유형

 

1. 과 같은 경우는 현재 단계에서 원소를 선택하고, 다음 단계에게 나머지 역할을 넘기는 식으로 진행된다.

• "순열, 중복 순열, 조합" 유형이 해당된다.

순열

순열은 순서에 따라 결과가 달라질 수 있는 경우.

중복 순열

중복 순열은 순열과 같지만, 같은 원소를 중복 선택 가능한 경우.

조합

순서는 결과에 영향을 주지 않고, 어떤 원소를 선택했냐가 중요한 경우.

---

 

2. 와 같은 경우는 현재 원소를 몇 개 선택할 것이냐 이다.

• "부분 집합, 중복 조합" 유형이 해당된다.

---

백트래킹의 장점과 단점

장점:

• 불필요한 경우를 배제해 탐색 효율이 높아진다.
• 문제의 조건만 명확히 정의하면 적용 가능하다.

단점:

• 최악의 경우 여전히 모든 경우를 탐색해야 하므로, 시간 복잡도가 높을 수 있다.
• 가지치기 조건이 약하거나 잘못 설정되면 성능이 저하된다.