[실전 알고리즘] 0x07강 - 백트래킹, 시뮬레이션_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x0C강 - 백트래킹, [실전 알고리즘] 0x0D강 - 시뮬레이션에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

이번 시간에는 백트래킹, 시뮬레이션을 다룹니다. 삼성 역량테스트 A형에 늘 나오는 알고리즘이죠.

 

 

백트래킹을 무엇으로 예시를 들어야하나 고민하다가 ㄹㅇ루다가 적절한 비유를 찾았습니다. 혹시 미연시를 해본 적 있나요? 아니면 검은방/역전재판과 같은 추리게임에서의 언쟁을 생각하셔도 좋습니다. 게임을 클리어하는 최적의 경로를 알고 있으면 그 경로대로 진행을 하면 되지만, 그렇지 않다면 모든 경우의 수를 전부 다 해봐야합니다. 아마 다음 장과 같은 방식으로 플레이하겠죠.

 

게임의 구조가 대충 이렇다고 생각해봅시다. 맨 처음에 범인이 누구인지 묻고, 근거를 묻고, 마지막으로 살인 트릭을 묻는데 대답을 잘못하면 베드엔딩으로 진입합니다.

 

맨 처음 선택지 3개 중에서 하무열을 먼저 골라볼 것입니다. 그런데 베드엔딩이 뜨는걸 확인하면 바로 끄고 다시 도전하겠죠.

 

이번엔 서현진을 골라봅니다. 그러자 베드엔딩이 뜨지 않고 다음 질문을 하는 것을 볼 수 있습니다. 여기에 세이브 포인트를 만들어두고 다음 질문의 대답을 고민합니다.

 

첫 번째 선택지를 고르니 베드엔딩이 뜨네요. 세이브 포인트로 돌아가서 두 번째 선택지를 고릅시다.

 

마찬가지로 베드엔딩이네요. 처음으로 돌아갑니다.

 

하무열과 서현진은 이미 다 해봤으니 이번에는 안승범을 골라봅니다.

 

근거로 넘어왔습니다. 근거가 하나밖에 없으니 '백선교와 관계된 그의 과거'를 선택합니다.

 

살인 트릭에서 첫 번째 선택지를 고르니 트루엔딩이 뜨네요. 다행입니다.

 

호기심이 많다면 다시 불러와 두 번째 선택지도 선택해보겠죠.

 

혹시 지금까지 살아오면서 이런 류의 게임을 단 한번도 해보지 않아 잘 이해가 가지 않는다면, 오목이나 바둑에서 다음 수를 어디 둘지 고민하는 과정도 생각해보면 비슷한 절차를 따릅니다. 이와 같이 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘을 백트래킹이라고 합니다.

 

상당한 구현력을 필요로 하고, 실수하기도 쉬운데다가 재귀의 특성상 틀리더라도 실수한 부분을 찾기도 힘들어서 굉장히 많은 시간을 할애해 연습하지 않으면 풀이는 아는데 그 풀이를 코드로 옮겨내지 못해 문제를 풀지 못하는 경우가 생길 수 있습니다.

 

BOJ의 N과 M 시리즈가 백트래킹을 연습하기에 아주 적합합니다. 총 12문제가 있는데 그 중에서 몇 가지를 같이 풀어보겠습니다. 첫 번째는 BOJ 15649번 : N과 M (1) 입니다. 8중 for문을 돌려도 풀 수는 있겠지만 코드가 굉장히 난잡하겠죠. 대신 백트래킹을 이용해 비어있는 리스트에서 시작해 수를 하나씩 추가하면서 길이가 $M$인 수열을 만들면 해당 수열을 출력하면 됩니다.

 

현재의 상태에서 수를 추가하기 위해서는 어떤 수가 수열에 이미 쓰였고, 어떤 수가 아직 쓰이지 않았는지를 따로 저장하고 있어야 합니다. 우선 각 상태가 어떤 모양을 이루고 있는지 트리를 한 번 살펴봅시다.

 

