조합의 정의 조합은 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 말한다. 앞서 살펴본 순열과의 차이점은 순서를 고려하지 않는다는 점이다. 수학적 증명을 통한 조합 구하기 순열이 nPr = n개에서 r개를 선택한 후 순서대로 나열하는 것인데 여기서 n개에서 r개를 선택하는 것이 순열이고 이 r개를 다시 나열하는 것이 nPr이다. 따라서 nCr은 다음과 같이 구할 수 있다. 위 식을 처리하기 쉬운 재귀 방식으로 변경해보자. 위 식을 잘 살펴보면 nCr은 보다 낮은 단계인 n-1Cr-1과 n-1Cr의 합이다. 여기서 r이 선택할 요소의 개수이다. 즉 n개에서 r개를 뽑는 방법은 어떤 요소 하나를 고려했을 때 그 요소를 뽑았을 때의 조합과 그 요소를 뽑지 않았을 때의 조합의 합이된다. 조합의 과정 ..
[조합]01. 조합의 구현
조합의 정의 조합은 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 말한다. 앞서 살펴본 순열과의 차이점은 순서를 고려하지 않는다는 점이다. 수학적 증명을 통한 조합 구하기 순열이 nPr = n개에서 r개를 선택한 후 순서대로 나열하는 것인데 여기서 n개에서 r개를 선택하는 것이 순열이고 이 r개를 다시 나열하는 것이 nPr이다. 따라서 nCr은 다음과 같이 구할 수 있다. 위 식을 처리하기 쉬운 재귀 방식으로 변경해보자. 위 식을 잘 살펴보면 nCr은 보다 낮은 단계인 n-1Cr-1과 n-1Cr의 합이다. 여기서 r이 선택할 요소의 개수이다. 즉 n개에서 r개를 뽑는 방법은 어떤 요소 하나를 고려했을 때 그 요소를 뽑았을 때의 조합과 그 요소를 뽑지 않았을 때의 조합의 합이된다. 조합의 과정 ..
2022.07.10