IT

백트래킹(Backtracing)의 개요 백트래킹은 구하고자 하는 해를 튜플로 나타내고 튜플에 기준 함수(한정 함수)를 적용했을 때의 결과가 최대치, 최소치 혹은 일정 조건을 만족하게끔 만들어주는 퇴각 검색 기법으로 정의된다. 백트래킹은 해답이 될 수 있는 튜플을 완성해 나아가며 그 과정에서 미완성된 튜플에 한정 함수를 적용하여 해답의 가능성이 없는 튜플들은 더이상 진행시키지 않는 방법을 사용한다. 이때 튜플을 만드는 과정에서 스택(Stack)을 사용하여 한정 함수를 만족하면 push, 만족하지 않으면 pop을 하는 방법을 사용한다. 이런 과정이 퇴각과 전진하는 것과 비슷하다 하여 퇴각 검색 기법(백트래킹, backtracking)이라 불린다. 기준 함수(한정 함수, Bounding Function)의 사..