[Algorithm] 조합

순열과 조합

• 순열은 n개 중에 r개를 뽑아 순서를 고려해 나열하는 경우의 수로 $nPr$로 표현됩니다.

• 조합은 n개 중에 r개를 뽑는 경우의 수로 $nCr$로 표현됩니다.

  순열과 조합의 수학적 공식

  $nPr = n! / (n-r)!$
  $nCr = n! / (n-r)!r!$

• 조합 공식은 순열에서 분모에 $r!$만 추가된 것을 확인할 수 있습니다.

• 이는 순서만 다른 경우의 수를 제거하는 역할입니다.

  조합 점화식 도출하기

예를 들어 5개 중에 3개를 고르는 경우의 수를 구해봅시다.

• 모든 부분 문제가 해결되었고 5개 중에 4개가 선택 여부가 결정되었다고 가정해보면
• 5번째 데이터의 선택 여부에 따른 경우의 수를 계산합니다.
  • 만약 5번째 데이터를 선택한다면 4개 중에 2개를 선택하는 경우의 수와
  • 5번째 데이터를 선택하지 않는다면 4개 중에 3개를 선택하는 경우의 수가 있을 것 입니다.
• 위의 두 가지 경우의 수를 합한 것이 5개 중에 3개를 선택하는 경우의 수가 됩니다.

$D[5][3] = D[4][2] + D[4][3]$

이를 통해 일반 점화식을 도출해보면 $i$개 중에 $j$개를 뽑는 경우의 수는 다음과 같이 나타낼 수 있습니다.

$D[i][j] = D[i-1][j-1] + D[i-1][j]$