조합 알아보기
- 조합은 nCr로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다. 조합과 비교되는 순열은 nPr로 표현되고, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 이야기 합니다. 순열과 조합의 차이는 순서의 고려 유무이다. 즉, 조합에서는 데이터 1, 2, 3과 3, 2, 1를 같은 경우로 판단하고, 순열은 다른 경우로 판단한다.
✅ 순열과 조합의 핵심 이론
- 순열의 수학적 공식은 위와 같다. 예를 들어 5개 중 2개를 순서대로 선택하는 경우의 수를 구한다고 가정해보면 1번째 선택은 5개 데이터를 선택할 수 있으므로 5가지를 선택할 수 있고, 2번째 선택은 1번째에서 선택한 데이터를 제외한 4가지를 선택할 수 있다. 따라서 5개 중 2개를 고르는 경우의 수는 총 5 * 4 = 20가지가 된다.
- 조합의 수학적 공식은 위와 같다. 순열과 매우 비슷하며 분모에 r!만 추가돼 있는 것을 확인할 수 있다. r!은 순서가 다른 경우의 수를 제거하는 역할을 한다. 예를 들어 5개 중 2개를 서낵하는 경우의 수를 구한다고 가정하면 기존 순열의 경우의 수에 2!로 나눠 5 * 4 / 2 = 10가지 경우의 수를 도출한다. 즉, 1과 2를 선택할 때와 2와 1을 선택할 때를 1가지 경우의 수로 만들기 위해 2로 나누는 것이다.
- 일반적으로 조합은 뒤에서 배우는 ‘동적 계획법’의 시작이라고 볼 수 있다. 따라서 알고리즘에서 조합을 구현할 때는 위의 수학 공식을 코드화 하지 않고 점화식을 사용해 표현한다.
점화식 3단계
- 특정 문제를 가정하기
- 예를 들어, 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 구하는 문제가 있다.
- 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기
- 모든 부분 문제가 해결된 상황이라고 가정하자. 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정한다. 그리고 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다. 만약 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면 선택이 완료됐다고 가정한 4개의 데이터에서 2개를 선택해야 한다. 마지막 데이터를 포함하지 않고 총 3개의 데이터를 선택하려면 이전 데이터 4개 중 3개를 선택해야 한다. 2가지 경우의 수를 합치면 데이터 5개 중 3개를 선택하는 경우의 수가 나온다.
5개 중 3개를 선택하는 경우의 수 점화식
D[5][3] = D[4][2] + D[4][3]