백트래킹의 개념을 이해하고, 전체 탐색(brute force, 브루트 포스)과 차이점을 설명할 수 있습니다. 유망 함수를 활용해서 더 효율적인 트리 탐색 알고리즘을 구현할 수 있습니다.
총 3편으로 준비했습니다. 2편은 백트래킹 알고리즘 문제에 적용해보기입니다.
1. 백트래킹과 백트래킹 알고리즘 개념
2. 백트래킹 알고리즘 문제에 적용해보기
3. 백트래킹 몸풀기 문제
백트래킹 알고리즘은 아주 간단해서 더 설명할 내용은 없습니다. 이제 백트래킹 알고리즘으로 해결할 수 있는 대표적인 문제인 부분 집합 합 문제와 N-여왕 문제를 살펴보겠습니다. 아참, 많은 사람은 백트래킹 알고리즘을 그냥 ‘백트래킹으로 문제를 푼다’라고 말하기도 합니다. 이 책에서도 ‘백트래킹으로 문제를 푼다’라고 하고 엄밀하게 두 용어를 구분하여 말하지 않겠습니다.
부분 집합 합
부분 집합 합(sum of subset)은 1부터 N까지 숫자를 조합했을 때 합이 K가 되는 조합을 찾는 문제입니다. 이 문제를 전체 탐색과 백트래킹으로 각각 한 번씩 풀면서 두 알고리즘의 차이와 백트래킹의 장점을 알아보겠습니다.
완전 탐색으로 풀기
각 숫자는 뽑는 상태와 뽑지 않는 상태가 있으며, 각 숫자를 선택하는 과정은 다른 숫자에 대한 선택에 영향을 미치지 않습니다. 이 규칙을 적용하면 N개의 숫자를 뽑는 조합은 2N개가 있으므로, 시간 복잡도는 O(2N)이라고 할 수 있습니다. 실제로 어떻게 완전 탐색을 할지도 살펴봅시다. N = 4이고 K = 5일 때 완전 탐색을 한다면 이렇게 할 겁니다.
원 안의 숫자는 현재까지 뽑은 숫자들의 합을 의미합니다. 동그라미(○)는 ‘그 수를 뽑는다’, 엑스(×)는 ‘그 수를 뽑지 않는다’입니다. 말 그대로 완전히 모든 경우의 수를 탐색하여 총 16번의 탐색을 진행합니다.
백트래킹으로 풀기
완전 탐색을 보면 알겠지만 답이 될 가능성이 없는 조합에 대해서도 탐색을 진행합니다. 유망 함수를 활용해서 답이 될 가능성이 없는 경우 최대한 탐색이 되지 않도록 해봅시다. 이 문제에서 유망 함수는 다음과 같이 설계하면 됩니다.
- 조건 1 : 현재 조합으로 합이 K가 되면 더 탐색하지 않기
- 조건 2 : 해당 숫자를 조합하여 합이 K 이상이 되면 더 탐색하지 않기
01단계 본격적으로 문제를 풀기 전에 실제로 어떤 상황에서 유망 함수가 백트래킹시키는지도 생각해봅시다. ➊ 우선은 2, 3을 뽑으면 이미 합이 5이므로 수를 더 뽑거나 하지 않아도 됩니다. 조건 1에 맞으니 백트래킹합니다. ➋ 다른 경우도 생각해봅시다. 1, 2를 뽑은 상태에서 3을 뽑는다면 6이므로 5보다 크니 3 이후는 뽑지 않아도 되므로 백트래킹합니다.
02단계 결국 백트래킹을 통해 탐색을 배제한 노드들이 많아졌습니다. 완전 탐색을 했다면 배제한 노드도 탐색해야 했을 겁니다. 이런 식으로 백트래킹은 탐색의 효율을 크게 높여줍니다.
합격 조언 – 유망 함수는 같은 문제에서도 다양하게 정의할 수 있어요
앞의 설명에서는 설명의 편의를 위해 유망 함수를 단순하게 정의하였습니다. 사실 앞의 설명에서 예로 든 유망 함수는 그렇게 효율적이지 않았습니다. 유망 함수는 문제를 푸는 사람에 따라 다르게 만들 수 있고, 실제로 이 문제도 다른 유망 함수를 사용하면 더 개선할 수 있습니다. 이 문제는 숫자를 1부터 체크하고 있으며 마지막 숫자를 알고 있습니다. 예를 들어 3을 탐색한 이후에는 나머지 숫자가 4라는 것을 알고 있죠. 이를 활용하면 마지막 4를 선택할지 판단하는 시점에 현재까지 뽑은 숫자의 합이 1 이상이어야 5가 될 가능성이 있다는 것을 알 수 있습니다. 숫자 1에서 3까지 조합에서 합이 0이었다면 4를 볼 필요도 없다는 것을 추가로 알게 되는 것이지요. 이 사실을 유망 함수에 적용하면 훨씬 효율적으로 백트래킹을 할 수 있을 겁니다.
N-퀸 문제
N-퀸 문제는 체스의 퀸을 N × N 체스판에 N개 배치했을 때 서로를 공격할 수 없는 위치에 놓을 수 있는 방법이 있는지 찾는 문제입니다. 체스를 모르는 독자를 위해 퀸을 설명하자면 퀸은 다음과 같이 이동할 수 있는 말입니다.
퀸의 이동 경로에 다른 퀸이 있다면 공격하여 제거할 수 있겠죠. 그렇게 되지 않도록 퀸을 배치할 수 있는지를 알아보는 문제입니다. 다음과 같은 경우 퀸은 서로를 공격할 수 없습니다.
문제를 파악했으니 이제 본격적으로 문제를 풀어봅시다. 여기서도 완전 탐색, 백트래킹 방식으로 모두 풀어보겠습니다.
완전 탐색으로 풀기
완전 탐색 방식은 퀸을 놓을 수 있는 경우의 수를 모두 탐색해보는 방식입니다. 각 줄에 여왕을 놓는 방법은 총 N개이므로 시간 복잡도는 O(NN)이 되겠네요. 예를 들어 체스판의 크기가 4 × 4라면 다음 그림을 생각해볼 수 있습니다. 지면상 한계로 일부 그래프를 생략했습니다.
그림은 퀸을 (1, 1), (2, 3), (3, 2), (4, 1)에 놓은 것과 대응하는 그래프의 탐색 경로를 표시한 것입니다. 완전 탐색은 그래프상의 모든 경우의 수를 다 탐색하며 조건에 맞는지 검사합니다. 이렇게 하면 답을 찾을 수는 있지만 매우 비효율적인 방법이라는 건 이제는 금방 알 수 있을 겁니다. 이를 테면 (3, 2)에 놓은 퀸은 (2, 3)과 대각선 상에 놓이므로 애초에 그 이후는 탐색할 필요도 없습니다. 아하, 유망 함수가 등장할 차례네요. 백트래킹 방식으로 풀어볼 시간입니다.
백트래킹으로 풀기
유망 함수를 추가해서 탐색 대상을 줄이고 시간 복잡도를 감소시켜봅시다. 여기서 정의할 유망 함수는 다음과 같습니다.
- 여왕이 추가될 때마다 행이나, 대각선 방향에 겹치는 여왕이 있으면 더 탐색하지 않기
유망 함수를 정의하면 이런 식으로 백트래킹을 합니다. (1, 1), (2, 3) 이후 (3, 2)를 만나면 대각선상의 (2, 3)와 겹치므로 유망 함수에서 걸러집니다. 즉, 그 이후는 더 탐색하지 않고 백트래킹합니다.
구체적으로 백트래킹을 통해 문제를 푸는 과정은 다음과 같습니다.
01단계 유효한 해의 집합을 정의합니다. 4행 4열의 칸이 있고 여기에 퀸을 놓을 수 있으므로 해의 집합은 다음과 같이 표시할 수 있습니다.
표시 방법이 헷갈릴 수 있으므로 그림으로도 확인합니다. 예를 들어 2, 1, 1, 3은 다음과 같은 말의 상태를 의미합니다.
02단계 앞서 본 것처럼 해의 집합을 그래프로 표현합니다.
03단계 백트래킹은 방금 본 것과 같습니다. 다른 예로도 설명해보겠습니다. 1 → 1로 이동하면 유망 함수에 의해 백트래킹합니다.
04단계 유망 함수를 통과하여 탐색하는 경우는 다음과 같습니다. 2, 4, 1, 3의 경우 유망 함수를 통과하는 조건입니다. X로 표시한 것들은 2, 4, 1, 3이 N퀸 조건에 맞는지 확인하는 과정에서 유망 함수에 의해 백트래킹된 것입니다.
완전한 풀이는 이쯤에서 생략하고 여기서는 백트래킹 방식으로 푼다는 의미와 유망 함수의 역할이 무엇인지에 대한 감만 잡고 넘어가겠습니다. 본격적인 코드를 통한 풀이는 이후 문제를 통해 더 단단하게 만들어봅시다.
3편은 백트래킹 몸풀기 문제입니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
