4.1 The maximum-subarray problem

4.1 단원은 주어진 리스트에서 합을 최대로 갖는 부분 합을 찾는 방법에 대해 공부했다. 앞에서 했던 merge sort와 비슷하게 리스트를 반으로 나누어서 최대 값을 찾아주면 된다. 그러나 한가지 경우가 더 있는데, 리스트를 나누어준 중간 값을 지나는 부분 합이다. find_maximum_cross 라는 함수를 추가로 정의해서 그 합을 왼쪽 리스트의 부분합, 오른쪽 리스트의 부분합 이렇게 세 개의 합과 비교해서 가장 큰 부분합의 시작인덱스와 끝 인덱스를 반환한다. python으로 작성을 해보았는데 쓸데없이 길어보이는 부분이 있지만 너무 귀찮아서 책에 있는 수도코드를 참고했다.

def find_maximum_sub(a, low_index, high_index):
    if low_index == high_index:
        return low_index, high_index, a[low_index]
    else:
        mid = int((low_index + high_index) / 2)
        (left_low, left_high, left_sum) = find_maximum_sub(a, low_index, mid)
        (right_low, right_high, right_sum) = find_maximum_sub(a, mid + 1, high_index)
        (cross_low, cross_high, cross_sum) = find_maximum_cross(a, low_index, high_index, mid)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_low, left_high, left_sum
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return right_low, right_high, right_sum
        else:
            return cross_low, cross_high, cross_sum

def find_maximum_cross(a, low_index, high_index, mid):
    if mid == low_index:
        left_sum = a[mid]
        left_index = mid
    else:
        left_sum = a[mid]
        left_index = mid
        sum = 0
        i = mid
        while i >= low_index:
            sum += a[i]
            if sum > left_sum:
                left_sum = sum
                left_index = i
            i -= 1
    if mid + 1 == high_index:
        right_sum = a[high_index]
        right_index = high_index
    else:
        right_sum = a[mid + 1]
        right_index = mid + 1
        sum = 0
        while mid < high_index:
            mid += 1
            sum += a[mid]
            if sum > right_sum:
                right_sum = sum
                right_index = mid
    return left_index, right_index, left_sum + right_sum

연습문제

4.1-1

제일 작은 음수와 그 인덱스를 반환한다.

4.1-2

def find_max_array(a):
    i=0
    max_sum = a[0]
    max_left = 0
    max_right = 0
    while i<len(a):
        j=0
        sum = 0
        while i+j<len(a):
            sum+=a[i+j]
            if sum > max_sum:
                max_sum = sum
                max_left = i
                max_right = i + j
            j += 1
        i += 1
    return max_left,max_right,max_sum

첫번째 인덱스에서 시작하는 부분합 n-1개를 전부 구해서 최대 합과 인덱스를 구함. 그리고 두번째에서 시작하는 모든 부분합 n-2개의 합도 계속 최댓값과 비교해준다. 이런식으로 구해주면 세타n^2 시간을 갖는다.

4.1-3

위의 두 코드를 비교해봤더니 약 13개 이상일 떄부터 재귀함수를 사용하지 않은 방법이 평균적으로 조금 빨랐다.

베이스 케이스를 길이가 13일때 이하일때 단순하게 구하도록 수정해봤지만 조금 빨라지는가 싶더니 숫자가 커지면 오히려 느려지기도 하고 큰 차이를 보이지는 않았다. 분할 된 리스트의 길이가 14~26 사이인경우 이를 절반으로 다시 나누면 7~13 길이의 값들이 나오게되고 일반적인 방법과 재귀 콜을 했을때랑 시간차이가 나야 하는데 리턴값을 받고 low_index 값을 다시 더하는 부분이 그 차이 정도는 매꾸게 되는게 아닌가 생각된다.

4.1-5

내일 풀어야지