[알고리즘] 🤷‍♂️ 백트래킹 알고리즘 / Backtracking Algorithm

🤷‍♂️ 백트래킹(Backtracking) 알고리즘

모든 경우의 수를 전부 고려하는 알고리즘으로 트리형 자료구조에 적합하며 계속해서 답이 될 수 있는 후보 노드들을 만들어내고, 해당 후보로는 적절한 답을 얻을 수 없는 후보를 철회("Backtracks")하면서 문제를 해결하는 알고리즘이다.

가장 유명한 예제로는 서로를 공격할 수 없는 8개의 퀸의 위치 배열을 찾는 N-queens 문제가 있다. N-queens 문제를 백트래킹 알고리즘으로 접근하면, 첫 행부터 아래로 내려가면서, 이미 존재하는 퀸에 가로 세로 대각선에 존재하는 후보는 철회하는 방식으로 풀 수 있다.

백트래킹 알고리즘은 '부분적 후보 해결책'의 개념을 확인하는 문제와 그것이 유효한 해결책으로 완성될 수 있는 지의 여부를 상대적으로 빠르게 시험할 때만 적용할 수 있다. 백트래킹 알고리즘은 주어진 값을 무질서한 표에 배치하는 문제애는 쓸 수가 없다. 하지만 많은 수의 후보들을 단일 검증으로 제거할 수 있기 때문에, 제대로 적용만 된다면 백트래킹은 보통 모든 후보군을 연산하는 브루트 포스(brute force, 무차별 대입)보다 훨씬 빠르다.

백트래킹 알고리즘은 가로세로퍼즐, 복면산(verbal arithmetic), 스도쿠 그리고 많은 퍼즐들 같은 제약 충족 문제를 해결하는 중요한 도구이다. 이는 배낭 문제(Knapsack Problem)와 다른 조합 최적화 문제의 파싱을 위한 보통 가장 간편한(가장 효율적이지 않다면) 기술이다. 또한 아이콘, 플래너, 프롤로그 같은 소위 논리 프로그래밍 언어들의 기초가 된다.

백트래킹 알고리즘은 유저가 제시한 해결할 문제를 정의한 절차적 과정에 의존하며, 이는 일부 후보들의 특성일 것이다. 그리고 어떻게 그들이 완벽한 후보들로 나아가는 지에 대한 것도 정의할 것이다. 따라서 이는 특정 알고리즘이라기 보다는 메타발견적학습이라 할 수 있다. 그러나 다른 메타발견적학습들과는 다르게, 백트래킹 알고리즘은 유한한 문제의 정해진 시간에서 모든 답을 찾는 것을 보장한다.

백트랙이라는 용어는 1950년대 미국의 수학자 D. H. 레머에의해 만들어졌다. 선구자적 문자처리언어인 SNOBOL이 최초로 백트랙킹 기능을 보유한 것으로 알려져 있다.

출처: https://en.wikipedia.org/wiki/Backtracking

[예시] 백트랙을 이용한 스도쿠 풀이

백트랙 알고리즘 이용해 해결한 문제

• [BOJ] 👸 N-Queens / 파이썬
• [프로그래머스] 🚍 셔틀버스 / 파이썬

영어로 된 위키피디아를 번역해서 올리다보니 오역이 있을 수도 있는 점 죄송합니다.