알고리즘 스터디 20일차

목차

1. 조합 핵심 이론

2. 조합 실전 문제

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

 

1. 조합 핵심 이론

조합 점화식은 DP(동적계획법)을 이용하는데 중요하다.

문제를 접근할 때 모든 부분 문제가  해결된 상황이라고 가정하고 지금 문제를 생각해야 한다.

무슨말이냐면 예를들어 5개중에 3개를 선택해야하는 조합문제에서 (데이터 1 2 3 4 5) 5를 선택해야 하는 경우의 수를 구한다. 단, 이때 나머지 데이터 1 2 3 4 에 대한 문제는 해결된 상황이라고 가정한다.

그럼 5를 선택하는경우와 선택하지 않는 경우로 나눌수 있고 두 경우는 각각 [이미 4개중 2개를 선택한경우]와 [이미 4개중 3개를 선택한경우]이다.

위의 내용을 점화식으로 나타내면 다음과 같다.

D[5][3] = D[4][2] + D[4][3]   (5개중 3개를 선택하는 경우의 수는 4개중 2개를 선택하는 경우의 수 + 4개중 3개를 선택하는 경우의 수) 이것은 수학적으로 접근해도 10 = 6 + 4 이기 때문에 성립한다.

즉, 조합 점화식은 D[i][j] = D[i-1][j] + D[i-1][j-1] 이다.

 

2. 조합 실전 문제

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

문제 풀이

import sys
input = sys.stdin.readline
N,K = map(int,input().split())
D = [[0 for j in range(N+1)] for i in range(N+1)]

for i in range(0,N+1):
    D[i][1] = i
    D[i][0] = 1
    D[i][i] = 1

for i in range(2,N+1):
    for j in range(1,i):
        D[i][j] = D[i-1][j] + D[i-1][j-1]
        D[i][j] = D[i][j] % 10007

print(D[N][K])

 

 

조합은 강의에서 설명하듯 동적계획법을 위한 단계정도로 보는것이 맞지만 위의 조합점화식만 알고있다면 조합문제에서는 무적이라고 생각한다. 이래서 알고리즘 공부를 하는구나 느낄 정도로 조합문제에 있어서 머리 아프게 구하지 말고 그냥 조합점화식에 대입하여 문제를 풀자.