데이터 분석 기술 블로그

1. 상태 공간 트리2. 상태공간트리를 구축하여 문제를 해결 3. 연습문제

1. 문제 제시 : N-Queen 문제2. 백트래킹(Backtracking) 개념여러 가지 선택지(옵션)들이 존재하는 상황에서 한가지를 선택합니다.선택이 이루어지면 새로운 선택지들의 집합이 생성됩니다.이런 선택을 반복하면서 최종 상태에 도달합니다.올바른 선택을 계속하면 목표 상태(goal state)에 도달합니다.

1. 백트래킹백트래킹 (Backtracking) 기법은 해를 찾는 도중에 '막히면' (즉, 해가 아니면) 되돌아가서 다시 해를 찾아가는 기법입니다.백트래킹 기법은 최적화 (optimization) 문제와 결정 (decision) 문제를 해결할 수 있습니다.결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'가 답하는 문제입니다.미로 찾기n-Queen 문제Map coloring부분 집합의 합(Subset Sum) 문제 등백트래킹과 깊이 우선탐색과의 차이어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄입니다. (Prunning 가지치기)깊이우선탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를..