[알고리즘] 조합(Combination), 조합 점화식

🟡 조합(Combination)

- 조합은 nCr로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 의미

- 조합의 수학적 공식

nCr = n! / (n-r)! r!

- 조합은 '동적 계획법'의 시작, 알고리즘에서 조합을 구현할 때는 위의 수학 공식을 코드화하지 않고 점화식을 사용해 표현

 

 

🟡 조합 점화식

다음 3단계로 점화식을 세워보겠다.

 

① 특정 문제를 가정하기

서로 다른 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정

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

- 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정하고, 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다.

1) 만약 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면 선택이 완료됐다고 가정한 4개의 데이터에서 2개를 선택해야 함

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]

 

 

🟡 조합 점화식을 사용한 문제 풀이법

① DP 배열을 선언한다. (D[N+1][N+1])

② DP 배열 초기화

D[i][1] = i // i개 중 1개를 뽑는 경우는 i개
D[i][i] = 1 // i개 중 i개를 뽑는 경우는 1개
D[i][0] = 1 // i개 중 0개를 뽑는 경우는 1개

③ 점화식을 사용해 풀이한다.