동적 계획과 이항 계수

수식 깨진 것들은 자체 검색으로 보완할 것

  • 동적계획법(Dynamic Programming): 문제를 더 작은 문제로 분할하되 상향식으로 문제를 해결

  • 메모이제이션(Memoization): 가장 작은 입력 사례의 해답을 테이블에 저장하고 필요할 때 꺼내 쓴다

  • 동적계획법으로 문제 풀기

    1. 문제를 해결할 수 있는 재귀 관계식(점화식)을 구한다
    2. 가장 작은 입력사례로부터 상향식 방법으로 문제를 해결한다

  • 분할 정복법 vs 동적 계획법

    • 문제를 작은 사례로 분할하여 해결한다는 점에서 동일
    • Top-Down vs Bottom-Up

  • 이항 계수

    • $\binom{n}{k} = \frac{n!}{k!(n-k)!}$, for $0 \le k \le n$
    • $\ n!, k!$의 값은 매우 커서 계산이 어렵다
    • 이항 계수의 재귀적 정의: 분할 정복
    • $\binom{n}{k} = \begin{cases}\binom{n-1}{k-1} + \binom{n-1}{k-1}&0<k<n\{1}&k=0||k=n\end{cases}$

파이썬으로 이항 계수의 재귀적 정의

1
2
3
4
5
6
7
8
9
10
def bin (n, k):
    if (k == 0 or n == k):
        return 1
    else:
        return bin(n - 1, k - 1) + bin(n -1, k)
# 함수 결과를 n = 10까지 출력
for n in range(10):
    for k in range(n + 1):
        print(bin(n, k), end = " ")
    print()

자바스크립트

1
2
3
function bin(n, k) {
    return (k == 0 || k == n) ? 1 : bin(n - 1, k - 1) + bin(n - 1, k);
}

$0 \le k \le n$에 의해 $k$는 $n$보다 큰 값일 수 없다

  • 이 방식은 중복 호출이 생김 → 반복적 방법이 요구됨
  • 이항 계수의 성질: 파스칼의 삼각형
  • 이항 계수 구하기
    1. 재귀 관계식을 찾는다
      $$B[i][j] = \begin{cases}B[i-1][j-1]+B[i-1][j]&0<j<i\1&j=0orj=i\end{cases}$$
    2. 상향식 방법으로 해답을 구한다
      • 파스칼의 삼각형이 가진 특성을 이용한다

파이썬으로 파스칼의 삼각형 구하기

1
2
3
4
5
6
7
8
9
10
def bin2 (n,k):
    B = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            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]
# 출력은 bin(n,k)와 동일

자바스크립트로 파스칼의 삼각형 구하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function bin2(n) {
    let result = []; // 빈 배열을 선언
    for (let row = 1; row <= n; row++) {
        // 행 수 만큼 for 루프
        let arr = [];
        // 추가할 새 배열을 선언 (루프 돌면서 초기화됨)
        for (let col = 0; col < row; col++) {
            if (col === 0 || col === row - 1) 
                // 파스칼의 삼각형에서 처음과 맨 마지막 숫자는 1로 채운다
                arr.push(1);
             else 
                // 안쪽 숫자는 이미 result 배열에 추가된 이전 열의 연속된 숫자를 더함
                arr.push((result[row-2][col-1] + result[row-2][col]));
        }
        result.push(arr);
    }
    return result
}
  • 이항 계수의 시간 복잡도와 성능 개선
    • $k$가 $n/2$보다 클 경우, 나머지 절반 삼각형은 중복값
    • 1차원 배열만으로도 구현이 가능

파이썬으로 파스칼의 삼각형 성능개선

1
2
3
4
5
6
7
8
9
10
11
12
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):
        j = min(i, k)
        while (j > 0):
            B[j] = B[j] + B[j - 1]
            j -= 1
    return B[k]
# 출력은 bin(n,k)와 동일

자바스크립트로 파스칼의 삼각형 성능개선

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function bin3(n,k) {
    if(n === 1) return [1] // n이 1일때엔 [1]을 리턴하도록 함
    // 파스칼의 삼각형은 절반 이후로는 전반 절반과 같은 값이다
    if(k > Math.floor(n/2)) k = n - k
    // 배열을 k+1 길이만큼 생성하고 0으로 채운다
    let arr = Array(k+1).fill(0)
    // 첫번째 값을 1로 설정한다
    arr[0] = 1;
    for (let i = 1; i < n + 1; i++){
        let j = Math.min(i, k)
        while (j > 0) {
            arr[j] = arr[j] + arr[j-1] // 이전값과 더한 값
            j -= 1 // j를 줄여나간다
        }
    }
    // 파스칼 삼각형 열이 홀수라면 중간 숫자는 중복되는 숫자이므로 slice함
    return n % 2 !== 0 
        ? [...arr, ...arr.slice(0,-1).reverse()] 
        : [...arr, ...arr.reverse()]
}