[종만북] 이항 계수 - 동적계획법(Dynamic Programming) JAVA

출처 : 종만북 8.1 도입

코드설명

이항계수는 nCr 과 같이 n개의 숫자에서 r개를 뽑는 조합의 개수를 의미합니다.

예로 들었을때, 3개중 2개를 뽑는 경우는 3개입니다.

 

이항계수의 점화식을 통해 동적계획법을 사용함으로써 어떤 중복되는 부분문제의 연산을 피할 수 있는지 알아보려고 합니다.

먼저 이항계수의 점화식입니다.

nCr = (n - 1 C r - 1) + (n-1 C r ) 입니다.

만약 n == 0 (아무아이템을 선택하지 않는경우 1가지) n == r( 모든 아이템을 선택하는 경우 1가지) 의 경우 모두 1가지의 경우입니다.

 

위의 점화식을 그대로 재귀함수로 사용하면 됩니다.

 

이러한 점화식을 쉽게 이해하기 위해 예를 들어보겠습니다.

{1 2 3 4 5} 5개의 숫자가 주어져있습니다.

우리는 5C3, 즉 5개의 숫자 중 3개의 숫자를 뽑는 경우의 수를 구하려고 합니다.

이때, 위의 점화식에 의해

5C3 = 4C2 + 4C3 입니다.

왜 이렇게 될까요?

먼저, 5C3을 나누는 방법을 생각해봅니다.

{1, 2, 3, 4 5} 중에서 반드시 5를 포함하도록 하고 2개를 뽑는경우

{1, 2, 3,4, 5} 중에서 반드시 5를 포함하지 않고 3개를 뽑는 경우.

 

위의 예시를 통해 위의 점화식이 성립함을 직관적으로 이해할 수 있습니다.

(추가로, 이항계수에서의 조합을 파스칼의 삼각형으로도 이해할 수 있습니다.)

5C3 은 10이 나오겠습니다.

 

하지만, 만약 binomialCoefficient(4, 2)를 계산한다고 가정했을떄 매우 많은 중복이 발생합니다.

예로 들었을때, bino(4,2)가 실행되었을떄 bino(4,2) = bino(3, 1) + bino(3, 2)가 재귀실행합니다.

bino(3,1)은 bino(2, 0) + bino(2, 1) 이 재귀실행합니다.

bino(3, 2)는 bino(2, 1) + bino(2, 2)이 재귀실행합니다.

이떄 bino(2,1)이 두번 호출되고 있음을 알 수 있습니다.

여기서는 단순히 2번이라 보이지만, 실제로 bino(2,1)이 다시 재귀함수로 내려가며 계속해서 실행되기에 함수가 2개씩 늘어나므로 2^(남은 종료지점까지의 레벨)로 함수 호출이 늘어납니다.

 

여기에서 이러한 중복계산은 bino(3,1)에서만 실행되며 bino(2,0)과 bino(2,1)의 계산을 Caching하여 중복계산을 피해야만 합니다. 이러한 방법을 메모이제이션(memoization)이라 합니다. 

 

메모이제이션(memoization)을 통해 함수의 결과를 저장하는 장소를 마련해두고, 한번 계산한 값을 저장해뒀다 재활용할 수 있습니다. 이를 통해 모든 부분문제가 한번씩만 계산된어 함수호출횟수가  한번만임을 보장할 수 있습니다.

 

bino(n, [n/2])를 계산할떄 n이 1 증가할때마다 두배씩 증가하던(2^(n의 크기)) binomialCoefficient(int n, int r) 이 binomialCoefficientWithMemoization(int n , int r) 에서는 문제의 개수만큼, 즉 파스칼 삼각형에서 이루어진 문제수로만 나눠질 것 입니다. 즉 n의 제곱꼴로 증가하게 됩니다. 즉 O(n^2)입니다. 이는 파스킬 삼각형이  n x (n+1)/2 개의 부분문제로 구성되기에 그렇습니다. 파스칼 삼각형의 크기입니다.

 

이와 같이 두번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계기법을 동적계획법이라 합니다.

 

위와 같이 메모이제이션의 시간복잡도를 계산했습니다. 일반적으로 메모이제이션의 시간복잡도 과정은 아래와 같이 구할 수 있습니다.

(존재하는 부분문제의 수) x (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수) 입니다.

