염딩코

이번 시간에는 Backtracking에 대해서 알아봅시다! Backtracking이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. DFS와 Backtracking DFS DFS는 가능한 모든 경로(후보)를 탐색합니다. 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다. 따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것입니다. Backtracking 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아갑니다. 즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다. 이를 pruning..

모든 경우의 수를 전부 고려하는 알고리즘. 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식입니다. 일종의 트리 탐색 알고리즘이라고 봐도 됩니다. 방식에 따라서 * 깊이우선탐색(Depth First Search, DFS) * 너비우선탐색(Breadth First Search, BFS) * 최선 우선 탐색(Best First Search/Heuristic Search) (그냥 뇌없이 짤 수 있다는 것이 장점입니다.) DFS와 Backtracking * DFS(깊이 우선 탐색) : DFS는 가능한 모든 경로(후보)를 탐색합니다. 따..