알고리즘 - 백트래킹(Backtracking)

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

1. 백트래킹(Backtracking)이란?

 

완전 탐색 알고리즘에 조건을 추가하여 가능성이 없는 부분을 탐색하지 않도록 하는 알고리즘이다. 

즉, 완전탐색 알고리즘은 "모든 부분을 전부 탐색한다"이고 백트래킹을 적용시키게 되면 "가능한 모든 부분을 전부 탐색한다"가 된다.

 

모든 경우의 수를 탐색하는 것이 아니라 가능한 부분만 탐색을 하도록 하여 반복 횟수를 줄임으로써 속도를 향상시키는 알고리즘이다.

 

핵심 키워드는 "배제"와 "풀이시간 단축"이다. 

이렇게 배제시키는 것을 가지치기 라고 부른다. 해당 방향으로 진행했을 경우 답이 나올 수 있는지 확인하고 나올수 없다면 진행하지 않도록 가지치기를 진행한다.

 

예를 들어

1~5까지의 숫자가 있다. 이것을 중복을 포함하지 않고 전부 하나씩 써서 5자리 숫자를 만들어야 한다.

그렇다면 내가 이미 사용한 숫자를 기록하고 기록된숫자 즉, 중복되는 숫자를 배제하여 숫자를 나열하는 것이 백트래킹 알고리즘이다.

1~5까지의 숫자로 만들 수 있는 모든 경우중

1 1 ~

2 2~

3 3~

...

등등 많은 중복되는 요소를 만들어내는 반복을 진행하지 않고 필요없는 부분을 배제하여 정답을 구할 수 있다.

 

2. 백트래킹 알고리즘의 장단점?

장점

1. 속도가 빠르다.

: 모든 경우의 수를 탐색하는 것이 아니라 불가능한 부분을 배제하여 문제를 풀기때문에 필요없는 부분에 대한 탐색을 진행하지 않아도 된다.

 

단점

1. 속도가 느리다

: 이게 뭔소린가 싶을거다. 방금 장점으로 빠르다고 해놓고 느리다고? 다른 알고리즘 대비 느리다. DP, 그리디 등이 일반적인 상황에서는 백트래킹을 하는것보다 빠르다. 하지만 백트래킹으로만 풀 수 있는 부분들이 있기 때문에 백트래킹에 대하여 공부해야 한다. 

 

3. 어떻게 사용하나?

백트래킹은 대부분 DFS를 활용한다.

 

DFS와 BFS는 이전에 내가 적어둔 알고리즘이 있다. 한번 읽어보는걸 추천한다. 

https://naemamdaelo.tistory.com/37

알고리즘 - 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

4. Example

https://naemamdaelo.tistory.com/45

[Java] 백준 9663번 : N-Queen

 

 

-꿑-