알고리즘 - 조합(Combination)

조합(Combination)

---

조합은 코딩 테스트에 자주 출제되는 주제이며 동적 계획법(DP)을 이해하는데 기초가 되는 부분이다.

조합 점화식 도출 방법에 대해 깊이 학습하면 조합은 물론 동적 계획법의 점화식 도출 부분에 많은 도움이 된다.

조합과 비슷한 순열을 비교하면 조합은 순서를 고려하지 않고, 순열은 순서를 고려한다는 부분이 다르다.

순열과 조합 비교

위 사진과 같이 순열은 순서를 고려하기 때문에 1,2,3과 3,2,1을 각각 다른 것으로 구분하지만, 조합은 순서를 고려하지 않기 때문에 두개 다 같은 것으로 생각한다.

순열과 조합 공식

왼쪽은 순열의 수학적 공식, 오른쪽은 조합의 수학적 공식이다. 다른 점으로는 조합은 순서를 고려하지 않기 때문에 r!를 추가하여 순서가 다를 경우의 수를 제거해준다.

조합의 공식을 살펴보면 n개의 숫자에서 r개를 뽑는 경우의 수를 의미한다.

 

조합 알고리즘의 핵심 사항

1. 특정 문제 가정하기

특정 문제

5개의 데이터 중 3개를 선택하는 문제가 있다고 가정하자.

 

2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기

부분 문제가 해결된 상황이라고 가정

위 사진과 같이 1~4번까지 선택이 완료된 숫자라고 가정하고 5번을 선택할지 안 할지 고려해본다.

선택이 완료된 데이터 중 2개를 선택하는 경우의 수는 ₄C₂가 되고 3개를 선택하는 경우의 수는 ₄C₃이 된다.

결과적으로, 5개중 3개를 선택하는 경우의 수는 ₄C₃ + ₄C₂을 해주면 된다.

 

3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기

일반화된 점화식을 이용하면 조합과 관련된 모든 경우의 수를 쉽게 구할 수 있다.

조합 점화식: D[i][j] = D[i - 1][j] + D[i - 1][j - 1]