Backtracking (백트래킹)

# P / NP 문제

P : 결정론적 다항 시간(Deterministic Polynomial time)에 문제의 해를 찾을 수 있는 문제 집합입니다. ex) O(n^2)

NP : 비결정론적 다항 시간(Non-deterministic Polynomial time)에 문제의 해를 검증할 수 있는 문제 집합입니다. 즉, 다항 시간 내에 주어진 답이 올바른지 검증하는 알고리즘이 존재합니다. ex) O(2^n)

 

이러한 NP문제를 풀때 백트래킹을 사용하면 문제를 효율적으로 해결하는데에 도움을 줍니다. (다만, 모든 NP문제를 백트래킹으로 풀 순 없습니다. 상태공간트리로 표현가능해야합니다.)

 

 

# backtracking이란?

백트래킹(Backtracking) 알고리즘은 가능한 모든 상태를 탐색하면서 해결책을 찾아내는 알고리즘입니다. 이 알고리즘은 일반적으로 재귀적인 방법을 사용하며, 상태 공간 트리(State Space Tree)를 탐색하면서 최적의 해를 찾아내는 방식으로 동작합니다.

상태 공간 트리는 가능한 모든 상태를 노드로 표현한 트리입니다. 각 노드는 가능한 상태를 나타내며, 자식 노드는 현재 상태에서 가능한 다음 상태를 나타냅니다. 따라서 이 트리를 탐색하면서 최적의 해를 찾아내는 것이 백트래킹 알고리즘의 핵심입니다.

# 동작 방식

1. 상태 공간 트리의 루트 노드에서 시작합니다.
2. 현재 노드에서 가능한 모든 경우의 수를 생성합니다.
3. 각 경우의 수에 대해 하나씩 탐색하며, 유망한 경우에만 계속 진행합니다.
4. 유망하지 않은 경우, 해당 경우의 수를 포기하고 이전 노드로 돌아갑니다. 이 과정을 백트래킹이라고 합니다.
5. 모든 경우의 수를 검사할 때까지 2-4번의 과정을 반복합니다.

백트래킹 알고리즘은 재귀 함수를 사용하여 구현할 수 있습니다. 재귀 함수는 상태 공간 트리를 구성하며, 탐색할 경우의 수가 많은 경우에는 큰 스택 메모리를 필요로 할 수 있습니다. 따라서 백트래킹 알고리즘을 구현할 때는 가지치기(Pruning) 기술을 사용하여 불필요한 탐색을 줄이는 것이 중요합니다.

 

 

# 그렇다면 백트래킹은 NP문제의 시간복잡도를 낮출수있는가?

백트래킹 알고리즘은 일반적으로 가지치기(Pruning) 기술을 사용하여 불필요한 계산을 줄이기 때문에, 평균적인 수행 시간은 줄어들 수 있습니다. 가지치기는 알고리즘의 효율성을 높이는 데 중요한 역할을 합니다. 따라서 평균적인 수행 시간에는 백트래킹 알고리즘이 더 효율적일 수 있습니다.

그러나 빅오표기법은 알고리즘의 최악의 경우 시간 복잡도를 기준으로 하므로, 백트래킹 알고리즘의 경우 최악의 경우 시간 복잡도가 변하지 않기 때문에, 빅오표기법으로는 변화가 없다고 말할 수 있습니다. 따라서 백트래킹 알고리즘의 효율성을 평가할 때에는 최악의 경우 시간 복잡도와 함께 평균적인 수행 시간도 고려해야 합니다.

 

(근데 왜 코테문제에선 통과할 수 있었던거지...? 그냥 테스트케이스가 최악의 경우까진 주지 않나봅니다.)