[과제] Divide and conquer

이번 과제는 분할정복 알고리즘으로 문제를 해결하는 것이었다.

 

1.a 정렬 후 회전된 배열에서 최대값 찾기

1) 내 답안

public static int max(int[] arr, int from, int to) {
    if(from > to) return -1;
        
    int mid = (from + to) / 2;
        
    if(arr[from] > arr[mid]) {
        int m = max(arr, from + 1, mid);
        return (m > arr[from]) ? m : arr[from];
    } else if(arr[mid] > arr[to]) {
        int m = max(arr, mid + 1, to);
        return (m > arr[mid]) ? m : arr[mid];
    } else if(arr[from] == arr[to]) { //O(n)
        int m1 = max(arr, from + 1, mid);
        int m2 = max(arr, mid + 1, to);
        return (m1 > m2) ? m1 : m2;
    } else {
        return arr[to];
    }
}

중복인 값이 많으면 $O(n)$, 아니면 $O(\log\, n)$

 

2) 교수님 답안

public static int max(int[] arr, int from, int to) {
    if(from > to) return -1;
    
    int mid = (from + to) / 2;
    int m = max(arr, mid + 1, to);
    
    return (arr[mid] > m) ? arr[mid] : m;
}

 

'정렬 후 회전된 배열'의 특징을 적극 활용한 답안.

역시 교수는 그냥 하는 게 아니다 그죠?

정렬 후 회전된 배열 {5, 6, 7, 8, 9, 1, 2, 3, 4}을 보면 $arr[mid]$와 $arr[mid+1..to]$에서의 최대값만 비교하면 됨을 알 수 있다.

내 답안에 비해 연산 횟수가 현저히 적으나 중복이 많은 {1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1}과 같은 배열에서는 2를 찾아내지 못 한다. 교수님이 잘못 하셨다는 게 아니라 그냥 그렇다구,,

 

 

1.b 정렬 후 회전된 배열의 회전된 횟수

public static int getRotations(int[] arr) {
    return ((getIdxOfMax(arr, 0, arr.length - 1) + 1)%(arr.length));
}
 
public static int getIdxOfMax(int[] arr, int from, int to) {
    if(from > to) return 0;
    
    int mid = (from + to) / 2;
    
    if(arr[from] > arr[mid]) { 
        int mIdx = getIdxOfMax(arr, from + 1, mid);
        return (arr[mIdx] > arr[from]) ? mIdx : from;
        
    } else if(arr[mid] > arr[to]) {
        int mIdx = getIdxOfMax(arr, mid + 1, to);
        return (arr[mIdx] > arr[mid]) ? mIdx : mid;
        
    } else if(arr[from] == arr[to]) { //O(n)
        int mIdx1 = getIdxOfMax(arr, from + 1, mid);
        int mIdx2 = getIdxOfMax(arr, mid + 1, to);
        return (arr[mIdx1] > arr[mIdx2]) ? mIdx1 : mIdx2;
        
    } else {
        return to;
    }
}

어떤 정렬된 배열 {1, 2, 3, 4, 5, 6, 7}을 생각해보자.

이 배열을 1회 회전시키면 {7, 1, 2, 3, 4, 5, 6}이다. 이 때 최대값 7의 인덱스는 0이다.

2회 회전시키면 {6, 7, 1, 2, 3, 4, 5}이다. 이 때 최대값 7의 인덱스는 1이다.

7회 회전시키면 원래대로 돌아온다. 이 때 회전 수는 0으로 간주한다(원본 배열과 같으니까)

따라서 회전수는 (최대값의 인덱스 + 1) % (배열 길이)다.

 

1.c 정렬 후 회전된 배열에서 주어진 k의 인덱스 찾기

public static int getIdx(int[] arr, int k, int from, int to) {
    int idx = getIdxOfMax(arr, from, to); //O(log n)
        
    if((from < idx) && (idx < to)) {
        return (k < arr[from]) ? getIdx(arr, k, idx, to)
                               : getIdx(arr, k, from, idx);
    } else if(idx == from) { //1 rotation
        return (arr[from] == k) ? from
                                : getIdx(arr, k, from + 1, to); 
    } else if(idx == to) { //0 rotation
        int mid = (from + to)/2;
        
        return (k <= arr[mid]) ? getIdx(arr, k, from, mid)
                               : getIdx(arr, k, mid + 1, to);
    } else {
        return -1;
    }
}

