패스트캠퍼스 챌린지 23일차

---

Part 2. 알고리즘 이론

Ch 21. 백 트래킹

01. 백 트랙킹 알고리즘 이해 (1)

---

• 80.백 트래킹(backtracking): 크루스칼 알고리즘이나 프림 알고리즘처럼 특정 문제를 풀기 위한 특정 알고리즘이 아니라 일반적으로 문제를 푸기 위한 전략 중 하나. 제약조건 문제에서 해를 찾기 위한 전략. 모든 경우의 수를 상태 공간 트리(State Space Tree)로 표현하고 각 후보군을 깊이우선방식(DFS)으로 확인
• 가지치기(Pruning): 나뭇가지를 쳐내듯 조건에 맞지 않으면 쳐내듯이 포기하고 다른 루트를 탐색하여 시간을 절약하는 방법
  
  백 트래킹은 해를 찾기 위해 모든 후보를 확인하다가 제약조건을 만족하지 못하면 퇴각 검색(backtrack)하여 다른 문제로 넘어가 최적의 해를 찾는 방법이다. 우리가 오지선다 문제를 풀 때, 다섯 개의 지문 중 정확하게 오답인 지문에 엑스 표를 치면 해당 지문은 고려하지 않고 다른 지문 중 답을 찾는다. 이처럼 정답이 아닌 답을 지우는 것처럼 조건에 맞지 않으면 포기하고 다른 것을 탐색하는 기법을 가지치기라 한다. 백 트래킹에서 가장 많이 나오는 문제는 체스판 문제이다. N*N의 체스판에서 대각선, 수직, 수평으로 이동할 수 있는 퀸 말이 서로 공격할 수 없도록 배치하는 문제이다. 이 때, 체스판에서 직접 경우의 수를 구하지 않고 체스판처럼 2차원 배열을 선언하고 그 안에서 퀸의 위치를 고려함으로써 백 트랙킹으로 문제를 해결한다.

 

 

---

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

- 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.-