백트래킹
현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
- 제약 조건을 만족하는 문제를 해결하기 위해 쓰는 알고리즘
- 특정 조건을 만족하는 조합 알고리즘에 해당하는 모든 해를 찾는 문제
모든 경우의 수 중 조건에 위배되는 경우는 빼고 답을 찾는 것 - 답이 될 수 있는 모든 경우의 수를 DFS를 이용해 찾음
만약 답이 될 수 없는 경우면 더 이상 탐색하지 않고 이전으로 돌아감 - 재귀로 푸니까 스택 메모리 제한 확인해야됨
- 시간복잡도 O(N!) 개 오 래 걸 림
N이 클 경우 백트래킹을 적용하면 시간초과 남
12! = 479001600 = 4*10^8
백트래킹 코드는 이 틀 내에서 문제에 따라 적절히 응용해야함 (조합 코드)
인덱스 설정이나 탈출 조건은 문제에 따라 바꿔주면 되고
⭐ 상태변화 & 원상복구가 중요함 원래대로 복구하는거 빼먹지 않도록 주의
void backtracking(int cnt, int idx) {
if (cnt == m) {
//조건 만족시 해야될 일 적음
return;
}
for (int i = idx; i < n; i++) {
if (!visited[i]) {
visited[i] = true; //상태변화
backtracking(cnt + 1, i+1);
visited[i] = false; //원상복구
}
}
}
next_permutation
👨🏻🏫 C++한정 next_permutation함수 : 나중에 코딩테스트 문제들을 풀다보면 순열과 조합을 가지고 코딩 노가다가 빡세게 들어가는 것들을 보게 되는데
이런 문제들을 백트래킹으로 해결할 수 있지만 아무래도 백트래킹은 실수할 수 있는 여지가 있고 코드가 길어진다.
그런데 이 next_permutation함수만 있다면 아주 깔끔하게 순열과 조합을 해결 할 수 있다.
int main() {
vector<int> v{ 1, 2, 3, 4 };
do {
for (auto& i : v) cout << i << ' '; cout << '\n';
} while (next_permutation(v.begin(), v.end()));
}1,2,3을 가지고 만들 수 있는 모든 순열을 이렇게 쉽게 구할 수 있다.
⭐ std::next_permutation(st, en)은 (st, en) 범위의 값을 en - st칸짜리 순열로 볼 때 현재 순열의 바로 다음 순서의 순열로 (st, en) 범위를 채워주는 함수입니다. 만약 현재 순열이 가장 마지막 순열이라 다음 순열이 없다면 (st, en)은 처음 순열로 바뀌게 됩니다.
next_permutation은 현재의 수열을 사전 순으로 생각했을 때의 다음 수열도 만들고 true를 반환하는 함수다. 만약 현재의 수열이 사전 순으로 생각했을 때 제일 마지막이어서 다음 수열이 존재하지 않는다면 false를 반환한다. 그렇기때문에 do while문으로 작성하면 가능한 모든 순열을 탐색할 수 있다. 즉 이 경우 경우의 수는 **nPn** n개중에 n개를 뽑을때의 경우의 수와 같다.-> n!
📌 단,탐색을 시작하는 상태가 처음 순열이어야 하기 때문에 모든 순열을 탐색하기 위해선 처음에 순열을 정렬해줘야 한다.
만약 중복된 수가 있다고 해도 사진 순의 결과를 잘 돌려준다. 예를 들어 1 1 2에서 시작했다면 1 2 1 , 2 1 1 로 바뀌게 된다.
prev_permutation
next_permutation과 거의 동일한데 다음 순열 대신 이전 순열을 구해준다는 것만 다른 함수입니다.
int main() {
string s = "dcba";
do cout << s << '\n';
while (prev_permutation(s.begin(), s.end()));
}prev_permutation도 반환값이 bool이며 이전 순열이 존재했다면 1을, 아니라면 0을 반환합니다. 만약 현재 순열이 처음 순열이었다면 (st, en)은 마지막 순열로 바뀌게 됩니다.
함수의 이름에서 볼 수 있듯 이 함수를 가지고 순열(permutation)을 잘 처리할 수 있는데 만약 조합(combination)이 필요하다면 어떻게 해야할까?
iterating combination
int main() {
vector<int> P{ 1, 2, 3, 4 };
vector<int> v{ 1, 1, 1 ,0 };
do {
for (int i = 0; i < 4; i++) if (v[i]) cout << P[i] << ' ';
cout << '\n';
} while (prev_permutation(v.begin(), v.end()));
}permutation을 순회하는 것과 비슷하게 combination도 어렵지 않게 순회할 수 있습니다.
combination은 순서에 상관없이 수를 선택하는 것을 의미하며 여기선 선택하는 수의 개수 k가 고정일 때(=nCk)를 생각해보겠습니다. 예를 들어 P = { 1, 2, 3, 4 }, k = 3이라면 3개를 순서 없이 뽑는 모든 경우 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4) 이렇게 4개의 조합이 가능합니다.
0과 1을 이용해서 next_permutation을 돌리는 방법으로 해결한다. 5개에서 3개를 뽑는 문제라면 배열 a를 {0,0,0,1,1}로 두면 된다.
이건 v = { 0, 1, 1, 1 }과 같이 뒤쪽 k개의 원소를 1로 채운 순열을 만들어서 next_permutation을 사용하면 처리할 수 있습니다. 즉, v에 대한 permutation을 순회하며 v[i] = 1인 P[i]만 골라서 조합을 만들어주면 됩니다.
(next_permutation은 중복이 있는 순열에서도 잘 작동하며, 전체 연산량의 합은 중복이 없을 때보다 적습니다)
만약 combination을 사전순으로 순회하고 싶다면 v = { 1, 1, 1, 0 }에서 시작해서 prev_permutation을 돌리거나 0, 1을 뒤집어서 { 0, 0, 0, 1 }부터 next_permutation을 돌려주면 됩니다.
+) 뒤쪽 m개의 원소가 1로, 나머지 원소는 0으로 구성된 n칸짜리 배열 v를 만들 때는 vector<int> v(n)에 fill(v.end() - m, v.end(), 1)을 사용하면 편리합니다. fill(st, en, val) 함수는 (st, en-1) 범위를 val로 채워주는 함수입니다.
※ vector의 end()는 마지막 다음 위치를 가리킨다.
boj15649번 N과 M(1)이 전형적인 백트래킹 구조.
👨🏻🏫 사실 N과 M 시리즈는 next_permutation을 이용하거나, 재귀함수를 이용해 백트래킹으로 구현하는 두 가지 풀이가 존재합니다. next_permutation은 재귀함수를 이용하지 않아서 구현이 편리하고, 백트래킹은 직접 다음 순열을 생성하지 않아서 더 빠르다는 장점이 있습니다.
앞으로 가능한 모든 순열, 조합을 탐색하는 문제가 자주 등장할 텐데, 상황에 맞게 두 방법 중 하나를 사용할 수 있도록 숙지해두시면 좋을 거 같습니다. 저는 보통 단순 순열, 조합을 필요로 하면서 효율성을 고려하지 않아도 되는 문제라면 next_permutation을 사용하고, 중복 순열, 중복 조합 등을 필요로 하거나 시간 최적화가 필요한 문제는 백트래킹으로 처리합니다.
순열(JAVA)
n개 중에 중복이 허용되지 않도록 r개를 뽑아서 일렬로 세우는 경우의 수
-> 중복X , 순서 고려O
package ky_0720;
public class permutation {
public static void main(String[] args) {
int n = 3;
int[] arr = {1,2,3};
int[] output = new int[n]; //n개 뽑음 -> nPn -> n!
boolean[] visited = new boolean[n];
perm(arr, output, visited, 0, n, 3);
//배열, 뽑아낼 원소들 배열, 방문 배열, depth, n, r)
//이미 들어간 값은 visited 값을 true로 바꾸어 중복하여 넣지 않도록 합니다.
//depth 값은 output에 들어간 숫자의 길이라고 생각하면 된다.
//depth의 값이 r만큼 되면 output에 들어있는 값을 출력.
}
//사전순으로 순열 구하기
static public void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
if(depth == r) {
print(output, r);
return;
}
else {
for(int i = 0; i < n; i ++) {
if(visited[i] == false) {
visited[i] = true; //방문 체크
output[depth] = arr[i]; //depth가 output의 인덱스 역할을한다.
perm(arr, output, visited, depth + 1, n, r);
visited[i] = false;//원상복귀 중요!
}
}
}
}
static void print(int[] arr, int r ) {
for(int i = 0 ; i < r; i++) System.out.print(arr[i] + " ");
System.out.println();
}
}
조합 (JAVA)
n개 중에 중복을 허용하지 않고 순서를 고려하지 않으면서 r개를 뽑는 경우의 수
-> 중복X, 순서 고려X
암기해두는 것이 좋다.
s는 시작하는 값으로 반복되는 원소가 나오지 않도록 한다.
원소가 중복이 안되면서 순서 또한 고려하지 않기 때문에 한번 뽑은 위치의 원소는 다시는 나오지 않도록 시작 인덱스를 하나씩 올려면서 재귀를 호출한다. 이런 식으로 재귀를 돌게 되면 같은 원소가 중복이 되지 않도록 방문 배열을 만들어서 방문 체크를 하지 않아도 되고 동시에 순서만 다른 같은 원소들로 이루어진 경우의 수가 나오지 않는다.
import java.util.*;
class Main {
static int n, m;
static int[] combi;
public void DFS(int L, int s) { //s는 스타트하는 값
if (L == m) {
for(int x : combi) System.out.print(x + " ");
System.out.println();
}
else{
for (int i = s; i <= n; i++) {
combi[L] = i;
DFS(L + 1, i + 1);//원소가 중복이 안되면서 순서 또한 고려하지 않기 때문에 한번 뽑은 위치의 원소는 다시는 나오지 않도록 시작 인덱스를 하나씩 올려준다.
}
}
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
n = kb.nextInt();
m = kb.nextInt();
combi = new int[m]; //조합을 저장할 배열
T.DFS(0, 1); //조합의 원소는 1부터 시작
}
}부분집합(Power Set)
⭐⭐ 전체중에 몇개를 뽑는 것이 정해져있지 않는 경우, 부분집합으로 문제를 푼다
해당 원소가 포함되는 경우 / 포함되지 않는 경우를 모두 탐색.
부분 집합은 집합의 원소 일부로 이루어진 집합을 의미하며, 자기 자신도 부분집합이 될 수 있으며, 원소가 전혀 없는 공집합(∅)도 부분집합이다.
그렇기 때문에, 각각의 원소를 선택하는 경우, 선택하지 않는 경우 두 가지의 경우로 나뉘며 전체 Big-O 시간은 O(2^n)이 된다.
조합과 다른점은, 조합은 r개를 선택하는 경우의 수 이지만, 부분집합은 선택하는 수가 0~n까지 다양하기 때문에 원본 배열을 모두 돌아보면 고른것들을 그대로 출력한다.
즉, n개로 만들 수 있는 가능한 모든 조합들의 경우의 수의 합이다. ex) 3C3 + 3C2 + 3C1 + 3C0
-> 중복X, 순서 고려X
그래서 아래 예제와 같이 select배열을 써서 따로 저장해도 되지만, boolean[] 배열을 통해 선택 여부만 체크하고 넘어가서 배열의 원소가 true일 경우에 결과배열에 넣어도 된다.
입력 : [1, 2, 3]
출력 : [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]
public static void subset(int[] arr, int idx, int[] select, int sidx) {
// r개를 고르지 않아도, 원본 배열을 모두 돌았으면 출력
if (idx == arr.length) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < sidx; i++) {
list.add(select[i]);
}
System.out.println(list);
return;
}
subset(arr, idx + 1, select, sidx);
select[sidx] = arr[idx];
subset(arr, idx + 1, select, sidx + 1);
}중복 순열
⭐⭐ 중복순열: 서로 다른 n개중 중복을 허용하여 r개를 일렬로 나열하는 경우의 수 -> 각 사건의 경우의 수^사건의 횟수 -> n^r
-> 중복O, 순서 고려O
ex) (1,1) (1,2) (2,1) (2,2)
- 몇 번의 사건이 발생하는지 보면, cctv가 방향을 정하는 사건이 몇번 일어날까? cctv의 개수만큼 사건이 발생한다. 그리고 각각의 사건당 4방향이니까 4가지의 경우의 수가 있다. cctv의 개수가 3대라면 444= 4^3 =64가지다. 최대 8대라면 4^8 = 6만정도 나와서 완전탐색을 쓸 수 있다.
- 즉, 4방향^cctv의 개수다. -> 각 사건의 경우의 수^사건의 횟수.
따라서 순열에서 중복을 제거하기 위해 사용했던 vis배열로 방문 체크하는 과정이 없다. 중복 순열 문제에서 방문체크를 한다면 그건 중복 순열과 별개로 가지치기를 하는 과정이다.
같은 것이 있는 순열
순열이 같은 것이 포함된 원소들을 나열하는 경우의 수는 나열하는 원소의 팩토리얼에 중복된 원소들의 팩토리얼을 나누어주면 됩니다.
예를 들어 aaabb와 같은 경우 a가 3개이고 b가 2개이므로 5!을 3!와 2!로 나누어주면 됩니다.
⭐ SWEA 숫자만들기 문제 풀이 참고
참고 : 바킹독 0x0C
순열조합
jinhan블로그
https://hanbi97.tistory.com/115
https://bcp0109.tistory.com/14
https://velog.io/@albaneo0724/Algorithm%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EB%B6%80%EB%B6%84-%EC%A7%91%ED%95%A9#%EB%B6%80%EB%B6%84-%EC%A7%91%ED%95%A9power-set
https://coding-factory.tistory.com/606
