백트래킹(Backtracking)
DFS(깊이 우선 탐색)을 통해 가능한 모든 경로를 탐색한다.
모든 경로를 탐색하는 과정에서 특정 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지않고 되돌아 간다.
이 과정을 가지치기라고 한다. 가지치기를 잘하느냐에 따라 효율성이 결정이 된다.
유명한 백트래킹 문제로 백준에 n-queen 문제가 있다 풀이를 정리한 글이 있으니 읽어보자.
음악하는 개발자
DFS(깊이 우선 탐색)을 통해 가능한 모든 경로를 탐색한다.
모든 경로를 탐색하는 과정에서 특정 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지않고 되돌아 간다.
이 과정을 가지치기라고 한다. 가지치기를 잘하느냐에 따라 효율성이 결정이 된다.
유명한 백트래킹 문제로 백준에 n-queen 문제가 있다 풀이를 정리한 글이 있으니 읽어보자.