[ 알고리즘 ] 백트래킹 (Backtracking)
백트래킹 이란?재귀적으로 문제를 해결하는 기법으로, 가능한 모든 해를 탐색하면서 불가능한 해를 만났을 때는 되돌아가서 다른 경로를 탐색하는 방식. 백트래킹 단계백트래킹의 구조는 기본적으로 DFS(깊이 우선 탐색)를 기반으로 하되, 조건문을 사용하여 불가능한 경로를 조기에 포기하는 방식이며 이를 통해 불필요한 탐색을 줄이고 효율적으로 해를 찾는다.해 탐색: 현재 경로를 확장하여 해를 탐색한다.유효성 검사: 현재 경로가 유효한지 검사 후 유효하지 않으면 그 경로를 포기하고 돌아간다.완전성 검사: 현재 경로가 완전한 해인지 검사한다. 완전한 해라면 결과를 기록한다.백트래킹: 위 단계들을 반복하며, 모든 가능성을 탐색한다. 백트래킹 사용백트래킹은 퍼즐 문제(예: 미로 찾기, N-퀸 문제), 제약 만족 문제,..
코딩테스트/[ 알고리즘 ]
2024. 5. 20. 14:28
