kingsubin

Section5. 최댓값 최솟값 찾기 본문

책/misc

Section5. 최댓값 최솟값 찾기

kingsubin 2021. 8. 5. 17:44
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package me.kingsubin.studyrepo.book.algorithm.section5;
 
public class findMaxMin {
    public static void main(String[] args) {
        int[] A = {2475928361489750};
        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;
    }
}
 
cs

 

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

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

 


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

' > misc' 카테고리의 다른 글

3장. HTTP 메시지  (0) 2022.05.02
2장. URL과 리소스  (0) 2022.04.25
1장. HTTP 개관  (0) 2022.04.24
HTTP 완벽 가이드 책 샀다.  (2) 2022.02.10
Section5. 빠른 정렬  (0) 2021.08.06
0 Comments
댓글쓰기 폼