[문제해결을 위한 창의적 알고리즘] Combination (고급 p.87)

이 책의 앞부분에서 살펴본 문제 ([문제해결을 위한 창의적 알고리즘] Combination (고급, p29)) 동적 계획법 (Dynamic Programming)으로 해결해 보는 문제이다. ! (팩토리얼)을 빠르게 증가하므로 오버플로우를 내지 않고 계산하기 위해 이와 같은 방법으로 풀 수 있다고 한다.

여기서는 Dynamic Programming의 성능을 가장 최적화할 수 있는 상향식 풀이를 소개한다. (실제로 재귀함수를 이용한 하향식 접근 방법은 call stack이 오버헤드가 되어 성능이 좋지 않다). 문제에서 가장 중요한 것은 점화식을 유도하는 것인데, n개 중에서 k개를 고르는 방법은 1) n-1개에서 k개를 다 고르는 것과 2)n-1개에서 k-1개를 고르고 마지막 n번째 항목을 그냥 추가하는 방법 2가지를 더하면 된다는 것을 유도하면 쉽게 문제가 해결된다.

import java.util.Scanner;

public class Combination87 {

public static int n, k;

//ㅜn,k의 최대값이 30이므로 30까지 index할 수 있도록 31 X 31 배열 선언

public static int[][] DT = new int[31][31];

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n=sc.nextInt();

k=sc.nextInt();

sc.close();

for (int i = 1; i<=n; i++){

for (int j=1; j<=i; j++){

// i개 중에서 1개를 선택하는 방법은 i가지

if (j==1)

DT[i][j] = i;

// i개 중에서 i개를 선택하는 방법은 1가지

else if (i==j)

DT[i][j]=1;

// i개 중에서 j개를 선택하는 방법은 i-1개에서 j개를 선택하는 가짓수와 i-1개에서 j-1개를 선택하는 가짓수 합

else

DT[i][j]=DT[i-1][j]+DT[i-1][j-1];

}

}

System.out.println(DT[n][k]);

return;

}

}

Big O(n x k)

Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/Combination87.java

문제해결을 위한 창의적 알고리즘 목록