목차

1. 백트래킹

1-1. 백트래킹이란

백트래킹은 ‘완전탐색 알고리즘' 중 하나로 한 번에 하나의 문제를 해결하되, 가지치기(Pruning) 를 통해 유망하지 않은 경로는 고려하지 않고 탐색하는 방법

• 기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다' 는데 기본 아이디어가 있다.

• 대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색)이 있다.

  DFS 는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동함

  DFS 의 장점 : 무한히 깊은곳을 찾아야할때 효과적

  but DFS 는 모든곳을 방문하기 때문에 목표지점이 있지 않는 경로로 빠져서 비효율적이 될 수도 있음

• 비효율적인 경로를 차단하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 백트래킹 알고리즘

• 백트래킹은 DFS에 가지치기 (Pruning) 를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법

• 가지치기를 얼마나 잘하느냐에 따라서 효율이 극대화 될수 있음

• 우리가 알아야할것은 '배제', '풀이 시간 단축'

• 백트래킹은 깊이우선탐색(Depth-First Search)과 마찬가지로 스택을 사용한다!

가지치기(Pruning)

가지치기는 모든 해를 전부 검사(brute force)와 백트래킹을 구분하는 핵심으로, 기준함수(현재 만들어진 케이스가 해답의 조건을 만족하는지 검사하는 함수)를 통해 가능성이 없는 케이스를 배제하여 풀이시간을 상당히 줄일 수 있다.

1-2 백트래킹 문제 접근

<aside> 💡 Sum of SubSet 문제 n =4, S = { 5, 9, 11, 20 }, m = 25 일 때, S의 모든 부분집합의 합이 m이 되는 모든 경우의 수를 찾는 문제 정답: {5, 9, 11}, {5, 20}

</aside>

1) 문제 상황을 상태공간 트리로 표현하기