오늘은 코딩테스트에 자주 등장하는 기본 개념으로 조합을 알아보자. 사실 조합으로만 푸는 문제가 나오진 않지만, 가장 빈출되는 동적 계획법을 풀이하기 위해선 조합에 대한 이해를 기반으로 점화식을 도출하는 연습은 필수라고 할 수 있다.
조합과 대비되는 개념으로는 순열이 있는데 이는 가볍게 개념만 인지하고 넘어가자
- 조합 : nCr = n!/(n-r)! -> n개의 수 중에서 r개의 수를 순서를 고려하여 나열할 경우의 수
- 순열 : nPr - n!/(n-r)!r! -> n개의 수 중에서 r개의 수를 순서를 고려하지 않고 뽑는 경우의 수
알고리즘에서는 위의 수학적 점화식을 코드ㄹ화하지 않고 점화식을 사용해 표현한다.
1. 특정 문제를 가정하기
먼저 가벼운 조합 문제를 가정해보자. 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 구해보자.
수학적인 점화식을 사용하면 5C3으로 10인 것을 가볍게 알 수 있지만, 컴퓨터에게 계산을 시키려면 어떻게 해야할까?
2. 모든 부분 문제가 해결된 상황이라고 가정하고 현재의 문제를 생각하기
모든 부분 문제가 해결된 상황이라고 가정해보자.
먼저 5개의 데이터 중에서 4개의 데이터는 선택이 완료된 데이터라고 가정을 해보자.
그리고 마지막 하나 남은 데이터를 선택하느냐 안하느냐의 여부에 따른 경우의 수를 계산한다.
즉, 쉽게 생각하면 5개 중 3개의 숫자를 뽑아야 하는데, 4개의 숫자를 제외하고 하나의 숫자만을 바라보면서 이 숫자를 선택할 것인지 아닌지만을 생각해보자는 이야기다. 이를 위해 모든 부분 문제가 해결된 상황이라는 가정이 필수적이다.
1. 만약 마지막 한개의 숫자를 선택한다고 하면, 처음에 배제해둔 4개의 숫자 중에서 2개의 숫자를 고르는 경우의 수를 구한다.
2. 만약 마지막 한개의 숫자를 선택하지 않는다고 하면, 처음에 배제해둔 4개의 숫자 중에서 3개의 숫자를 고르는 경우의 수를 구한다.
1과 2의 경우의 수를 구하면 5개의 수중에서 3개를 선택하는 경우의 수가 나오게 된다.
말로만 들으면 되게 복잡하지만, 사실 이러한 논리 또한 수학적 이론인 파스칼 삼각형에서 도출된 것이다.
3. 특정 문제를 해결한 내용을 바탕으로 보편적인 점화식 도출하기
가장 처음에 설명한 표현식과 가정, 그리고 위의 이미지를 기반으로 조합을 풀이하기 위한 점화식을 세우면 아래와 같다.
수학적 점화식 : nCr = n-1Cr + n-1Cr-1
컴퓨터 점화식 : DP[N][K] = DP[N-1][K] + DP[N-1][K-1]
'알고리즘 > 문제 풀이 비법' 카테고리의 다른 글
| Do it! 코딩테스트-기초편. 3_자료구조 (0) | 2023.03.13 |
|---|---|
| 알고리즘 선택의 기준_시간복잡도 (0) | 2023.03.06 |
| 최소공통조상 (0) | 2022.10.26 |
| 트리 (0) | 2022.09.21 |
| 완전 탐색(Brute Force) (0) | 2022.06.17 |
