조합

조합

조합은 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다. 조합과 비교되는 순열은 n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 이야기한다. 순열과 조합의 차이는 순서의 고려 유무이다. 조합은 실제 알고리즘 코딩 테스트에서 순열보다 조합의 출제 빈도수가 높고, 응용할 문제도 많다. 조합은 동적 계획법의 시작이라고 볼 수 있다. 따라서 알고리즘에서 조합을 구현할 때는 수학 공식을 코드화하지 않고 점화식을 사용해 표현한다.

 

조합의 점화식

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]

조합 점화식

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

점화식이 간단하므로 외울 수도 있지만, 원리를 정확하게 이해하는 것이 문제 응용하기 유리하다.