[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용
  : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0C강 - 백트래킹'
  : 'Jinhan's Note' 중 'Theme 07. 백트래킹(Backtracking)'

1. 백트랙킹(Backtracking)
2. STL next_permutation
3. Q&A
4. 마치며

1. 백트랙킹(Backtracking)

• 백트랙킹(Backtracking)
  : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

(예제는, '바킹독님 블로그' 참조)

1) 가지 치기(pruning)

재귀 호출을 트리 구조로 생각했을 때,
가지치기는 트리 edge를 끊어서 해당 subtree는 탐색하지 않는 것을 의미.

1. naive한 재귀 풀이를 생각

2. 현재 상태에서 정답을 갱신할 수 있는지 확인하는 로직

3. 가지치기를 적용해 더 효율적으로 해결

2. STL next_permutation

int a[3] = {1, 2, 3};
do{
	for(int i = 0; i < 3; i++)
    	cout << a[i];
    cout << '\n';
}while(next_permutation(a, a+3));
/*
123
132
213
231
312
321
*/

next_permutation은 현재의 수열을 사전 순으로 생각했을 때의, 다음 수열을 만들고 true를 반환하는 함수.

만약 다음 수열이 존재하지 않으면 false를 반환.

따라서 do-while문을 이용하면 코드가 깔끔해짐.

조합을 구할 때는, 원래의 수열에서 0과 1을 이용하면 구할 수 있음
위의 예시에서, 3개 중 2개를 뽑는다고 하면
배열 a를 {0,1,1}처럼 두면 됨.

3. Q&A

-

4. 마치며

-

[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.

• 전반적 내용
  : '바킹독'님의 블로그 중 '[실전 알고리즘] 0x0C강 - 백트래킹'
  : 'Jinhan's Note' 중 'Theme 07. 백트래킹(Backtracking)'