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

[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.

 

2월 13일 오늘의 강의

 

백 트래킹

백 트래킹(back tracking) 또는 퇴각 검색(back track)이라고 부른다. 이는 알고리즘이라고 하기 보다는 제약 조건을 만족하는 문제에서 정답을 찾기 위한 기법이라 볼 수 있다.

 

정답을 찾기 위해 후보 군에서 제약 조건을 체크하다가, 해당 후보군이 제약 조건을 만족하지 않을 경우 back track하여 이 후보군과 관련된 경우의 수를 더이상 찾지않고 다음 후보군으로 넘어가며 제약 조건을 만족하는 경우를 찾는 방법이다.

 

실제 구현하게 되면 고려할 수 있는 모든 경우의 수를 상태 공간 트리(State Space Tree)로 표현한다. 그리고 이러한 트리에서 DFS 알고리즘을 통해 후보군을 확인한다. 이때 Promising과 Pruning의 기법이 사용되는데 Promising은 해당 루트가 조건에 맞는지를 검사하는 기법이고, Pruning은 조건에 맞지 않을 경우 back track 하여 다른 후보군을 탐색하는 기법이다. 이를 통해 탐색의 시간을 최소화할 수 있다.

 

상태 공간 트리

 

 

출처 : 잔재미 코딩

 

상태 공간 트리는 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리를 의미한다. 만약에 미로 찾기에서 출구까지 가는 경로를 찾을 경우 선택할 수 있는 모든 경로를 트리로 만들 수 있다면, 막다른 곳이나 출구가 leaf node에 위치하게 될 것이다. 상태 공간 트리를 깊이 우선 탐색(DFS)하게 된다면 정답을 찾을 때까지 반복하게 되는데 이러한 방법은 비효율적이기 때문에 백 트래킹 기법을 사용하여 효과적으로 탐색할 수 있게 된다.

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

 

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