251004 추가 예정.
순열
: 중복되지 순서로 나타내는 수열.
- 중복되는 숫자해도 되고, 수열이 중복되지 않는다.
추가 250826
https://velog.io/@kwt0124/%EC%88%9C%EC%97%B4
- 영백트래킹 vs 인덱스 백트래킹
-
영백트래킹은 순열이고, 중복이지만 순서가 다르다.
-
인덱스 백트래킹은 조합이고, 중복을 처리한다.
-
즉 경우의 수를 만들때
중복이 없어야 한다면 인덱스 백트래킹을 사용하고,
중복이 있더라도 순서에 변화가 있다면 영백트래킹을 사용하자.
인덱스 백트래킹. - 조합.
- 아래 실행 결과를 보면, 중복이 없다.
영 백트래킹 - 순열
- 숫자에 대한 중복이 있지만, 순서는 뒤죽박죽이다.
새롭게 추가.
순열 : next_permutation
-
시간복잡도는 n! 이다.
-
반드시 정렬해야 한다.
-
주의할 점으로는 next_permutation 사용하면서 조합으로 하기에는 시간복잡도가 많이 소요된다. 어쨋든 do~while 돌려야 한다.
-> 즉 조합 문제는 인덱스 백트래킹으로 접근해야 한다.
- 시간복잡도 : nPr = n! / (n-r)!
결론
: next_permutation 사용하려고 할 때, n! 의 시간복잡도를 먼저 생각하자.
- 15658 연산자 끼워넣기 2에서 잘못생각해서 순열로 생각했는데,
이때 시간복잡도는 40! 이므로, next_permutation 사용하면 안된다.
조합
- 시간복잡도 : nCr = n! / (n-r)! * r!
순열과 조합
1,2,3 을 순열과 조합으로 3개 뽑아서 나타내라.
-
순열
-> 123 / 132 / 213 / 231 / 312 / 321
-> 시간 복잡도 3P3 -> (3!) / (3-3)! -> 3! -> 6 -
조합 : 순서를 유지해야 한다.
-> 123 끝
-> 시간복잡도 3C3 -> (3!) / (3-3)! * 3! -> 1
🔥🔥🔥