세 값의 대소 관계와 중앙값

세 값의 대소 관계

세 값의 대소(작고 큼)관계는 총 13가지가 나오게 되는데 이 조합을 그림으로 나열한다면 나무 형태이므로 결정 트리라고 합니다.

class Max3 {
    	public static void main(String[] args) {
        	Scanner sc = new Scanner(System.in);
            
            System.out.println("세 정수의 최대값을 구합니다.");
            System.out.print("a값 입력 : "); int a = sc.nextInt()
            System.out.print("b값 입력 : "); int a = sc.nextInt()
            System.out.print("c값 입력 : "); int a = sc.nextInt()
            
            // abc를 각각 비교해서 최대값 구하기
            int max = a;
            if (b > max) 
            	max = b;
            if (c > max)
            	max = c;
                
            System.out.println("최대값은 " + max + "입니다.");
        }
    }

위와 같은 구조로 작성하고 a,b,c의 값을 각각 최대한의 경우의수로 활용하면 총 13개의 경우의 수가 나오는 간단한 구조입니다. 이렇게 대소 관계는 구하기가 쉽습니다.

세 값의 중앙값

하지만 최댓값, 최솟값과는 달리 중앙값을 구하는 절차는 매우 복잡한데 수많은 알고리즘을 생각해 볼 수 있을 것입니다.

※ 세 값의 중앙값을 구화는 과정은 '퀵 정렬'에서도 다룹니다.

	class Median {
    	static int med3(int a, int b, int c) {
        	if (a >= b)
            	if (b <= c)
                    return b;
                else if (a <= c)
                	return a;
                else
                	return c;
            else if(a > c)
              return a;
            else if(b > c)
              return c;
            else
              return b;
        }
    }

세개의 정수형 인자를 받는 med3() 메서드 입니다.

확실히 최대값 최소값을 구하는 알고리즘보다는 복잡합니다.

또 다른 알고리즘으로 아래 코드가 있습니다.

	static int med3(int a, int b, int c) {
    	if((b >= a && c =< a) || (b <= a && c >= a))
        	return a;
        else if ((a > b && b > c) || (c > b && b > a))
        	return b;
        else
            return c;
    }

위 코드는 첫번째 예제에 비해 성능이 좋지 않습니다.(오래 걸림)

첫번째 코드에 비해 두번째 코드의 조건문이 더 많기에 더 오래 걸릴수 있다고 추측할 수 있습니다.

두 메서드는 대부분 입력 크기에 따라 달라지지 않기에 시간 복잡도는 0(1)이지만, 아래 메서드의 조건문이 더 많아서 더 많은 CPU 분기 예측 실패를 초래할 수 있습니다. 예측실패시 CPU 파이프라인이 비워지고 성능 저하가 발생하기에 첫 번째 메서드를 사용하는 것이 유리하겠습니다.
https://ko.wikipedia.org/wiki/%EB%B6%84%EA%B8%B0_%EC%98%88%EC%B8%A1
(알필요 없음)