[조합] 조합

✔ 조합

조합이란?

• n개의 숫자에서 r개를 뽑는 경우의 수
• nCr로 표현
• nCr = n! / (n - r)! * r! (이때, r!는 순서가 다른 경우의 수를 제거하여 같은 경우로 취급하기 위한 것)

순열이란?

• n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수
• nPr로 표현
• nPr = n! / (n - r)!

조합의 점화식

1. 특정 문제를 가정하기
   • 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정
2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기
   • 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정
   • 마지막 데이터의 선택 여부에 따른 경우의 수를 계산
     만약 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면 선택이 완료됐다고 가정한 4개의 데이터에서 2개를 선택,
     만약 마지막 데이터를 포함하지 않고 총 3개의 데이터를 선택하려면 이전 데이터 4개 중 3개를 선택
   • 두 가지 경우의 수를 합치면 데이터 5개 중 3개를 선택하는 경우의 수가 나오게 됨 (5C3 = 4C2 + 4C3)
   • 이를 통해 5개 중 3개를 선택하는 경우의 수 점화식을 구할 수 있게 됨 (D[5][3] = D[4][2] + D[4][3])
3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기
   • 위의 점화식을 이용하여 일반화된 조합 점화식을 구할 수 있게 됨 (D[i][j] = D[i - 1][j] + D[i - 1][j - 1])

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn