[알고리즘] 되추적(Backtracking)을 알아보자.

오늘의 주제는 되추적(Backtracking) 이다. 저번 포스팅인 깊이우선탐색(Depth-First Search)과 넓이우선탐색(Breath-First Search)의 몸풀기를 거치고최단경로(Shortest Path) 알고리즘에 들어가는 첫 걸음이라고 생각하고 가벼운 마음으로 읽어보면 되겠다. 우선 되추적(Backtracking)이 뭔지부터 알아보자.『 퇴각검색(영어: backtracking, 한글: 백트래킹)은 한정 조건을 가진 문제를 풀려는 전략이다. "퇴각검색(backtrack)"이란 용어는 1950년대의 미국 수학자 D. H. 레머가 지었다. 문제가 한정 조건을 가진 경우 원소의 순서는 해결 방법과 무관하다. 이런 문제는 변수 집합으로 이뤄지는데, 한정 조건을 구성하려면 각각의 변수들은 값이 있..
Algorithm 2016. 2. 1. 22:01
1