[알고리즘] Algorithmic Analysis - correctness with induction

 

알고리즘, 컴퓨터 과학의 핵심 / 알고리즘 개념 소개와 분석법

서론

2학기, 지난 학기에 배운 자료구조 과목에 이어 알고리즘을 수강하게 되었다. syllabus 상으로 앞으로 배울 내용에 대해 살펴봤을 때, 자료구조와 큰 차이는 없어보였다. 하지만 자료구조에서는 자료를 어떻게 handling할지 구체적인 방안에 대해 공부했다면, 알고리즘은 전체적인 상황에 집중한다. 즉, 알고리즘은 컴퓨터 과학의 핵심이며, "문제를 해결해나가는 절차"라고 정의할 수 있다. 이는 마치 요리 레시피와 같아서, 입력을 받아 특정한 단계들을 거쳐 원하는 결과를 출력하는 과정을 기술한다. (과정에 초점)

알고리즘의 correctness 증명

알고리즘이 항상 올바른 결과를 출력하는지 확인하는 것은 매우 중요하다. 이를 위해 우리는 알고리즘을 분석하고, 그 안에서 변하지 않는 특정 조건, 즉 '불변성(invariance)'을 찾아내는 방법을 사용한다. 이러한 불변성을 통해 알고리즘의 각 단계가 올바르게 작동함을 증명하고, 결과적으로 전체 알고리즘의 정확성을 보장할 수 있다.

이 개념을 더 잘 이해하기 위해 Insertion Sort 알고리즘을 예시로 살펴보자. Insertion Sort는 정렬되지 않은 리스트를 정렬된 상태로 만드는 알고리즘이다.

Python

def insertion_sort(A):
    for i in range(1, len(A)):
        cur_value = A[i]
        j = i - 1
        while j >= 0 and A[j] > cur_value:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = cur_value

이 알고리즘의 핵심 아이디어는 리스트의 일부를 정렬된 상태로 유지하고, 나머지 요소들을 하나씩 올바른 위치에 삽입하는 것이다. 여기서 우리는 다음과 같은 루프 불변성을 정의할 수 있다:

• 루프 불변성(loop invariant) : i번째 반복이 시작될 때, 리스트의 첫 i개 요소(A[:i])는 정렬된 상태이다.

이제 이 불변성을 이용하여 수학적 귀납법을 통해 Insertion Sort의 정확성을 증명해보자. 수학적 귀납법은 다음 네 가지 구성 요소로 이루어진다:

1. 귀납 가설(inductive hypothesis) : i번째 반복 후에 루프 불변성이 성립한다.
2. 기본 경우 (Base Case) : 알고리즘 시작 전 (i=0)에 루프 불변성이 성립한다. 즉, A[:1]은 하나의 요소만 포함하므로 정렬된 상태이다.
3. 귀납 단계(inductive step) : i번째 반복 후 루프 불변성이 성립한다면, (i+1)번째 반복 후에도 루프 불변성이 성립한다.
4. 결론(conclusion) : 마지막 반복 후 루프 불변성이 성립한다면, 알고리즘이 성립한다.

기본 경우는 자명하게 성립한다.

i=0(raw list)

귀납 단계를 증명하기 위해, i번째 반복 후 A[:i]가 정렬되었다고 가정하자. (i+1)번째 반복에서는 A[i]를 A[:i]의 올바른 위치에 삽입한다. 이 과정은 A[:i]의 정렬 상태를 유지하면서 A[i]를 추가하여 A[:i+1]을 정렬된 상태로 만든다. 따라서 (i+1)번째 반복 후에도 루프 불변성은 성립한다.

i=2

마지막으로, 결론을 살펴보자. 마지막 반복(i = n-1) 후에는 루프 불변성에 의해 A[:n]이 정렬된 상태이다. A[:n]은 전체 리스트 A와 동일하므로, 알고리즘은 리스트 A를 정렬된 상태로 만들고, 따라서 정확하다.

i=4(sorted list)

결론

자료구조 시간에 배운 insertion sort를 엄밀히 증명해 보았다. 알고리즘은 문제 상황에 대해 논리적으로 접근하는 것이 중요했다. 이번 시간에는 알고리즘의 정확성을 증명하는 방법으로 불변성을 찾고 수학적 귀납법을 적용해 보았다. 고등학교 때 배운 수학 지식이 이렇게 활용되는 것을 보니 흥미로웠다. 앞으로 알고리즘 과목을 수강하며 수학적 엄밀성에 대해서도 배우고 적용해나가야겠다.

추천글 : 
[자료구조] 왜 자료구조를 배우는가?
(https://hyeonb.blogspot.com/2024/03/blog-post.html)

[알고리즘] Algorithmic Analysis - runtime with asymptotic analysis
(https://hyeonb.blogspot.com/2024/09/algorithmic-analysis-runtime-with.html)