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