최적 알고리즘과, 루프 불변성

 

 

[ 알고리즘 분석 기준]

최적 알고리즘을 찾기 위해서 가장 먼저 해야할 일은 문제를 풀 수 있는 가장 효율적인 알고리즘을 고안하는 것이다. 그 후 이 알고리즘의 작업량(W(n))을 구한다. 이 문제를 풀 수 있는 다른 알고리즘의 작업량(F(n)과 개발자가 고안한 알고리즘의 작업량이 같거나 적은지 확인한다. 작업량 W(n)과 F(n)이 같거나 적다면 최적의 알고리즘으로 본다.

 

알고리즘에 대해서 분석하기 위한 기준으로 "최단정수기"가 있다. 최단정수기는 (1) 최적성, (2) 단순성, (3) 정확성, (4) 수행성, (5) 기억장소 사용량을 말한다. 이 다섯가지 기준을 활용해서 알고리즘을 말할 수 있고 평가할 수 있다.

 

(1) 최적성

제작한 알고리즘보다 더 적은 연산을 수행하는 알고리즘이 없다는 것을 말한다.

 

(2) 단순성

알고리즘은 간결하여 해독성이 좋아야 한다.

 

(3) 정확성

입력에 대해서 유한 시간 내에 원하는 결과를 만들어야 한다.

 

(4) 수행성

Worst Case와 Best Case의 중간을 해당 알고리즘의 수행 능력으로 본다.

 

(5) 기억장소 사용량

알고리즘이 문제를 처리할 때 사용하는 저장 공간을 말한다.

 

 

[ Loop Invariant, 루프 불변 ]

알고리즘 개론에서 나오는 이야기 중에 하나가 루프 불편(Loop Invariant)이다. 루프 인배리언트는 프로그램의 루프를 반복할 때마다 이전의 결과와 이후의 결과가 같다는 것을 증명하는 것이다. 3가지 기준으로 루프의 불변을 증명하는데 첫번째는 초기(Intialization)단계 두번째는 유지(Maintenance)단계 그리고 세번째는 종료(Termination)단계이다.

 

(1) 초기단계(Initialization)는 루프를 처음 실행할 때, 참이 되는 조건을 말한다. Loop에 처음 진입하자 마자 실패하는건 당연히 불변하지 않다는 것이다.

 

(2) 유지단계(Maintenance)는 초기 이후에 임의 Loop에서도 참이 성립되는 조건을 말한다. 예를 들어 1~100번째 Loop가 있다고 했을 때 1부터 100까지 Loop은 다 참이 되어야 한다는 말이다.

 

(3) 종료단계(Terminantion)는 루프가 종료될 때 참이 성립되는 조건이다. 루프를 열심히 수행하는 것도 중요하지만 마지막에는 잘 수행하고 루프를 탈출해야 완벽한 것이다.

 

뒤에서는 selction sort(선택 정렬), merge sort(합병 정렬), quick sort(퀵 정렬)에 대한 Loop Invariant(루프 불변성)을 알아보도록 하겠다. 코드는 웹 파이썬 콘솔에서 실행했다.

 

 

 

[ Insertion Sort의 Loop Invariant ]

삽입 정렬(Insertion Sort)는 $O(n^2)$ 시간복잡도를 가진다.

(1) 초기 단계 : j=1

Array "A"를 index pointer인 j를 1초 초기화한다.(j = 1)

 

(2) 유지단계 : j ≤ n

Array "A"를 전부 하나씩 비교(j <= n)하면서 전체의 값을 정렬한다.

 

(3) 종료단계 : j = n+1

Array "A"의 전체 길이(n)보다 범위를 넘어가게 될 경우(j = n + 1), 루프를 종료하고 selection Sort를 완벽하게 종료한다.

 

 

Selection Sort의 파이썬 코드는 아래와 같다.

def insert_sort(v):
	for i in range(1, len(v)):
	    j = i -1
	    print(str(v[i]) + "과 " + str(v[j]) + "를 비교한다.")
	    while(j >= 0 and v[i] < v[j]):
	        print("While True")
	        j-=1
	    print("인덱스" + str(j+1) + "에 " + str(v[i]) + "를 넣어라")
	    v.insert((j + 1), v[i])
	    print("before del")
	    print(v)
	    del v[i + 1]
	    print("after del")
	    print(v)
	    print("\n")
	return v

v = insert_sort([8,9,4,6,3])
print(v)

 

 

 

[ Merge Sort의 Loop Invariant ] 

Divide 단계에서는 정렬이 일어나지 않고 단순하게 Element를 쪼개기 때문에 시간 복잡도가 $O(n)$ 이다. 이런 단순한 과정으로 인해 Loop Invariant의 증명이 불필요하다. 대신에 Conquer 단계에서는 쪼개진 리스트를 정렬하면서 합치는 과정을 갖게 되는데 이때 시작복잡도는 $O(logn)$이다. 쪼개는 과정(Divide)과 합치는 과정(Conquer)을 더해서 $O(nlogn)$의 시간복잡도를 가진다. 그중 합치는 내용을 Loop Invariant로 증명해볼 수 있다.

 

(1) 초기단계 : l = h = 0

low_array와 high_array의 index로 사용될 l과 h를 0으로 초기화한다.

 

(2) 유지단계 : l < low_array[l] and h < high_array[h]

l이 low_array 인덱스를 벗어나고 h가 high_array 인덱스를 벗어날 때까지 반복한다.

 

(3) 종료단계 : len(low_array) + len(high_array) = len(merged_array)

low_array의 길이와 high_array의 길이의 합이 merged_array 길이의 합과 같으면 종료한다.

 

Merge Sort의 파이썬 코드는 아래와 같다.

def merge_sort(array):
    print("#start array : " + str(array))
    
    if len(array) < 2:
        return array

    mid = len(array) // 2
    low_array = merge_sort(array[:mid])
    print("#low_array : " + str(low_array))
    high_array = merge_sort(array[mid:])
    print("#high_array : " + str(high_array))

    merged_array = []
    l = h = 0
    while l < len(low_array) and h < len(high_array):
        if low_array[l] < high_array[h]:
            print("#high win and low append")
            merged_array.append(low_array[l])
            l += 1
        else:
            print("#low win and high append")
            merged_array.append(high_array[h])
            h += 1
        print("#compare : " + str(merged_array))
    
    merged_array += low_array[l:]
    print("#last low_array[l:] : " + str(low_array[l:]))
    print("#last low_array : " + str(merged_array))
    merged_array += high_array[h:]
    print("#last high_array[h:] : " + str(high_array[h:]))
    print("#last high_array : " + str(merged_array))
    return merged_array

array = [9,3,4,7,1,2,0,8,5,6]
result = merge_sort(array)
print("#"+str(result))

 

 

 

[ Quick Sort의 Loop Invariant ] 

퀵정렬의 시간복잡도는 병합 정렬과 마찬가지로 $O(nlogn)$이고 이 시간복잡도는 Divide and Conquer를 합친 시간복잡도이다.

 

(1) 초기단계 : A[p ~ i] ≤ Pivot

Array "A"의 절반(A[ p ~ i ])은 Pivot보다 작은 값으로 이루어져 있다.(A[ p ~ i ] <= Pivot)

 

(2) 유지단계 : A[i+1 ~r-1] > Pivot

Array "A"의 나머지 절반인 A[i+1 ~r-1]는 Pivit보다 큰 값으로 이루어져 있다.(A[i+1 ~r-1] > Pivot) Pivot보다 작은 값으로 이루어진 Left Array와 Pivot보다 큰 값으로 이루어진 Right Array는 루프를 돌면서 Array를 반복적으로 쪼개고 정렬한다.

 

(3) 종료단계 : A[r] = Pivot

Array "A"가 더 이상 쪼개지지 않을 때까지 쪼개졌을 때, Array의 마지막 값이 Pivot이 된다.(A[r] = Pivot) 마지막 값이 Pivot이 되면 퀵정렬을 완료하고 종료한다.

 

Quick Sort의 파이썬 코드는 아래와 같다.

def quick_sort(arr):
    print("#input : " + str(arr))
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    print("#pivot : " + str(pivot))
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
            print("#num < pivot : " + str(lesser_arr))
        elif num > pivot:
            greater_arr.append(num)
            print("#num > pivot : " + str(greater_arr))
        else:
            equal_arr.append(num)
            print("#num = pivot : " + str(equal_arr))
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)
    
array = [1,0,5,2,6,8,9,3,4,7]
v = quick_sort(array)
print("#quick_sort result : " + str(v))