public class seq_Matrix {
/*
* 연쇄행렬 최소곱셈 알고리즘
* 두개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구함
* 복잡도 : O(n^3)
* DP table의 칸의 개수 n*n = n^2 .
* 한개의 칸을 채울 때 필요한 연산의 개수는?
* 최악의 경우 DP[1][6]인 경우에 가장 많은 연산을 요구.
* 한칸을 채울 때 최악의 경우 n번의 연산을 해야하므로
* O(n^3)의 시간복잡도 가진다.
*/
public static int minmult(int n, int d[], int P[][]){
int M[][] = new int[n+1][n+1];
for(int i = 0; i < n; i++) M[i][i] = 0;
for(int diag = 0; diag < n; diag++){ //diagonal
for(int i = 1; i < n - diag; i++){ //i = row
int j = i + diag; //j : column
if(j==i){
M[i][j] = Integer.MAX_VALUE; continue;
}
for(int k = i; k < j; k++){
M[i][j] = Math.min(M[i][j],
M[i][k] + M[k+1][j] + d[i-1]*d[k]*d[j]);
P[i][j] = k; //최소치를 주는 k의 값.
}
}
}
return M[1][n];
}
// 곱셈의 수가 가장 적게 드는 순서대로 괄호 쳐서 출력
public static void order(int i, int j, int P[][]){
if(i == j) System.out.printf("A" + i);
else{
int k = P[i][j];
System.out.printf("(");
order(i, k, P);
order(k+1, j, P);
System.out.printf(")");
}
}
}
public class floyd {
/*
* dp 기반 최단경로
* loop이 세번, n^3
* W : 그래프의 인접행렬식 표현
* D : 각 정점들 사이의 최단 거리
*/
public static void FW(int n, final int W[][], int D[][]){
D = W;
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
D[i][j] = Math.min(D[i][j], D[i][k] + D[k][j]);
}
}
}
}
// D는 최단경로 거리 저장하는 배열
// P는 최단경로 path,즉 거치는 노드 저장하는 배열
public static void FM2(int n, final int W[][] , int D[][] , int P[][]){
D = W;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
P[i][j] = 0; //0으로 P 초기화
}
}
for(int k = 1; k <= n; k++){
for(int i = 0; i <= n; i++){
for(int j = 1; j <= n; j++){
if((D[i][k] + D[k][j]) < D[i][j]){
P[i][j] = k; //vi에서vj로 가는데 vk를 지난다는 정보 저장
D[i][j] = Math.min(D[i][j], D[i][k] + D[k][j]);
//D[i][j] = D[i][k] + D[k][j];
}
}
}
}
}
//경로 출력
public static void path(int q, int r, int P[][]){
if(P[q][r] != 0){
path(q, P[q][r],P);
System.out.printf("v" + P[q][r]);
path(P[q][r], r, P);
}
else{
System.out.printf("v" + P[q][r]);
}
}
}
public class dp_binomial{
//dp 사용한 이항계수 계산 알고리즘.
//이항계수 결과값을 리턴한다.
public static void bin2(int n, int k){
int arr[][] = new int[n+1][k+1];
/* [dp : 파스칼의 삼각형 이용]
* 단위 연산 기준으로 계산하기!
* for문이 총 두번 있는데 바깥쪽이 n번 돌아가고 안쪽 loop이
* minimum이니까 k번 돌아간다.
* 따라서 n*k, 만약 k=n이면 n^2
* 시간 복잡도 : O(n*k) -- > O(n^2)
*/
for(int i = 0; i <= n; i++){
//0~i 또는 0~k까지 중 작은 것을 택함. 불필요한 것 배제
for(int j = 0; j <= Math.min(k,i); j++){
// 대각선일 때, 즉 i와 j가 같으면 무조건 1임
if(j == 0 || j == i) arr[i][j] = 1;
else arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}
// return arr[n][k];
for(int i = 0; i < n+1; i++){
for(int j = 0; j < k+1; j++){
System.out.printf(arr[i][j] + " ");
}
System.out.println();
}
}
// 시험에 나옴!! 매우 중요
public static void bin2_important(int n, int k){
int arr[][] = new int[n+1][k+1];
/*
시간복잡도를 O(n^2)를 어떻게하면 O(n)으로 낮출 수 있는가?
한 행이 끝나면 그 이전에 계산한 값은 필요하지 않음.
따라서 k 대신에 1만 써도 된다.
그리고 j 대신에 j%2를 넣어주기 mod 연산
이렇게하면 n*k가 아닌 2n이 필요하다. -> O(n)
*/
for(int i = 0; i <= n; i++){
for(int j = 0; j <= Math.min(i, 1); j++){
// 대각선일 때, 즉 i와 j가 같으면 무조건 1임
if(j == 0 || j == i) arr[i][j%2] = 1;
else arr[i][j%2] = arr[i-1][(j%2)+1] + arr[i-1][j%2];
}
}
// return arr[n][1];
for(int i = 0; i < n+1; i++){
for(int j = 0; j < k+1; j++){
System.out.printf(arr[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args){
// System.out.println(bin2(5, 2));
bin2(5, 2);
// System.out.println(bin2_important(5,2));
bin2_important(5, 2);
}
}
public class dq_binomial {
//분할 정복을 이용한 이항계수 구하기.
// 재귀가 필요하다
/*
* 여기서 가장 치명적인 문제점은 무엇인가?
* 이미 계산한 부분도 다시 계산.
*/
public static int bin1_recur(int k, int n){
if((k==0) || (k == n)) return 1;
else{
return bin1_recur(n-1, k-1)
+ bin1_recur(n-1, k);
}
}
}