C언어 알고리즘&자료구조 #1 세 값의 중앙값을 구하는 알고리즘

---

중앙값을 구하는 알고리즘은 최대/최소값을 구하는 알고리즘에 비해서 절차가 복잡하기에 여러가지의 알고리즘이 나올 수 있다.

이번 포스팅에서는 2가지의 알고리즘을 제시하고, 어떤 알고리즘이 더 효율적인지에 대해 정리해 보려고 한다.

---

<LIST>

#1세 값의 대소관계는 13종류이다.

#2중앙값을 구하는 알고리즘

---

#세 값의 대소 관계는 13종류이다.

세 변수의 중앙값을 구하는 알고리즘에 대해 알아보기 전에, 세 값을 조합했을 때 총 몇 가지의 조합이 나올 수 있는지, 결정 트리(decision tree)를 통해서 알아 보도록 하자.

결정 트리는 왼쪽 끝(a>=b)에서 시작해서 오른쪽 끝으로 이동한다.

조건이 성립하면 검은색 줄, 조건이 성립하지 않으면 빨간색 줄을 통해서 이동한다.

이렇게 결정트리를 미리 그려 두면, 알고리즘이 모든 경우를 빼먹지 않고 제대로 작동하는지 쉽게 파악이 가능하다.

 

 

---

#중앙값을 구하는 알고리즘

이제 본격적으로 세 값의 중앙값을 구하는 알고리즘에 대해서 알아보자.

우선 첫 번째 알고리즘이다.

 

#include <stdio.h>

int MID1(int x, int y, int z)
{
	if(x>=y){
		if(y>=z)
			return y;
		else if(x<=z)
			return x;
		else
			return z;	
	}
	
	else if(x>z){
		return x;
	}
	
	else if(y>z){
		return z;
	}
	
	else{
		return y;
	}
}

int main(void)
{
	int x,y,z;
	
	printf("Calculate MID\n");
	printf("X : "); scanf_s("%d",&x);
	printf("Y : "); scanf_s("%d",&y);
	printf("Z : "); scanf_s("%d",&z);
	
	printf("MID is %d\n", MID1(x,y,z));
	
	return 0;
}

 

다음으로 두 번째 알고리즘이다.

 

int MID2 (int x, int y, int z){
	if ((y>=x && z<=x) || (y<=x && z >= x))
		return x;
	else if ((x>y && z<y) || (x<y) && z>y)
		return y;
	else
		return c; 
}

 

두 알고리즘 중 어떤 알고리즘이 더 효율적인 알고리즘일까?

언뜻보면 두 번째가 더 짧기에 두 번째 알고리즘이 더욱 효율적인 코드라고 생각 할 수도 있겠지만, 정답은 첫 번째이다.

 

 

2,4번째 줄을 보면 y>=x 의부정은 y<x 이고, y<=x의 부정은 y>x 인데, 이 부등호 식들의 부정값이 else if 문에서 다시 계산이 이루어지고 있다.

따라서 중복이 발생한다. 우리는 알고리즘을 효율적으로 설계하기 위해선, 중복을 최소화 해야하만 하기에, 코드의 길이는 두 번째 알고리즘이 짧지만, 첫 번째 알고리즘으로 설계하는게 더욱 효율적인 방법이다.

---

다음 글은 개인적인 알고리즘 공부 내용을 기록한 것입니다.