이런 식으로 수열을 만들어가다가 $M$개의 항이 쌓이면 출력을 하면 됩니다.

 

이 문제에서는 isused와 arr와 k라는 변수가 쓰입니다. isused는 1부터 4까지의 각 수가 쓰였는지 확인하는 변수이고 k는 리스트에 들어있는 수의 갯수를 의미합니다. arr는 리스트에 들어있는 수를 의미하고 arr[1 to k]까지만 의미를 가집니다. arr[k+1], arr[k+2] 등은 참조되지도 않고 의미도 없는 값입니다.

 

이제 백트래킹을 시작해봅시다. 리스트는 비어있고 isused 또한 모두 False로 초기화되어 있습니다. k는 당연히 0입니다.

 

우선 리스트의 1번째 원소에 넣을 수를 정해야 합니다. 우선 1을 넣습니다.

 

2번째 원소로 넣을 수를 정합시다. 1은 사용중이므로 불가능하고 2를 넣읍시다.

 

3번째 원소로 넣을 수를 정합시다. 1, 2가 사용중이므로 불가능하고 3을 넣습니다. 리스트의 크기가 3이 되었으므로 (1, 2, 3)을 출력합니다.

 

길이 3짜리 리스트를 만들어 출력했으므로 이전 경우로 돌아옵니다. 이 때 3이 빠졌으므로 isused[3]을 False로 변경하고 k를 1 감소시켜야 합니다. 단 arr[3]은 어차피 의미가 없는 값으므로 굳이 변경하지 않아도 됩니다.

 

다시 3번째 원소에 넣을 수를 정합시다. 1, 2는 사용중이고 3은 이전에 넣어봤으므로 4를 넣습니다. 리스트의 크기가 3이 되었으므로 (1, 2, 4)를 출력합니다.

 

한 칸 뒤로 갑니다. 길이 3짜리 리스트를 만들어 출력했으므로 이전 경우로 돌아옵니다. 리스트의 3번째 원소에 넣을 수를 정하고 싶은데 1, 2는 사용중이고 3, 4는 이전에 넣어봤으므로 더 이상 넣을 수가 없습니다.

 

다시 한 칸 뒤로 갑니다.

 

리스트의 2번째 원소에 넣을 수를 정합시다. 1은 사용중이고 2는 이전에 넣어봤으므로 3을 넣습니다.

 

비슷한 논리로 계속 진행합니다.

 

 

(1, 3, 4) 이후는 후략하겠습니다. 마찬가지로 리스트의 길이가 3이 됐거나 넣을 수 있는 수를 모두 넣어본 경우에는 뒤로 돌아가서 다음 수를 넣는 식으로 계속 반복하면 됩니다.

 

아마 돌아가는 원리를 시각적으로는 이해했을 것입니다. 그러나 이를 실제로 구현하는건 굉장히 까다롭고, 예시 코드를 보더라도 이해하는게 굉장히 힘들 것입니다. 그러나 처음 봤을 때 낯설게 느껴지고 이해가 잘 안가는 것이 정상입니다. 앞의 내용들에 비해 갑자기 난이도가 확 올라가서요. 그러니 코드가 어렵더라도 너무 상심하지 말고 조급해하지도 말고 천천히 이해를 해보려고 시도해봅시다.(정답 코드)

 

arr와 isused를 vector로 두어도 상관없고, 또 함수 인자로 주고 받는 대신 전역변수로 선언해도 상관 없습니다.

 

그 다음으로는 BOJ 15652번 : N과 M (4)를 살펴보겠습니다. 이 문제에서는 수가 중복될 수 있고 고른 수열은 비내림차순이어야 한다는 조건이 추가되었습니다. 그렇기에 수의 중복을 막기 위해 사용하던 isused가 이젠 필요하지 않고, 비내림차순 성질을 만족하기 위해 재귀 함수 내의 for문이 0부터 시작하는 대신 arr[k-1]부터 시작하면 됩니다.(정답 코드)

 

