조합인데 개수가 작으면 for문으로 가자.
- 5개 중에서 3개를 뽑아라.
뽑는 개수가 작으면 그냥 for문으로 바로 가자.
이때의 시작 복잡도는 위의 경우 v.size()의 3제곱이다.
언제 순열? 언제 조합? 251005
-
1) 조합의 경우
: 5명 사람 중에서 3개를 뽑아야할때 -
2) 순열의 겨우
: 5명 사람 중에서 3명을 뽑는데 , 순서에 상관 있는 조건이 붙은 경우,
// 예를 들면, 들어온 순서대로 번호표를 받는다.
-> 순열이다.
next_permutation 주의사항.
: 5개 중에서 3개를 뽑으라고 하는 경우, next_permutation 사용하면 안된다.
- 중복되는 수열이 나오는데 왜냐하면 5개를 가지고 섞고 있기 때문이다.
부분 순열에 대해서_251005
경우의 수 4가지를 알아보자.
- 반드시 숙지해야 함.
순열
-
순열이란 순서에 상관 있게 선택하는 경우이다.
-
1 2 3 4에서 3개를 뽑는다고 해보자.
123 / 124 / 132 / 134 / 142 / 143
213 / 214 / 231 / 234 / 241 / 243
312 / 314 / 321 / 324 / 341 / 342
412 / 413 / 421 / 423 / 431 / 432
- 이 때의 수식은 4! / (4 - 3)! 이다.
-> 총 24개다.
관련 문제 : n 과 m 1번
-
문제
-
코드
조합
-
조합이란 순서에 무관하게 동일한 경우, 를 나타내는 겨우이다.
-
1 2 3 4 에서 3개 뽑는 조합은
123 / 124 / 134
234 /
- 4c3 이고 이 때의 수식은
4! / 3! 이다.
-> 총 4개다.
관련 문제 : n과 m 2번
- 문제
- 코드
중복 순열
-
중복 순열이란 순서에 상관있게 중복되는 거를 뽑는거다.
-
1 2 3 4 중에서 3개를 뽑아보자.
111 112 113 114 123 124 134
- 이런식으로 매순간 4번을 선택하므로
-> 4 4 4의 시간복잡도를 가진다.
관련 문제 : n과 m 3번 문제
중복 조합
- 중복 조합이란, 중복을 하면서 순서에 관계 없이 동일한 거를 제외하는 거다.
관련문제 : n과 m 4번 문제
🔥🔥🔥