🍏순열과 조합
순열
순서를 고려하여 선택한 요소를 배열하는 경우의 수
5개중 3개를 선택하는 모든 순열의 수 =5P3
r개의 순열의 수는r!,n개에서r개를 뽑아 만드는 순열의 수는
n!/(n-r)!
-> 뽑을 것!/안뽑은 것!
코드로 표현한다면
중첩된 for문이 다 함께 arr[0]부터 시작
같은 인덱스가 한번에 나올시 제외
조합
순서를 고려하지 않고 요소를 선택하는 경우의 수
5장에서 3장을 선택하는 조합에서 모든 조합의 수 =5C3
이 값은 (n개에서 r개를 뽑아 만든 순열의 수)에 (r개의 순열의 수를 나눈것)
=nCr = (n!/n-r!)/r!
=n! /(r! * (n - r)!)
-> 뽑을 것/안뽑은 것!*뽑은 것!
코드로 표현한다면
각 중첩문이 i=0, j=i+1, k=j+1로 시
각각의 중첩문이 가져오는 인덱스가 중복 될수 없다
반복문으로 순열과 조합을 만들면 개수가 커질수록 반복문이 늘어남으로 비효율적이며 개수을 변수로 받았을 때 대응이 힘들어진다
팩토리얼(!)
n에서부터 1씩 감소하여 1까지의 모든 정수의 곱
(팩토리얼에서, 0! 과 1! 은 모두 1)
멱집합
주어진 집합의 모든 가능한 모양의 집합, 공집합을 포함
lgorithm with Math)🍎실전문제(Algorithm with Math)
🐇(중복순열)가위바위보
입력한 rounds의 판수동안 나올 수 있는 가위바위보 경우의 수를 구하는 문제
🐇(순열)새로운 치킨 소스 레시피
N가지의 재료 중 M가지를 사용하여 조합한 모든 경우의 수를 리턴하는 문제
전체 재료를 담은 int[]와 선택한 수 int값을 입력받는다
재료는 0과 1로 구성된 숫자로 항상 1로 시작
단, 0이 3개 이상인 재료는 상한 재료이기 때문에 사용할 수 없다
재료를 넣는 순서가 다르면 다른 조합이다
유효한 재료를 남기는 부분
순열 조합을 만드는 재귀함수 부분
🐇(조합)블랙잭은 지겨워
🐇(GCD) 빼빼로 데이
어 이렇게 푸는게 아니야?🐇(Advanced)(멱집합)집밥이 그리워