N과 M 시리즈 12문제를 다 풀어보면 좋으나 9, 10, 11, 12는 좀 어려울 수도 있습니다. 기본기를 다진다고 생각하고 되는데까지 쭉 풀어보세요.

 

이제 본격적으로 백트래킹을 이용해서 해결해야하는 문제인 BOJ 9663번 : N-Queen 문제를 봅시다. N-Queen 문제는 $N \times N$ 체스판에 퀸 $N$개를 서로 공격하지 못하는 위치에 놓는 경우의 수를 구하는 문제입니다. 

 

각 행에 퀸이 정확히 1개씩 있음은 자명합니다. $N$이 최대 14로 그다지 크지 않기 때문에 각 행에 대해 퀸을 어느 열에 둘지를 가지고 백트래킹을 하면 됩니다.

 

 

 

 

단 백트래킹 과정 중에서 가지치기를 제대로 하지 않으면 $O(N^N)$이 되어 시간 초과가 발생합니다. 가지치기를 제대로 하지 않았다는 의미는, 예를 들어 $N = 10$일 때 1번째 행부터 차례로 퀸을 놓아가는데 5번째 행에서 이미 퀸을 더 이상 둘 수 없는 상황이 되었다고 생각해봅시다. 그러면 더 이상 함수를 따라 내려가면 안됩니다. 그런데 앞으로 더 진행해도 불가능함이 확실해졌는데도 계속 따라 내려가면 가지치기를 제대로 하지 않은 것입니다.

 

앞의 N과 M (1) 문제에서 isused가 각 수가 수열에 쓰였는지를 확인한 것 처럼 이번 문제에서는 두 방향의 대각선(왼쪽 위와 오른쪽 아래를 연결하는 대각선, 오른쪽 위와 왼쪽 아래를 연결하는 대각선)과 열에 대해 다른 퀸이 존재하는지 여부를 따로 저장하고 있어야 합니다.

 

isused1은 열에 대한 변수입니다. $(x, y)$에 퀸을 둘 때 isused[y]를 true로 만들면 됩니다.

 

isused2는 오른쪽 위와 왼쪽 아래를 연결하는 대각선에 대한 변수입니다. $(x, y)$에 퀸을 둘 때 isused[x+y]를 true로 만들면 됩니다.

 

isused3은 왼쪽 위와 오른쪽 아래를 연결하는 대각선에 대한 변수입니다. $(x, y)$에 퀸을 둘 때 isused[x-y+N-1]를 true로 만들면 됩니다.

 

 

 

정답 코드를 확인해보세요. 이번에는 isused를 전역변수로 두었습니다.

 

백트래킹에서 자주 실수하는 요소들은 이렇습니다. 특히 3번과 4번 요소를 정말 주의해야 합니다. 재귀를 들어갔다가 나올 때 isused와 같은 값을 반드시 되돌려놔야하고, vector로 값을 관리할 때에는 인자로 참조자를 넘겨주어야 합니다. 그렇지 않으면 vector의 복사가 발생해 시간에서 굉장히 큰 손해를 봅니다. 1, 2번 요소는 시간초과를 발생하지 않도록 하기 위한 부분들이고 제출을 하기 전에 직접 오래 걸릴 것 같은 테스트케이스를 디버그 모드가 아닌 릴리즈 모드에서 돌려보면서 시간이 초과될 것 같으면 최적화를 더 하는 식으로 해야합니다.

 

시뮬레이션 문제는 말 그대로 주어진 문제의 상황을 그대로 따라가며 풀이를 해야 하는 문제입니다.

 

윷놀이를 실제로 구현하기 / 파싱/ 뿌요뿌요에서 연쇄가 몇 단계에 걸쳐 일어나는지 계산하기 등등 워낙 종류가 다양해서, 다양한 문제를 풀어보며 구현력을 높이는 방법 말고는 마땅한 대비법이 없습니다.

 

