알고리즘 - 백트래킹(Back tracking)에 대한 이해

백준 사이트를 통해 알고리즘 공부를 하던 중, 백트래킹에 대한 개념이 명확하지 않아 정리해봅니다. 이론은 SW expert academy에서, 실습은 백준에서 참고했습니다. N-Queen 문제 N x N 체스판에서 N개의 퀸이 서로를 공격하지 못하게 배치하는 문제 백트래킹 기법이란? 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법 최적화 문제와 결정 문제를 해결할 수 있음 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes or no로 답하는 문제 예) 미로찾기 미로에서 빠져나갈 경로가 존재하는가? -> 결정 문제 미로에서 최단거리로 나갈 수 있는 경로는 무엇인가? -> 최적화 문제 올바른 선택을 계속하면 ..