목록BackTracking (1)

데이터 분석 기술 블로그

스택 - 백트래킹

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