/ C

알고리즘 정복하기 with C (3)Optimal Binary Search Trees

알고리즘 정복하기 with C (3)Optimal Binary Search Trees

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 알고리즘은 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 알고리즘을 코딩하면서 공부하기로 했습니다.

Optimal Binary Search Trees

이진 검색 트리는 말 그대로 이진 트리를 검색 목적으로 사용하는 것입니다. 왼쪽에는 같거나 더 작은 값을, 오른쪽에는 더 큰 값을 저장하고 leaf 노드들 간의 depth 차이가 1보다 클 수 없습니다. 여기서 ‘최적’이란 단어까지 붙으면 최적 이진 검색트리가 됩니다. 최적 이진 검색 트리는 가능한 이진 검색 트리 중 key를 찾는데에 걸리는 평균 시간이 가장 짧은 이진 검색 트리를 의미합니다.

Optimal Binary Search Trees pseudo code

Optimal Binary Search Trees 의 pseudo code

void optsearchtree(int n, const float p[], float& minavg, index R[][]) {
  index i, j, k, diagonal;
  float A[1..n+1][0..n];
  
  for(i=1; i<=n; i++) {
    A[i][i-1] = 0;
    A[i][i] = p[i];
    R[i][i-1] = 0;
  }
  
  A[n+1][n] = 0;
  R[n+1][n] = 0;
  
  for(diagonal = 1; diagonal <= n-1; diagonal++)
    for(i=1; i <= n-diagonal; i++) {
      j = i + diagonal;
      A[i][j] = minimum(A[i][k-1]+A[k+1][j])) + sum of pi ~ pj; //basic operation
      R[i][j] = a value of k that gave the minimum;
    }
    minavg = A[1][n];
}

Optimal Binary Search Trees 시간 복잡도

for문을 Basic Operation으로 할때 min의 루프까지 3번 중첩되고, j = i + diagonal 이므로, i 루프를 수행하는 횟수는 n - diagonal, k 루프(min)를 수행하는 횟수는 j - i + 1 = diagonal+1 이다. 따라서 ((n - diagonal) * (diagonal + 1)에서 diagonal = 1 ~ n-1 까지의 합이므로 n(n - 1)(n +4) / 6 이다. 따라서 O(n^3) 이다.

Optimal Binary Search Trees 구현

입력데이터

소스코드

#include <stdio.h>
#include <stdlib.h>

void optsearchtree(int n, float p[], float* minavg, int *R[]);

int main()
{
	int n = 4;
	float p[5] = { 0, 0.1, 0.2, 0.4, 0.3 };
	float minavg;
	float* p_minavg = &minavg;
	int** R;
	R = (int**)malloc(sizeof(int) * n+2);
	for (int i = 0; i < n+2; i++) 
		R[i] = (int*)malloc(sizeof(int) * n+1);
	
	optsearchtree(n, p, p_minavg, R);

	printf("A[1][4]: %f", minavg);


	return 0;
}

void optsearchtree(int n, float p[], float* minavg, int *R[])
{
	int i, j, k, diagonal;
	float** A;
	A = (float**)malloc(sizeof(float) * n+2);
	for (i = 0; i < n+2; i++)
		A[i] = (float*)malloc(sizeof(float) * n+1);

	for (i = 1; i <= n; i++) {
		A[i][i - 1] = 0;
		A[i][i] = p[i];
		R[i][i] = i;
		R[i][i - 1] = 0;
	}
	A[n + 1][n] = 0;
	R[n + 1][n] = 0;

	for (diagonal = 1; diagonal <= n - 1; diagonal++) {
		for (i = 1; i <= n - diagonal; i++) {
			j = i + diagonal;
			float min = 99999, min_k = 0;
			for (k = i; k < j + 1; k++) {
				if (A[i][k - 1] + A[k + 1][j] < min) {
					min = A[i][k - 1] + A[k + 1][j];
					min_k = k;
				}
			}
			R[i][j] = min_k;

			float sum = 0;
			for (k = i; k < j + 1; k++)
				sum += p[k];

			A[i][j] = min + sum;
		}
	}

	//printf("\n%f %d\n", A[2][4], R[2][4]);

	*minavg = A[1][n];
}

결과

최적 이진 탐색 트리 알고리즘을 구현했습니다. 결과가 잘 나옵니다.

알고리즘 진행 과정 손계산

알고리즘의 진행과정을 직접 계산하여 결과를 비교해보았습니다. 결과가 동일하게 나옵니다.