[알고리즘] 백 트래킹 기법 이해하기

[백 트래킹 기법 이해 (BackTracking)] - 백트래킹 혹은 퇴각 검색으로 부르며, 제약 조건 만족 문제에서 해를 찾기 위한 전략이다. * 제약조건 만족 : 해를 찾기 위해 후보군에 제약 조건을 점진적 체크, 해당 후보군이 제약 조건을 만족할 수없다고 판단되면 즉시 backtrack으로 넘어가서 이 후보군을 탐색 후보군에서 완전 제외 시킴* 즉 가능성이 없는 후보군을 삭제한 후, 해당 후보군을 다시는 체크하지 않으며, 이를 통해 최적의 해를 찾는 방법이다. 행렬에서 각 행이 0,1,2,3... 과 같이 점진적 증가인 경우를 카운트해서 반환한다면,그 행의 맨 뒤까지 탐색할 때 점진적인 증가가 발생되지 않은 시점에서 해당 후보군을 제외시키고, 다른 탐색 후보군을 탐색하는 방법 또 퇴각 검색 기법 중..