구현을 할 때 기능 단위로 함수를 적절히 쪼개고 중간 결과를 계속 출력하게끔 하면서 완성을 하면 되긴 되는데 딱히 방법론이라고 할만한건 없고 그냥 각자 자기에게 맞는 방법대로 구현을 하면 됩니다.

 

문제를 시뮬레이션으로 풀기 전에 시간복잡도를 계산할 수 있어야 합니다. 그렇지 않으면 몇 시간에 걸쳐 코드를 다 짠 후 제출하고 나서야 시뮬레이션으로 풀면 시간초과가 발생함을 알아버리는 상황이 생길 수도 있습니다. 그리고 시간복잡도를 계산하기 위해서는 순열과 조합에 대한 개념을 가지고 있습니다.

 

아래의 4개의 질문에서 모르는 내용이 있다면 고등학교 수학 수준의 경우의 수, 순열과 조합에 대한 지식을 따로 공부를 하시는걸 강력히 추천드립니다.

 

N과 M 문제를 풀어보셨다면 1, 2, 3, 4를 배치해 만들 수 있는 모든 길이 4짜리 수열을 출력하는 문제를 해결할 수 있을 것입니다. 그런데 STL에는 next_permutation(레퍼런스), prev_permutation(레퍼런스)라는 아주 강력한 2개가 있습니다. 각각 사전 순으로 다음 순열과 이전 순열을 만들어주는 함수입니다. 동작 원리는 엄청 어렵지는 않지만 건너뛰겠습니다. 궁금하면 구글에 next_permutation implementation이라고 검색해보세요.

 

N과 M 문제를 풀기위해 힘겹게 재귀로 풀어야했던 문제를 next_permutation으로 이렇게 정말 간단하게 해결할 수 있습니다. next_permutation에는 시작 주소(혹은 시작 참조자)와 끝 주소(혹은 끝 참조자)를 넣어주면 해당 범위의 수열을 사전 순으로 다음 순열로 바꿔줍니다.

 

next_permutation을 응용하면 단순히 $N$개를 섞는 것 말고도 $M$개를 뽑는 문제도 해결할 수 있습니다. 예시를 참고해보세요.

 

이제 BOJ 1182번 : 부분집합의 합 문제를 풀어봅시다. 원소가 $N$개인 집합에서 부분집합의 원소는 $O(2^N)$개이므로 모든 부분집합에 대해 합을 계산해보면 됩니다. 모든 부분집합을 구할 때 이진수를 이용하는 테크닉을 쓰면 20중 for문을 짤 필요 없이 해결할 수 있습니다.(정답 코드) 구체적으로 테크닉이 어떻게 동작하는지는 다음 슬라이드를 참고하세요.

 

N이 3일때를 생각해봅시다. $$에서 부분집합들을 뽑기 위해 0부터 7을 이진수로 표시한 값을 이용하면 됩니다. $2^2$의 자리는 $A[2]$에 대응되고 $2^1$의 자리는 $A[1]$에 대응되고 $2^0$의 자리는 $A[0]$에 대응됩니다. 예를 들어 6는 이진수로 110 이므로 $A[2], A[1]$에 대응됩니다. 이를 구현하기 위해서는 2로 나눈 나머지를 계산하고 2로 나누는 작업을 3번 반복하면 됩니다.

 

이번 강의 내용이 지금까지 다룬 8개의 강의 중에서 가장 큰 고비입니다. 잘 이겨내시고 문제를 많이 풀어보셔서 숙달하시길 바랍니다.

 

특히 삼성 역량테스트 A형을 목표로 하시는 분들은 A형의 거의 모든 문제가 BFS/DFS/백트래킹/시뮬레이션/전수조사 범주를 벗어나지 않기 때문에 0x05강과 이번 0x07강을 중점적으로 보고 그룹 문제집에 들어있는 문제를 전부 다 풀어보면 충분한 대비가 될 것입니다.