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

앞으로는 알고리즘문제들을 풀기 전에 이론에 대해서 좀 더 공부하고, 글로도 남겨서 차근차근 정리하려고 한다. 작년에 수강했던 알고리즘수업 때 필기와 인터넷 자료, 알고리즘 문제해결전략 책을 종합해서 공책에 필기로도 남기고 블로그에 글도 남길 것이다. 앞서서 공부했던 다이나믹프로그래밍, DFS, BFS에 대해서도 다시 정리를 하고 글로 남길 예정이다.  

어제부터 다시 공부하기 시작한 알고리즘 분류는 Backtracking(백트래킹)이다. '백트래킹이란 무엇이다'라고 확실히 정의를 내리기는 어렵지만, 백트래킹은 가능한 모든 조합에 대해 전부 시도를 하는 것이다. 이 말을 자세히 다시 살펴보면 '가능한 모든 조합'이기 때문에 조건에 맞을 경우에 전부 시도를 한다. 알고리즘 교수님께서 해주신 필기에는 "DFS with promising function" 이라고 되어있는데 어느 정도 명확하고 와닿는 설명인 것 같다. 단순히 DFS와 BFS를 위한 문제를 풀 때는 그래프 모양만 생각했었는데 백트래킹에서는 트리모양을 생각하면 좀 더 이해하기가 쉽다. promising function에서 promising은 tree에서 특정 node를 방문할 것인지 아닌지를 판단하는 것으로, 해당 조합이 가능한 경우인지를 판단하는 것이다. 

백트래킹으로 문제를 풀 경우 대부분은 몹시 효율적이지만 worst case일 경우는 비효율적이다. 이 말은 100% 이해하지는 못했는데, 좀 더 여러 문제를 풀면서 시간복잡도에 대해서 공부를 해봐야 할 것 같다.

백트래킹을 통해 내가 풀어본 문제는 부분집합의 합(백준 1182번), 암호 만들기(백준 1759번)이다. 아직은 두 문제밖에 풀지 못했는데 백트래킹에 대한 개념을 이해하는 데 약간 도움이 됐다. 첫 번째, 부분집합의 합문제는 강의자료를 살펴보니 작년에 알고리즘을 수강할 때도 풀었던 문제였다. 원소가 배열로 주어지고, 그 배열들의 합으로 특정한 합을 얼마나 만들어낼 수 있는지를 푸는 문제다. 특정한 합을 '얼마나' 만들어 낼 수 있는지를 알아내야 하므로 모든 부분집합을 만들어보고 그때의 합을 계산해야 한다. 즉, 가능한 모든 조합에 대해서 전부를 시도해야하므로 백트래킹을 사용해야한다.(문제를 리뷰한 다른 사람들 글도 참고했었는데, brute force 방식으로도 푸는 것 같다. 나는 아직 brute force 부분에 손을 대지 않아서.. 자세히 읽어보진 않았다.) 두 번째, 암호 만들기문제는 첫 번째 문제보다 좀 더 까다로웠다. 주어진 알파벳을 통해서 오름차순으로 가능한 암호들을 다 출력해야 한다. 자음은 두개 이상 포함해야 하고 모음은 한 개 이상 포함해야 하는 조건도 있다. 각 조건에 대해 백트래킹을 수행하는 함수에 파라매터로 넘겨주면 조건을 체크하면서 문제를 해결할 수 있다. 

사실 어제 백트래킹 이론에 대해 다시 읽어보고 공부를 할 때, 가능한 모든 조합에 대해 전부를 시도한다는 개념적인 저 말이 잘 와닿지를 않았다. 왜냐면 작년 알고리즘을 수강할 때, 백트래킹을 배우고 처음 풀었던 문제가 n-queen 이었는데 백트래킹이란 말 그대로 다시 거꾸로 돌아가서 탐색한다는 부분만 너무 강조돼서 기억에 남았었기 때문이다. 그래서 어제 계속해서 필기했던 걸 다시 보고 인터넷을 계속 검색해서야 거꾸로 돌아간다는 저 부분이 강조된 기억을 좀 지울 수 있었다. 두 문제밖에 안풀었으니 n-queen문제도 다시 풀어보고 백트래킹을 복습해보도록 해야겠다.