백트래킹 썸네일형 리스트형 [Algorithm] 백트래킹(Backtracking) BOJ 1987번 알파벳 문제를 단순히 DFS로 풀다가, dx, dy로 나아가는 방향 선정에 따라 답이 달라지는 것을 느껴 관련 알고리즘인 백트래킹에 대해 정리하려고 한다! 백트래킹(Backtracking) 알고리즘의 정의 - ' 가능한 모든 방법을 탐색한다 ' 라는 아이디어를 가진 알고리즘 - 백트래킹(Backtracking)이란, 현재 상태에서 가능한 모든 후보군을 따라 들어가며, 해결책에 대한 후보를 구축해 나아가다, 가능성이 없다고 판단되는 즉시 후보를 포기하면서 정답을 찾아가는 알고리즘이다. - 즉, 해를 찾는 도중 해가 아니어서 막히게 되는 경우 -> '다시 되돌아가서' 해를 찾아가는 기법 - 최적화 문제와 결정 문제를 푸는 방법 DFS와 백트래킹 1. 깊이 우선 탐색(DFS) - DFS는 가.. 더보기 이전 1 다음