백트래킹문제 (1) 썸네일형 리스트형 [Algorithm] 백트래킹(Backtracking) 백트래킹(Backtracking) ? 백트래킹은 '가능한 모든 방법을 탐색한다'는 기본 아이디어에서 나온다. 브루트 포스 알고리즘과의 차이는 브루트 포스의 경우 모든 경우를 전부 시도해보는 방식이라면, 백트래킹의 경우 탐색을 진행하면서, 조건에 맞지 않는 부분을 제외하며 진행하는데에 차이가 있다. DFS는 현재 지점에서 방문할 곳이 있다면, 재귀 호출을 이용하여 계속 이동하게 되는데, 모든 곳을 방문하기 때문에, 목표지점이 있지 않는 경로에 빠져, 비효율적인 결과를 초래할 수 있다. 그래서 이와 같은 비효율적인 경로를 차단하고 목표지점에 갈 수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘이다. 가지치기를 얼마나 잘하느냐에 따라 시간이 많이 단축이 될 수가 있으니, 반복적인 연습을 통해 조건.. 이전 1 다음