[D-6] 조합

📍 조합

코딩 테스트에서 자주 출제되는 주제이다.
동적 계획법을 이해하는데 기초가 되는 매우 중요한 장이다.
조합 점화식 도출 방법에 대해 꼼꼼히 학습하는 것을 추천한다.

✅ 정의

조합(combination)은 n​Cr​로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다.
순서를 고려하지 않는다.

✅ 조합의 점화식

1. 특정 문제를 가정하기

• 적당한 조합 문제를 가정한다.
• 5개의 데이터에서 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]​

📍 순열

✅ 정의

순열은 n​Pr로 표현하고, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 뜻한다.