Back Tracking

 

❐ Description

---

백트랙킹 문제를 풀면서 면접 질문 대비 겸  개념을 정리해보자.

그리고 나만의 풀이 템플릿 까지 작성하여 라이브 코테도 준비하자.

 

 

 

 

 

❐ Back Tracking이란?

---

Back Tracking은 모든 가능한 해를 탐색하기 위해 DFS를 기반으로 하는 알고리즘 설계 기법이다.

주로 문제의 해를 구성하는 과정에서, 더 이상 유망하지 않은 해(조건에 부합하지 않거나 불가능한

경우)를 만나면 되돌아가(BackTrack) 다른 경로를 탐색한다. 이를 통해 불필요한 계산을 줄이고

효율적으로 문제를 해결할 수 있다.

 

• DFS 기반 : 트리 또는 그래프 형태로 해를 구성하며, 깊이 우선 탐색을 진행한다.
• Pruning(가지치기) : 조건에 맞지 않거나 유망하지 않은 경로를 탐색하지 않고 되돌아가는 과정.
• 결과 탐색 : 모든 가능한 해를 탐색하거나, 하나의 해만 찾는 문제에도 사용된다.

BackTracking은 특히 탐색 공간이 클 때 가지치기를 통해 효율적으로 문제를 해결할 수 있는 강력한

기법이다. 문제의 제약 조건과 목표에 따라 Pruning 조건을 적절히 설계하는 것이 핵심이다.

 

 

 

 

❐ Sudo Code

---

public void backTracking(현재조건) {
    if (해결 조건 충족) {
        해를 저장;
        return;
    }
    
    for (가능한 선택 : 현재 상태에서의 선택지들) {
        if (유요한 선택인지 확인) {
            선택 적용;
            backTraking(다음 상태); // 재귀호출 
            상태 되돌리기; // BackTrack
        }
    }
}

 

 

 

 

 

❐ 장단점

---

1. 장점

• 효율적 : 불필요한 탐색을 줄여 메모리와 시간을 절약
• 직과적 : 재귀 구조를 활용하여 구현이 명확

2. 단점

• 성능 한계 : 해 공간이 큰 경우에는 비효율적
• 가지치기 전략이 약할 경우 많은 중복 계산 발생

 

 

 

 

 

---