동적계획과 이항계수

동적계획법

• 문제를 더 작은 문제로 분할 -> 상향식(Bottom - Up) 으로 문제 해결
• 재귀적으로 하향식(Top - Down)으로 푸는 분할정복과 대비
• 동적 계획법으로 문제를 풀기 위해서는 재귀적 정의(점화식)을 상향식으로 구성

이항계수 - 분할정복

위의 성질을 사용하여 코드를 구성

 

def binomial(n,k):
    if (k==0 or n==k):
        return 1
    else:
    	return binomial(n-1, k-1) + binomial(n-1, k)

하지만, 한 이항계수 값을 구하는데 있어서, 중복되는 계산이 여러번 발생하는 문제점(비용증가)이 있다.

출처 : https://at0z.tistory.com/28

따라서, 동적계획의 방법을 생각해 보아야 한다.

 

동적계획 - 이항계수

위의 식을 하향식(재귀) 가 아닌 상향식으로 변환

 

B : 이항계수 배열

def bin2(n, k):
    B = [[0]*(k+1) for _ in range(n+1)] // B[n][k] 인덱스에 접근하기 위하여
    for i in range(n+1):
        for j in range(min(i,k)+1):     
            // i < k 인 경우 i 보다 큰 k 값을 계산할 수 없음
            // i > k 인 경우 k 보다 큰 값을 구해도 답을 내는데 쓸모가 없음
            // 따라서 min(i,k) 값 까지 계산
            if (j==0 or j==i):
                B[i][j] = 1
            else:
                B[i][j] = B[i-1][j-1] + B[i-1][j]
    return B[n][k]

성능개선

위의 동적계획법을 활용한 코드의 성능을 개선해보자.

이항계수 성질에서

(n, k) = (n, n-k) 이므로, k가 n/2 보다 큰 값을 계산할 때에는 기존의 값을 활용하여 시간복잡도를 개선할 수 있다.

또한 2차원 배열이 아닌 1차원 배열을 사용하는 아이디어로 공간복잡도 또한 개선할 수 있다.

 

1차원 배열을 사용하는 아이디어는,

한번의 반복문을 도는것이 n이 증가하는 것이고 본래의 배열에 값을 다음 n의 값으로 채워넣는것이다. 

코드를 보면서 이해해보자.

 

def bin3(n, k):
    // 시간복잡도 개선
    if(k > n//2):
        k = n-k 
    
    B = [0] * (k+1)
    B[0] = 1
    for i in range(1, n+1):
    // 모든 이항계수를 구하는것이 아니라 k까지 (필요한만큼만) 계산
    j = min(i,k)
    while (j>0):
    	// 쉽게 말해서 배열의 오른쪽부터 업데이트 하는것이다.
        // 그 이유는 왼쪽부터 오른쪽으로 갈 경우 이미값이 다음 n 값으로 업데이트 되어 재사용할 수가 없기 때문
        // 반면 오른쪽부터 왼쪽으로 갈 경우 바뀐값을 참조할 수 없으므로 적절히 수행 가능
        B[j] = B[j] + B[j-1]
        j -= 1
    return B[k]