목록backtracking (1)

나의 공부장

백트래킹, 브루트 포스, DFS의 차이점?

위의 세 가지 모두 경우의 수를 다 돌려보는 느낌이 들지만, 정확히 따지자면 다음과 같다고 합니다. 백트래킹 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법입니다. 반드시 DFS만으로 가능한 게 아니고 BFS 등으로도 가능하지만 일반적으로는 DFS와 연관이 깊다고 합니다. 브루트 포스 꼭 '깊이'나 '탐색'의 개념이 아니더라도, 모든 경우의 수를 다 대입해보는 기법입니다. DFS 여러 지점을 한 단계씩 거쳐가면서 탐색하고, 스택의 개념을 이용해서 이전 단계로 돌아가야만 DFS라고 합니다.
알고리즘/알고리즘 관련 궁금증 2020. 5. 27. 00:54
이전 Prev 1 Next 다음