백트래킹

-1) 백트래킹과 백트래킹 알고리즘 개념

깊이 우선 탐색, 너비 우선 탐색 방법은 데이터를 전부 확인하는 방법
-> 완전 탐색 : 모든 경우의 수를 탐색하는 방법 - 대부분 비효율적

백트래킹이란?
어떤 가능성이 없는 곳을 알아보고 되돌아 가는 것

백트래킹 알고리즘이란?
가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘

문제마다 효율이 달라지므로 시간 복잡도를 특정하여 정의하기는 어렵지만 완전 탐색하는 방법보다 백트래킹이 효율적

유망함수란?
백트래킹 알고리즘의 핵심은 "해가 될 가능성을 판단하는 것"
그 가능성은 유망 함수라는 것을 정의하여 판단

1. 유효한 해의 집합을 정의
2. 위 단계에서 정의한 집합을 그래프로 표현
3. 유망 함수를 정의
4. 백트래킹 알고리즘을 활용해서 해를 찾음

백트래킹 알고리즘 문제에 적용하기

부분 집합 합

1부터 N까지 숫자를 조합했을 때 합이 K가 되는 조합을 찾는 문제

N퀸 문제

체스의 퀸을 N x N 체스판에 N개 배치했을 때, 서로를 공격할 수 없는 위치에 놓을 수 있는 방법이 있는지 찾는 문제