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

개인 공부 후 자료를 남겨놓기 위한 목적이므로,
생략되거나 오류가 있을 수 있음을 알립니다.

 

 

---

목차

0. 백트래킹의 목적

1. 백트래킹의 특징

2. 기본 구조

3. 1번 템플릿

4. 2번 템플릿

5. 3번 템플릿

6. 가지치기

 

 

 

0. 백트래킹의 목적

코드를 짜다보면 n중 반복문을 짤 경우가 생기게 된다.

이를 하드코딩으로는 거의 해결할 수 없게되므로 재귀함수를 이용하여 짜게 되는데

재귀함수를 이용한 완전 탐색 알고리즘을 백트래킹이라고 한다.

 

간단히 말해서는 정해지지 않은 n중 for문을 짜기 위한 목적의 알고리즘이라고 생각해도 된다.

 

 

---

 

1. 백트래킹의 특징

백트래킹의 특징은 다음과 같다.

1. 진입장벽이 높다. (재귀함수 사용)
2. (후술할) 기본 템플릿에서 내용을 수정하려면 재귀에 대한 높은 이해도를 요구한다.
3. 한번 익히면, 매우 쉽다. (+ DP를 덤으로 배울 수 있다.)
4. 완전탐색의 일종이다.

백트래킹의 시간 복잡도는 O(2^n), O(nPm), O(nCm) 등으로 표현된다.

 

 

기존 완전탐색 vs 백트래킹

000

001

002

003

004

010

011

...

444

 

위와 같은 3자리 5진수를 for문을 이용해 출력해보자.

다음과 같이 작성할 수 있을 것이다.

 

 

 

여기서 3자리를 n자리로 바꿔서 생각해보면 n의 입력값에 따라 for문의 중첩수가 달라져야 한다.

 

n의 조건이 어느정도까지 나올 줄 모르므로 하드코딩은 실질적으로 작성하기 어렵고,

 

이를 해결하기 위해 우리는 재귀함수를 사용하게 된다.

 

이에 관련된 내용은 작성해둔 게시글이 있으니 다음의 링크를 참고하면 된다.

[알고리즘] 재귀함수(recursion function)

 

 

---

 

2. 기본 구조

 

백트래킹의 기본 구조는 다음과 같고 우리는 이 코드를 3가지로 변형시켜 사용한다.

 

 

3. 1번 템플릿 (중복 순열)

가장 기본적인 백트래킹 (크기가 m인 수열에서 중복을 허용해 n개를 뽑는 경우를 모두 출력)

 

백트래킹을 사용하면서 나오는 변수는 어디에 저장해야 할까?

 

recur 함수 내부에서 변수를 저장하게 되면 변수의 유효 범위 때문에 { } 안은 지역변수로서 함수가 끝나면 사라지게 되므로

 

우리는 정답으로 내보낼 값들을 전역 변수에 저장해야 한다.

 

이를 코드로 표현하면 우리가 배우게 될 1번 템플릿이 완성된다.

 

1번 템플릿

 

 

 

 

4. 2번 템플릿 (순열)

1번 템플릿을 발전시켜 중복을 허용하지 않는다면 어떻게 짜야할까?

 

이를 해결하기 위해서 사용 유무를 관리하는 배열을 하나 만들어준다. (방문처리)

 

`vector<bool> visited(n, false)`와 같은 배열을 만들어준 뒤

사용중이라면 continue, 사용 전이라면 사용하고 visited[i] = true 이후 다음 재귀로 넘어가는 식으로 코드를 짠다.

여기서 주의해야 할 점은 다음 for문에서 i를 다시 사용해야하기 때문에 visited[i]를 사용 후에 반납을 해주어야 한다.

 

코드로 확인해보자.

 

 

 

5. 3번 템플릿 (조합)

다음의 문제가 있다고 하자.

"3개를 뽑아 더해서 나오는 값들 중 합이 8인 것의 개수를 구해라"

 

0 1 2 3 4

1 3 2 4 10

 

이를 for문을 이용해서 풀면 아마 다음과 같이 풀 것이다.

 

위 for문이 도는 인덱스를 생각해보면 

 

0 1 2

0 1 3

0 1 4

1 2 3

1 2 4

2 3 4

...

...

 

와 같이 나오게 되는데, 이를 보면 인덱스가 오름차순인 것을 확인할 수 있다.

(중복을 제거하기 위해)

 

이를 백트래킹에 적용해보자.

 

start가 적용됨

 

이전 값을 인자로 넘겨주어 오름차순으로 만들어질 수 있도록 유도하였다.

 

 

 

6. 가지치기 (프루닝)

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

백트래킹을 이용해 모든 값을 넣어 위의 문제를 풀어보자.

 

가지치기를 하기 전의 풀이

 

위 방식의 경우에는 모든 수의 조합을 만들어보고 이후에 부등호가 맞는지 확인하게 된다.

 

이는 쓸대없는 연산이 무척 많이 들어가므로, 매 재귀마다 부등호가 맞는지 확인을 미리해준다면 

 

쓸모없는 연산들을 조기에 차단할 수 있다. 이를 가지치기라고 한다.