[실전 알고리즘] 백트래킹

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

 

 

연습문제 1- N과 M

[백준 15649] N과 M (1) - 백트래킹 (tistory.com)

 

연습문제 2- N-Queen

[백준 9663] N-Queen (tistory.com)

 

연습문제 3- 부분수열의 합

[백준 1182] 부분수열의 합 (tistory.com)

 

STL next_permutation

next_permutation - C++ Reference (cplusplus.com)

 

왼쪽 그림이 순열(순서 상관 있음) , 오른쪽 {0,1} 넣어서 구현하는게 조합(순서 상관 없음)

조합에서 5개에서 3개를 뽑는 문제라면 배열 a를 {0, 0, 0, 1, 1}로 두면 됨

 

 

출처

BaaaaaaaarkingDog | [실전 알고리즘] 0x0C강 - 백트래킹 (encrypted.gg)