최대값, 최소값, 중간값 구하기 - 자료구조와 함께 배우는 알고리즘 입문(자바)

해당 포스팅은 "자료 구조와 함께 배우는 알고리즘 입문"이라는 책을 바탕으로 공부한 내용임.

여러 변수의 값 중 최대값 구하기

예를 들어서 여러 개의 변수가 있을 때 그 중에서 가장 큰 값을 구하는 방법은 무엇일까?

 

아마 이건 따로 알고리즘을 접하지 않아도 어려운 문제는 아닐 것이다.

 

그냥 순차적으로 비교해나가면 된다.

public static int max(int a, int b, int c, int d){

        int max = a; // 변수 max를 생성해서 a의 값을 대입
        
        if(b>max) max = b; // max와 b를 비교해서 b가 크다면 max에 b를 대입
        
        if(c>max) max = c; // max와 c를 비교해서 c가 크다면 max에 c를 대입
        
        if(d>max) max = d; // max와 d를 비교해서 d가 크다면 max에 d로 대입
        
        return max;
    }

 

임의의 변수 max를 생성한 뒤 입력 값 중 하나를 대입한다.

 

그 뒤엔 max와 나머지 값을 비교하는 식으로 진행하면 된다.

여러 변수의 값 중 최소값 구하기

해당 내용도 최대값 구하기를 응용하면 쉽게 풀 수 있다.

 

다만 최소값이기 때문에 최대값과 부등호의 표시 등을 조금만 바꿔주면 된다.

 

public static int min4(int a, int b, int c, int d){

        int min = a; // 변수 min을 생성해서 a값을 대입
        
        if(min>b) min = b; // min과 b를 비교해서 b가 작다면 min에 b를 대입
        
        if(min>c) min = c; // min과 c를 비교해서 b가 작다면 min에 c를 대입
        
        if(min>d) min = d; // min과 d를 비교해서 b가 작다면 min에 d를 대입
        
        return min;
        
    }

 

임의의 변수 min을 생성한 뒤 입력값 중 하나를 대입한다.

 

그리고나서 min과 비교해서 min보다 비교값이 작다면 비교값을 min에 대입하는 식으로 진행하면 된다.

여러 값 중에서 중간값 구하기

예를 들어서 위와 같은 변수 3개가 있다고 가정해보자.

 

이 중에서 중간 값을 어떻게 구할까?

사람이라면 당연히 10이 가운데 값인 것을 쉽게 알아차릴 것이다.

 

하지만 이러한 인식 과정을 컴퓨터로 입력해주려면 조금 더 까다로운 과정을 거쳐야 한다.

 

public static int middle(int a, int b, int c){
        int avg = (a+b+c)/3; // 세 정수의 평균값

        int a1 = (a-avg>0)?(a-avg):-(a-avg); // 평균값에서 정수 a를 뺀 절대값
        int b1 = (b-avg>0)?(b-avg):-(b-avg); // 평균값에서 정수 b를 뺀 절대값
        int c1 = (c-avg>0)?(c-avg):-(c-avg); // 평균값에서 정수 c를 뺀 절대값

        // 절대값끼리 비교해서 가장 작은 절대값을 골라내는 식
        int anum = a1; // anum에 a의 절대값 a1을 대입
        anum = (anum > b1)?b1:anum; // a1과 b1을 비교해서 b1이 작으면 anum에 b1을 대입
        anum = (anum > c1)?c1:anum; // b1과 c1을 비교해서 c1이 작으면 anum에 c1을 대입

        // 반환될 결과값에 가장 작은 절대값을 대입
        int result = anum;

        // 평균에서 정수를 뺀 절대값에 따른 매개변수 선택
        // 가장 작은 절대값이 a1과 같으면 결과값인 result가 a;
        // 가장 작은 절대값이 b1과 같으면 결과값인 result가 b;
        // 가장 작은 절대값이 c1과 같으면 결과값인 result가 c;
        return result = (anum == a1)?a:(anum == b1)?b:c;
    }

 

우선 내가 이 문제를 보고 가장 직관적으로 떠올린 답은 위와 같은 식이다.

 

우선 매개변수 3개의 평균 값을 구한다.

 

그리고 각 매개변수 별로 매개변수에서 평균값에서 뺀 절대값을 구한다.

 

가장 작은 절대값을 가진 매개변수를 반환한다.

 

즉 평균에 가장 가까운 매개변수을 가운데 값이라 생각하고 반환하는 식이다.

 

일단 내가 검증할 때는 이상없이 잘 작동했고 가운데 값을 잘 반환했다.

 

하지만 책에서 요구하는 답을 얼핏보니 책은 매개변수 a,b,c를 일일이 비교하는 방식을 썼다.

 

예를 들면 아래와 같이 매개변수 a,b,c를 일일이 비교해서 가운데 값을 구하는 식이다.

 

 

책에 따르면 이런식의 분기별 조합이 13가지가 존재한다고 한다.

 

즉 이런식의 조합을 식으로 나타내려면 선택문을 이용해서 13가지 분기를 만들어야 한다...

 

굳이 이런 식으로 해야하나 싶긴했다.

 

왜냐면 분기가 많다는건 그만큼 식이 복잡해지고 실수가 생길 여지가 크다는 것이다.

 

public static int middle3(int a, int b, int c){

        if(a>=b)
            if(c>=a) return a;
            
            else if(c>=b) return c;
            
            else return b;
            
        else if (c>=b) return b;
        
        else if (c>a) return c;
        
        else return a;
    }

 

하지만 책에서 원하는 답에 맞춰서 결국 혼자서 풀어봤다.

 

기본적으로 대소관계가 확실하고 중간값이 확실히 존재한다면 중간값이 잘 반환된다.

 

다만 연습장에 끄적이면서 경우의 수를 따지면서 썼던 식이라서...

 

어째서 저렇게 나왔는지는 잘 기억이 안난다.

 

책에 나온 것처럼 13가지 조합이 다 성립되는지 그런건 모르겠고 여튼 중간값은 확실히 출력해준다.

 

public static int middle3_2(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;
    }

 

책에서 나온 알고리즘이다.

 

기본 구조는 동일하지만 비교 순서가 다소 다른 차이가 있다.

 

당연하지만 이게 정답으로 실려있으니 중간값은 확실히 출력된다.