kingsubin

package me.kingsubin.studyrepo.book.algorithm.section5;
 
public class findMaxMin {
    public static void main(String[] args) {
        int[] A = {24, 75, 92, 83, 61, 48, 97, 50};
        int[] answer;
 
        answer = findMaxMin(A, 0, A.length - 1);
 
        System.out.println("Min: " + answer[0]);
        System.out.println("Max: " + answer[1]);
    }
 
    // (Divide And Conquer) find the min and max in array A[i....j]
    public static int[] findMaxMin(int[] A, int i, int j) {
        int mid;
        int[] result = new int[2];
        int[] leftResult;
        int[] rightResult;
 
        if (i == j) { // size 가 1인 경우
            result[0] = A[i];
            result[1] = A[j];
        } else if (i == j - 1) { // size 가 2인 경우
            if (A[i] < A[j]) {
                result[0] = A[i];
                result[1] = A[j];
            } else {
                result[0] = A[j];
                result[1] = A[i];
            }
        } else {
            // 재귀 형식으로 계속 left, right 정복해나감 
            mid = (i + j) / 2; // 배열의 중간 부분 변수로
            leftResult = findMaxMin(A, i, mid);
            rightResult = findMaxMin(A, mid + 1, j);
 
            if (leftResult[0] < rightResult[0]) {
                result[0] = leftResult[0];
            }
            if (leftResult[1] < rightResult[1]) {
                result[1] = rightResult[1];
            }
        }
 
        return result;
    }
}
 

 

Section 5에서는 분할정복에 대해서 다룬다.

일반적으로 알고있는 quick sort 가 떠오른다.

 

---

출처: 자바로 쉽게 배우는 알고리즘