[알고리즘] 탐색(5) - 가지치기(Pruning)

개념 가지치기(Pruning)는 탐색 과정에서 필요없는 과정을 줄여 최적화 시키는 것입니다. 단편적인 예를 들면, 탐색한 값들 중 최솟값을 구하는 문제에서 현재까지 탐색한 결과값보다 값이 커질 경우 더이상 탐색하지않고 종료하는 것이 가지치기입니다. 위 사진*은 특정 방법으로 노드 하나하나 탐색하고 있을때, 결과의 최솟값을 구해야하는 문제에서 모든 곳을 탐색한 경우의 수라고 가정해보겠습니다. 이 문제의 답이 빨간색 노드가 가지고있는 값이 최솟값이라고 하고 파란색 노드가 빨간색 노드의 값보다 커지는 위치라고 했을때, 위처럼 모든곳을 탐색할 필요가 있을까요? 파란색 노드 아래로는 탐색하지 않아도 적어도 최솟값이 아니란걸 알 수 있습니다. 따라서 탐색하지 않고 종료하는것이 가지치기 입니다. * 설명을 위한 사진..

2020.04.13