백트래킹 공부
백트래킹
- 백트래킹은 코딩 테스트에서 자주 출제되는 유형 중 하나로, 가능한 모든 경우의 수를 탐색하여 해답을 찾는 알고리즘입니다.
- 해당 글은 백트래킹 문제를 만났을 때 접근하는 방법을 정리했습니다.
접근 방법
- 모든 경우의 수를 시각적이고 체계화하는 방법인 트리를 그리는 것 입니다.
- 발전 단계 n 정의: 트리의 깊이, 현재 탐색 단계를 나타내는 변수 n을 정의합니다.
- 트리 확장: 각 단계에서 가능한 선택지를 자식 노드로 확장합니다.
- 트리가 완성되면 시간복잡도를 고려했을 때 시간 초과가 발생할 가능성이 있다면 다른 방법을 찾고, 가능성이 없다면 이대로 진행합니다.
- 또한, 어떤 트리로 표현할 것인지 선택하는 것도 중요합니다.
- 이진 트리로 표현할 경우 주어진 N의 크기가 50까지 가능합니다.
- 멀티 트리로 표현할 경우 주어진 N의 크기가 15까지 가능합니다.
- 물론, 해당 범위는 가지치기 같은 최대한 경우의 수를 줄였을 때 가능한 범위입니다.
- DFS의 재귀 함수 형태로 구현합니다.
- 발전 단계 n이 최종 목표에 도달하면 무조건 종료합니다. 또, 정답 처리도 같이 처리합니다.
- 하부 함수 호출을 위한 제약 조건을 확인하고, 재귀 호출이 끝난 후, 현재 단계에서 변경했던 모든 상태를 다음 탐색을 위해 원대로 복구합니다.
- 마지막으로 시간 초과를 방지하기 위해 가지치기를 고려합니다.
예시를 통한 설명
- 백준 N과 M (1)를 예시로 설명하겠습니다.
- 가능한 모든 경우의 수를 구하기 위해 트리를 그려야 하는데 발전 단계 n을 선택한 숫자로 정의합니다.
- 여기서 핵심은 테스트 케이스를 기반으로 하는 것이 아니라 일반화를 해서 트리를 표현하는 것 입니다.
- 시간복잡도를 계산했을 때 8!이기 때문에 문제가 없습니다.
- DFS 함수를 구현하기 위해서 제약조건을 확인합니다.
트리 표현 과정
- 발전 단계 n이 아직 아무것도 선택하지 않아서 0으로 표시하고, 1부터 N까지 선택을 것을 표시합니다.
- 테스트 케이스를 기반으로 하는 것이 아니라 일반화를 하면서 표현합니다.
- 테스트 케이스를 기반으로 하는 것이 아니라 일반화를 하면서 표현합니다.
- 발전 단계 n이 1이 되면 1부터 N까지 선택하는 것을 표시합니다.
- 여기서 중요한 것은 2부터 N까지 표시하는 것이 아니라는 것 입니다.
- dfs가 자기자신 호출이기 때문에 1부터 N까지 선택하게 됩니다.
- 가능한 모든 경우를 탐색이기 때문에 가능한 부분을 체크하는 작업이 필요합니다.
- 거기서 필요한 것이 방문 체크입니다.
- 그렇게 일반화 하면 발전 단계 n이 M-1이 되면 1부터 N까지 선택하고 발전 단계 n이 M과 같이지면 종료하게 설계합니다.