[알고리즘] 동적 프로그래밍 - 이항계수 / 이진트리

이항계수

 

분할 정복법을 이용한 이항계수 알고리즘

int binary(int n, int k){
	if(k==0 || n == k) return 1;
    else return binary(n-1, k-1) + bin(n-1, k);
}

 

 

동적프로그래밍을 이용한 이항계수 알고리즘

int binary(int n, int k){
    int B[n][k];
    for(int i=0; i<=n; i++){
    	for(int j=0; j<=min(i,k); j++){
        	if(j==0 || j==i) B[i][j] = 1;
            else B[i][j] = B[i-1][j-1] + B[i-1][j];
      	}
    }
    return B[n][k];
}

 

 

트리의 종류

이진 트리(binary tree) : 각 노드가 최대 두 개의 자식 노드만을 가질 수 있는 트리

균형 이진 트리(balanced binary tree) : 트리의 모든 노드의 왼쪽 부분트리와 오른쪽 부분트리의 깊이가 최대 하나 차이가 나는 트리

순서 트리(ordered tree) : 각 노드의 자식이 순서화된 루트트리.

완전 이진 트리(complete binary tree) : 노드의 차수가 2거나 리프노드.