섹션 8. 조합(Combination)

자주 출제되는 유형인 그래프, DP, 인덱스트리 중 동적계획법(DP)를 이해하는데 도움이 된다.

조합 점화식 도출 방법을 잘 기억하자

 

조합(combination)은 nCr로 표현하고, n개의 숫자에서 r개를 뽑은 경우의 수를 뜻한다.

순열은 nPr로 표현되고, n개의 숫자중 r개를 뽑는 순서를 고려해 나열할 경우의 수를 이야기한다.

 

코딩 테스트에서는 순열보다 조합의 출제 빈도가 높고, 응요할 수 있는 문제도 많다.

조합은 순열과 비슷하게 분모에 r!만 추가되어 있는 것을 확인 할 수 있다. 순서가 다른 경우의 수를 제거하는 역할을 한다.

1. 특정 문제를 가정하기
2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기
3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기

조합 점화식

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