두 달 지났더니 어떻게 했는지 잊어버림.

주석을 잘 달아놓자

 

 

 

2.a 중복값이 없고 오름차순 정렬된 배열 A에서 A[i]=i인 i 찾기

public static int same(int[] arr, int from, int to) {
    if(from > to) return -1;
    
    int mid = (to + from) / 2;
    
    if(arr[mid] < mid) {
        return same(arr, mid + 1, to);
    } else if(arr[mid] > mid) {
        return same(arr, from, mid - 1);
    } else {
        return mid;
    }
} 

앞에서 했던 것들과 거의 같음. 설명 생략

 

2) 교수님 답안

public static int same(int[] arr, int from, int to) {
    if(from > to) return -1;
    
    int mid = (to + from) / 2;
    
    if(arr[from] <= from && to <= arr[to]) {
        return mid;
    } else {
        return -1;
    }
} 

 

$A[i]=i$이려면 $A[from]$은 $from$ 이하여야 한다.

오름차순 정렬되어 있으므로 $A[from]>from$이면 $A[i]$는 무조건  i보다 클 수밖에 없다.

예를 들어 $A = \{1, 4, 5, 6, 7\}$, $from = 0, to=4$라고 하자.

$A[0]=1$이다. 즉 $A[from]>from$이다. 이 경우 $i$가 $1$ 커지면 $A[i]$는 무조건 $1$ 이상 커지므로 $A[i]$와 $i$의 차이는 좁혀지지 않는다. 따라서 $A[i]=i$인 $i$는 없다.

물론 이는 문제에서 '중복 값이 없다'고 주어졌기 때문. 중복값이 엄청 많으면 당연히 좁혀진다.

 

2.b 모든 요소가 0 이상이며 중복 요소가 없고 오름차순 정렬된 배열 A에서 A[i]=i인 i 찾기

는 더 쉽다.

인덱스는 $0$부터 시작하므로 $A[0]$이 $0$이 아니라면 모든 요소가 무조건 양수다.

중복 요소가 없으므로 $A[0]>0$이면 $A[1]$부터 마지막 요소까지 $A[i]=i$인 $i$는 없게 된다.
(없으면 -1 반환)

public static int same(int[] arr) {
    return (arr[0] == 0) ? 0 : -1;
}

 

3. 최대합 부분배열 구하기

public static int[] findMaxRange(int[] arr, int[] range) {
    if(range[0] > range[1]) return new int[] {-1, -1};
    if(range[0] == range[1]) return new int[] {range[0], range[0]};
    
    int mid = (range[0] + range[1]) / 2;
    int frontSum = 0, rearSum = 0;
    int frontMax = Integer.MIN_VALUE, rearMax = Integer.MIN_VALUE;
    int frontIdx = 0, rearIdx = 0;
    
    for(int i = mid; i >= range[0]; i--) {
        frontSum += arr[i];
        if(frontMax < frontSum) {
            frontMax = frontSum;
            frontIdx = i;
        }
    }
    
    for(int i = mid + 1; i <= range[1]; i++) {
        rearSum += arr[i];
        if(rearMax < rearSum) {
            rearMax = rearSum;
            rearIdx = i;
        } 
    }
    
    int[] frontRange = findMaxRange(arr, new int[] {range[0], mid});
    int[] midRange = new int[] {frontIdx, rearIdx}, resRange;
    int[] rearRange = findMaxRange(arr, new int[] {mid + 1, range[1]});
    
    resRange = (sum(arr, frontRange) > sum(arr, rearRange)) ? frontRange : rearRange;
 
    return (sum(arr, midRange) > sum(arr, resRange)) ? midRange: resRange;
}
 
public static int sum(int[] arr, int[] range) {
    return (range[0] == range[1]) ? (arr[range[0]]) 
                                  : (arr[range[0]] + sum(arr, new int[] {range[0] + 1, range[1]}));  
}

어떤 배열에서 연속된 요소 몇 개를 골라서 그 합이 최대가 되는 부분배열을 구한다.

예를 들어 {-1, 2, -5, 5, 7, 8}의 최대합 부분배열은 {5, 7, 8}이므로 반환값은 (3, 5)다.

 

양심고백) 사실 검색하면 다 나와서 검색해서 했다.

다른 분들이 올린 코드는 합을 반환하는데, 과제는 범위를 구하는 거라서 그 부분만 수정했다.