위 식을 이항계수를 계산하는 binomialCoefficientWithMemoization(int n , int r)  에 적용해보겠습니다.

존재하는 부분 문제의 수를 계산합니다. rr의 최대치는 n입니다. binomialCoefficientWithMemoization(int n , int r)를 계산할떄 만날 수 있는 부분 문제의 수는 O(n^2)입니다. (n)(n+1)/2 이기에 그렇습니다. 각 부분 문제를 계산할때 걸리는 시간은 반복문이 없으니 O(1)이고, 그러면 위의 식에 따라 계산하면, O(n^2) * O(1) = O(n^2)이 됩니다.

 

좀 더 디테일하게 살펴보면, 기저사례의 경우나 이미 답을 계산해둔 부분 문제의 경우 상수 시간에 수행되기에 알고리즘의 전체 수행시간에 영향을 미치지 않는다는 점을 인지합니다. 이항계수에서는 n==r이거나, r==0일떄가 기저사례였고, cache[30][30]을 통해 상수시간에 수행되게 합니다. 따라서, 메모이제이션의 수행시간은 위의 것들을 제외한 수행시간이 되는데 이 값의 최악의 경우가 O(n^2)임을 알 수 있습니다. 

 

기본적인 코드로직입니다.

 

• 기본 조건:
  • r == 0인 경우: 아이템을 하나도 선택하지 않는 경우이므로 1을 반환합니다.
  • n == r인 경우: 모든 아이템을 선택하는 경우이므로 1을 반환합니다.
• 점화식 적용:
  • 기본 조건에 해당하지 않는 경우, 점화식 C(n,k)=C(n−1,k)+C(n−1,k−1)C(n, k) = C(n-1, k) + C(n-1, k-1)C(n,k)=C(n−1,k)+C(n−1,k−1)를 사용하여 재귀적으로 값을 계산합니다.

 

입력예시 1

5 2

결과예시 1

10

코드

완전탐색할경우

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, K; 
	public static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		System.out.println(bino(N, K));
	}
	
	public static int bino(int n, int r) {
		//아무 아이템을 선택하지 않을경우, 모든 아이템을 선택할경우는 1가지 경우밖에 없습니다.
		if(r == 0 || n == r) {
			return 1;
		}
		return bino(n-1, r) + bino(n-1, r-1);
	}
	
}

 

코드입니다.

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	
	//-1로 초기화합니다.
	public static int[][] cache = new int[30][30];
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<30;i++) {
			Arrays.fill(cache[i], -1);
		}
		
		System.out.println(binomialCoefficientWithMemoization(5, 3));
    }
	
    // 메모이제이션을 이용한 이항 계수의 계산
	public static int binomialCoefficientWithMemoization(int n , int r) {
		//기저사례 1 : n == r(n개중에서 r개를 선택할경우), r == 0 (0개를 뽑는경우는 1가지)
		if(n == r || r == 0) return 1;
		//-1이 아니라면 한 번 계산했던 값이니 곧장 반환
		if(cache[n][r] != -1) return cache[n][r];
		//직접 계산한뒤 배열에 저장
		return cache[n][r] = binomialCoefficientWithMemoization(n - 1, r -1) + binomialCoefficientWithMemoization(n - 1, r);
	}
	
}

 

2차원 배열을 활용하여 모든 이항계수를 구해놓을경우(파스칼의 삼각형과 유사하다. 명확히 얘기하면 그림이 살짝 다르다)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, K; 
	public static int answer = 0;
	public static int[][] bino;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		bino = new int[N+1][N+1];
		bino();
		System.out.println(bino[N][K]);
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				System.out.print(" "+bino[i][j]);
			}
			System.out.println();
		}
	}
	
	public static void bino() {
		for(int i=0; i<=N; i++) {
			for(int j=0; j<=i; j++) {
				if(j == 0 || j == i) {
					bino[i][j] = 1;
					continue;
				}
				bino[i][j] = bino[i-1][j-1] + bino[i-1][j];
			}
		}
		
	}
	
}

 

파스칼삼각형 예시. 

 

 1 0 0 0 0   //0개 중에 0개를 선택할경우
 1 1 0 0 0	//1개중에 0개를 선택할경우, 1개중에 1개를 선택할경우
 1 2 1 0 0
 1 3 3 1 0
 1 4 6 4 1