backtracking1 Backtracking Algorithm Method 백트래킹 알고리즘은 모든 솔루션을 탐색해볼 수 있는 방법이다. 탐색 과정은 Tree 자료 구조를 DFS(depth first order)로 탐색하는 것과 동일하다. Tree 자료 구조를 기준으로 Partial Candidates는 tree의 Node로 표현되고, 1 depth 마다 부모 노드의 partial candidates에서 자식 Node의 값이 추가된다. 수많은 솔루션에서 정답만 찾아야 한다면, 백트래킹은 다음과 같이 동작한다. DFS와 같이 root node에서 부터 tree를 재귀적으로 순회한다. 각 노드에서 알고리즘은 노드가 valid solution인지 체크한다. 만약 solution이 아니라면 스킵한다. 정답이라면 저장한다. 특정 Depth에서의 노드 값들의 배열을 저장해야 .. 2023. 3. 9. 이전 1 다음