backtracking (1) 썸네일형 리스트형 Algorithm&DataStructure - Backtracking 1. Backtracking - 모든 경우의 수를 고려하는 트리탐색 알고리즘이다. - 탐색중 현재 경로가 유망하지 않다면 가지치키를 할 수 있다. - 유망하지 않다 = 더 이상 탐색할 필요가 없다. 2. 백준 15649번 - 1부터 n 까지의 자연수 중 서로 다른 m개를 골라 줄세우는 경우들을 구한다. (nPm) - m에 따라서 경우의 수 tree가 만들어진다. - 이 트리에 대해서 깊이 우선의 탐색을 수행하는데 조건에 따라 탐색을 중지할 수 있다. - 이미 m개를 골랐다면 더 이상 깊이 트리를 탐색할 필요가 없으니 종료 조건에서 가지치를 하는 것이다. void backtracking(int count = 0) { if(count == m) { for(int i =0; i 이전 1 다음
