백트래킹의 개념을 이해하고, 전체 탐색(brute force, 브루트 포스)과 차이점을 설명할 수 있습니다. 유망 함수를 활용해서 더 효율적인 트리 탐색 알고리즘을 구현할 수 있습니다.
총 3편으로 준비했습니다. 1편은 백트래킹과 백트래킹 알고리즘 개념입니다.
1. 백트래킹과 백트래킹 알고리즘 개념
2. 백트래킹 알고리즘 문제에 적용해보기
3. 백트래킹 몸풀기 문제
깊이 우선 탐색, 너비 우선 탐색 방법은 데이터를 전부 확인하는 방법이었습니다. 이를 완전 탐색이라고 하는데요, 완전 탐색은 모든 경우의 수를 탐색하는 방법이므로 대부분의 경우 비효율적입니다.
백트래킹이란?
예를 들어 출근하기 위해 아파트를 나섰는데 지하철 개찰구에 도착해서야 지갑을 두고 나온 사실을 알았다고 해봅시다. 그러면 우선은 아파트로 돌아갈 것입니다. 집으로 돌아가서 방을 하나씩 보면서 물건을 찾기 시작할 겁니다. 혹시라도 옆 집의 문 앞에 선 경우라도 금방 ‘아 옆 집이구나’하는 생각에 뒤로 돌아 우리 집으로 향할 겁니다. 이렇게 어떤 가능성이 없는 곳을 알아보고 되돌아가는 것을 백트래킹(Backtracking)이라 합니다.
백트래킹 알고리즘이란?
이렇게 가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘을 백트래킹 알고리즘이라고 합니다. 그림을 봅시다.
그림을 보면 답을 찾는 과정에서 가능성이 없는 곳에서는 백트래킹합니다. 백트래킹 알고리즘은 문제마다 효율이 달라지므로 시간 복잡도를 특정하여 정의하기 어렵습니다. 하지만 확실한 것은 백트래킹을 통해 해가 될 가능성이 없는 탐색 대상을 배제할 수 있으므로 탐색 효율이 단순히 완전 탐색하는 방법보다 백트래킹이 효율적입니다. 그럼 구체적인 예와 함께 백트래킹 알고리즘을 알아봅시다.
유망 함수란?
백트래킹 알고리즘의 핵심은 ‘해가 될 가능성을 판단하는 것’입니다. 그리고 그 가능성은 유망 함수라는 것을 정의하여 판단하죠. 실제로 백트래킹 알고리즘은 다음과 같은 과정으로 진행합니다.
- 유효한 해의 집합을 정의합니다.
- 위 단계에서 정의한 집합을 그래프로 표현합니다.
- 유망 함수를 정의합니다.
- 백트래킹 알고리즘을 활용해서 해를 찾습니다.
그렇다면 유망 함수가 백트래킹 알고리즘에서 어떻게 동작하는지 아주 간단한 문제를 풀어보며 알아봅시다.
합이 6을 넘는 경우 알아보기
{1, 2, 3, 4} 중 2개의 숫자를 뽑아서 합이 6을 초과하는 경우를 알아내는 백트래킹 알고리즘을 알아봅시다. 뽑는 순서가 다르면 다른 경우의 수로 간주합니다. 예를 들어 {1, 3}과 {3, 1}의 합은 각각 4로 같지만 서로 다른 경우의 수입니다.
01단계 유효한 해의 집합을 정의합니다. 서로 다른 두 수를 뽑는 경우의 수는 다음과 같습니다.
02단계 정의한 해의 집합을 그래프로 표현합니다.
03단계 그래프에서 백트래킹을 수행합니다. 여기서는 ‘처음에 뽑은 숫자가 3 미만이면 백트래킹한다’라는 전략을 사용합니다. 다시 말해 1과 2를 처음에 뽑으면 이후에 어떤 경로로 가도 원하는 답이 나올 수 없으므로 1, 2는 아예 탐색을 시도하지도 않습니다. 이렇게 특정 조건을 정의하는 것을 유망 함수(Promising Function)를 정의한다고 합니다. 예를 들어 위 그림에서 1과 2는 유망 함수를 통과하지 못하여 백트래킹합니다.
04단계 3은 유망 함수를 통과합니다. 참고로 1, 2는 유망 함수와는 상관없이 깊이 우선 탐색 알고리즘에 의해 방문하지만 답이 아니므로 백트래킹하는 것입니다. 그 이후 3 → 4로 가서야 답을 찾습니다.
05단계 이와 같은 방식으로 나머지도 탐색을 진행하면 됩니다.
2편은 백트래킹 알고리즘 문제에 적용해보기입니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
