10-1. 조합 알아보기

조합(combination)

• n개의 숫자에서 r개를 뽑는 경우의 수
  • nCr로 표현

순열(permutation)

• n개의 숫자 중 r개를 뽑아 ‘순서’를 고려해 나열할 경우의 수
  • nPr로 표현

순열과 조합의 핵심 이론

• 순열
  • nPr = $\frac{n!}{(n-r)!}$
• 조합
  • nCr = $\frac{n!}{(n-r)! r!}$
    • $r!$의 의미: 순서가 다른 경우의 수를 제거하는 역할
    • 알고리즘에서는 점화식을 사용해 표현

점화식 세우기

1. 특정 문제 가정하기

   • 5개의 데이터에서 3개를 선택하는 조합의 경우의 수

2. 모든 부분 문제가 해결된 상황이라고 가정 → 지금 문제 생각하기

   • 5개의 데이터 중 4개가 이미 선택 여부가 결정된 데이터라 가정

   • 이후 5번째 데이터의 선택 여부에 따른 경우의 수를 계산

     • 만약 5번째 데이터를 포함해 총 3개의 데이터를 선택하려면 선택이 완료됐다고 가정한 4개의 데이터에서 2개가 선택되어 있어야 함
     • 5번째 데이터를 포함하지 않고 총 3개의 데이터를 선택하려면 이전 데이터 4개 중 3개가 선택되어 있어야 함

     ⇒ 이후 이 2가지 경우의 수를 합쳐 데이터 5개 중 3개를 선택하는 경우의 수를 도출

     

   • 이를 점화식으로 표현하면 다음과 같음

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

3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기

   • 일반화된 점화식을 이용하여 조합과 관련된 모든 경우의 수를 쉽개 도출할 수 있음

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

문제 풀이

1. DP 테이블 초기화

   D[i][1] = i # i개 중 1개를 뽑는 경우의 수
   D[i][0] = 1 # i개 중 1개도 선택하지 않는 경우의 수는 1개
   D[i][i] = 1 # i개 중 i개를 선택하는 경우의 수는 1개
   

2. 점화식으로 DP 테이블 값 채우기

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

3. D[N][K] 값 출력