처음 백트래킹을 공부했을 때, 이 백트래킹 유형 풀이에 대한 글을 썼다. 그런데 순조부(순열,조합,부분집합)라는 유형이 있다는 것을 알게 됐는데, 백트래킹 문제와 풀이가 거의 유사했다. 그 이유는 사실 모두 브루트포스 유형 즉, 모든 경우의 수를 찾아보는 완전탐색 유형으로 묶어지기 때문이었다.
그래서, 이 문제 유형들을 다시 구분해서 각 특징을 정리해보았다.
순열 및 백트래킹
핵심로직 : 일반적인 백트래킹 처럼 for문 돌며 isUsed배열 사용
검사 타이밍 : n개까지 뽑았을 때(모든 원소를 뽑았을 때)
리턴 타이밍 : n개까지 뽑았을 때(모든 원소를 뽑았을 때)
ex) int arr[] = {1, 2, 3}
1 2 3, 1 3 2
2 1 3, 2 3 1
3 1 2, 3 2 1
문제 예시 : 백준15649 N과 M(1) 풀이
부분집합
핵심로직 : 각 스택프레임에서 현재 원소를 포함하고 실행, 포함하지 않고 실행, (for문 사용 X)
검사 타이밍 : 함수호출마다 검사 (모든 갯수에 대해 검사함 _1개 뽑았을때 검사, 2뽑았을때 검사, ... n개 뽑았을때 검사)
리턴 타이밍 : n개까지 뽑았을 때 (모든 원소를 뽑았을 때)
(정확하게는 마지막 원소까지 탐색했을 때 _depth가 n일 때)
ex) int arr[] = {1, 2, 3}
1, 1 2, 1 2 3, 2, 2 3, 3
// <- 다시 2부터 시작할 필요 없음(for문 필요x), 2가 들어간 조합도 첫번재에서 다 나왔기 때문
문제 예시 : 백준2961 도영이가 만든 맛있는 음식 풀이
주의 : 백준1182 부분수열의 합과 같은 문제에서는, 검사 타이밍이 depth가 n개까지 갔을 때이다. 왜냐하면 depth가 n개에 다다랐을 때, 검사할 부분수열이 완성되었다고 할 수 있기 때문. (일부 숫자가 포함이 되었던 안되었던)
중간에서 검사하면 곤란하다. (출력해보면 왜 인지 대충 알 듯)
도영이가 만든 맛있는 음식은 중간에서 검사해도 상관없다. 이 부분수열의 합 문제가 각 부분수열들을 마지막에(depth==n) 완성한 후 검사해야 하는 특별한 케이스이다.
자세한 이유는 다음 참고 : ChatGPT - 왜 "도영이가 만든 맛있는 음식"문제에서는 중간에 검사가능한데, "부분수열의 합"문제에서는 depth가 n일 때 검사해야 하는가 (거의 마지막부분 참고)
조합
핵심로직 : 부분집합처럼 각 스택프레임에서 포함하고 실행, 포함하지 않고 실행
검사 타이밍 : 특정 갯수를 뽑았을 때 검사
리턴 타이밍 : 특정 갯수까지 뽑았을 때, n개까지 뽑았을 때(모든 원소를 뽑았을 때)(또는 마지막 원소까지 탐색했을 때)
ex) int arr[] = {1, 2, 3}
1 2, 1 3, 2 3
// <- 부분집합과 마찬가지로 다시 2부터 시작할 필요 없음
문제 예시 : 백준2798 블랙잭 풀이
