조합

[C++] 조합 (Combination) 구할 수 있는 알고리즘

개념n개의 값 중에서 r 개의 숫자의 순서를 고려하지 않고 나열한 경우의 수, 순열은 반대로 고려한다. 예시) [1,2] 와 [2,1] 이 있을 때 동일하게 여긴다는 의미계산식으로는 nCr 이라고 표현한다.nCr= nPr / r!= n! / ((n-r)! * r!)예시로 서로 다른 3개의 숫자(1,2,3) 중 중복되지 않으면서 순서와 관계 없이 2개를 뽑는다고 가정해보자3C2= 3! / 1! * 2!= 3! / 2!= (3x2x1) / (2x1)= 3로 총 3개의 경우의 수가 나오게 된다 (1,2 / 1,3 / 2,3) 조합의 점화식 n-1Cr-1 + n-1Crn-1Cr-1 : 어떤 특정한 원소를 포함시키고 뽑았을 때n-1Cr : 어떤 특정한 원소를 포함시키지 않고 뽑았을 때예시){1,2,3} 에서 3C..

[알고리즘] 순열과 조합의 차이

순열과 조합의 가장 큰 차이는 순서가 있고 없고 이다. 예를 들어 자전거의 번호가 있는 자물쇠를 연다고 가정해보자. 자물쇠 번호가 1234라고 한다면 순서에 대한 고려 없이 4321을 입력하면 자물쇠는 열리지 않는다. 이를 순열이라고 한다. (순서가 있음) 또 다른 예시로 닭가슴살 샐러드를 가정해보자. 닭가슴살 샐러드의 재료는 닭가슴살, 양상추, 소스, 토마토라고 한다면 우리는 샐러드를 담을 때 닭가슴살을 처음으로 넣고 두 번째는 양상추... 이런 식으로 넣지 않고 그냥 재료에 맞게 넣는다. 이를 조합이라고 한다. (순서가 없음) 이제 수학적으로 다가가 보자 1 2 3 4 배열이 있고 2가지 경우를 뽑는다고 가정해보자 순열의 경우에는 순서가 중요하기에 하기와 같이 다 뽑아 버린다. 1 2 1 3 1 4 ..

[수학] 순열, 조합 공식 총 정리

팩토리얼 (!) 서로 다른 n개를 나열하는 경우의 수를 의미한다. 기호로는 n! 으로 표기하고 계산은 n부터 1씩 줄여나가면서 1일 될 때까지의 모든 수를 곱한다. 순열 (nPr) 서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음) 조합 (nCr) 서로 다른 n개 중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음) 중복 순열 (n​πr) 중복 가능한 n개 중에서 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음) 중복 조합 (nHr) 중복 가능한 n개 중에서 r개를 선택하는 경우의 수를 의미한다. (순서 상관 없음) 같은 것이 있는 순열 나열하는 원소의 팩토리얼에 중복된 원소들의 팩토리얼을 나누어주면 된다. 원 순열 원 모양의 테이블에 n개의 원소를 나열하..