pruning1 [코딩 + 알고리즘 완주반] 24일차. 백트래킹 # 백트래킹 - 제약조건만족 문제에서 해를 찾기 위한 전략 - 해를 찾기 위해 조건을 점진적으로 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단하는 즉시 backtrack( 다시 이 후보군을 체크하지 않음) 하고 다른 후보군으로 넘어가 최적의 해를 찾는 방법 - 모든 경우의 수를 상태공간트리 (State Space Tree) 를 통해 표현 - 각 후보군을 DFS 방식으로 확인 - Promising : 해당 루트가 조건에 맞는지 검사하는 기법 - Pruning (가지치기) : 조건에 맞지 않으면포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법 # N-Queen 문제 N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제 퀸 : 수직, 수평, 대각선 이동 가능 Pr.. 2021. 4. 14. 이전 1 다음 반응형
