[문제해결을 위한 창의적 알고리즘] 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