알고리즘
백트래킹(Backtracking) (with 예제 Leetcode 17. Letter Combinations of a Phone Number)
백트래킹이란 일반적으로 모든 가능한 해를 시도해보며, 조건을 만족하는 해를 찾는 알고리즘이다. 조건을 만족하지 않으면 이전 단계로 돌아가서 다른 가능성을 시도하하기 때문에 "백트래킹(backtrack)"이라고 한다. DFS는 모든 경로를 탐색하는데 백트래킹은 조건이 있어 모든 경로가 아닌 조건에 맞는 경로만 탐색한다는 차이점이 있다. 이전상태로 돌아오는 작업이 필요하기 때문에 스택(혹은 재귀)를 사용하는 DFS를 이용해서 주로 구현한다. DFS를 이용한다면 기본적으로 구성은 비슷하다. 탐색을 멈출 조건문이 제일 처음에 들어가고, 모든 노드 방문을 위한 반복문, 내부에서 본인을 재귀 호출, 요구사항에 맞는 값 리스트에 추가해서 리턴하거나 프린트 말로만 설명하면 헷갈리니까 리트코드에서 예제를 하나 가져와서 ..
2023. 7. 29.
