자료구조 및 알고리즘 1 - Arrays, Algorithms, Complexity and Recursion

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다.

 

알고리즘의 완전성을 증명하는 것은 중요합니다. 완전성을 증명하는 방법에는 여러가지가 있습니다. 알고리즘의 단계별로 하나하나 들어가서 이해하고 완전성을 확인하는 방법도 있습니다. 하지만 이는 그리 좋은 방법은 아닙니다. 해당 글에서는 수학적 귀납법을 사용하겠습니다.

 

 

 

 

 

1. 수학적 귀납법

 

임의의 공리 P가 존재한다고 할 때, 수학적 귀납법의 기본형은 다음과 같습니다.

1. P(0) 가 성립한다. (* Base)
2. 임의의 n 에 대하여 만약 P(n) 이 성립한다면, P(n+1) 역시 성립한다. (* Step)

 

수학적 귀납법의 강한 형태도 존재합니다.

1. P(0), P(1), P(2) ... P(n-1) 이 성립한다.
2. P(n) 이 성립한다면, P(n+1) 역시 성립한다.

 

수학적 귀납법에 대표적인 예시인

• 1+2+3+...+n = n(n+1) / 2

를 증명하면서 다시 이해 해보겠습니다.

 

n은 양의 정수이므로 첫 번째 조건인 P(0) 는 P(1) 으로 생각해도 무방합니다.

1. P(1) : n이 1일 때 P(1) 은 1 * (1+1) / 2 = 1 입니다. 따라서 P(1) 은 성립합니다. 즉 초기조건이 성립합니다.
2. P(n-1) 이 성립한다고 가정한다면 P(n) 이 성립하는지 따져봅니다 : P(n-1) = (n-1) * n / 2 여기에 n 을 더해주면 P(n-1)+n = P(n) 이고 따라서 (n-1) * n / 2 + n = n * (n+1) / 2 이므로 P(n) 은 성립합니다.

따라서 수학적 귀납볍에 의해 P 는 참입니다.

 

하지만 이때 궁금증이 생깁니다. 왜 어떤 근거로 P(n-1) 이 성립한다고 가정할 수 있을까? 그 이유는 Vacuous True 때문입니다.

 

 

 

 

 

 

2. 명제 P->Q 의 의미

 

명제 P->Q 가 있다고 했을 때의 진리표를 구해보면 다음과 같습니다.

P가 참	Q가 참	명제는 참
P가 참	Q가 거짓	명제는 거짓
P가 거짓	Q가 참	명제는 참(* Vacuous True)
P가 거짓	Q가 거짓	명제는 참(* Vacuous True)

 

예를 들어보겠습니다.

"시험 점수 100점을 맞으면" "치킨을 아버지께서 사주신다" 라는 명제가 있습니다. 해당 명제에 대한 진리표는 다음과 같습니다.

100점	치킨	참
100점	치킨 안사줌	거짓
80점	치킨	참?
80점	치킨 안사줌	참?

 

80점을 맞았을때 아버지께서 치킨을 사주셨는데 이때 아버지는 약속을 지킨걸까?

80점을 맞았을때 아버지께서 치킨을 안 사주셨으면 아버지는 약속을 지킨걸까?

 

때로는 해당 경우들을 그냥 참으로 생각하는 게 더 나을 수 있습니다.

도데체 뭐가 나을까요?

 

다음 예를 들어보겠습니다.

"만약 n>3 이면 n^2 > 10 이다.(단 n은 양의 정수)" 라는 명제가 있습니다.

 

해당 명제는 자명해보입니다. 당연히 3보다 큰 정수는 제곱하면 10보다 크기 때문입니다.

 

하지만 이때 n=1 인 경우를 생각해봅시다.

이때 명제는 참 인가요?

이 경우 참이 아니라고 했을 때 해당 명제를 설명하기는 복잡해집니다.

참이라고 생각하는게 더 낫지 않을까요?

 

이렇게 명제의 전제가 거짓인 경우 뒤에 뭐가 나오든 참이라고 할 때, 그에 해당하는 참을 Vacuous True 라고 합니다.

 

다시 귀납법으로 돌아오겠습니다.

 

귀납법의 Step 단계의 경우

P(n-1) 이 성립할 때 P(n) 이 성립하는 것을 보이는 것 입니다.

 

이때 P(n-1) 이 거짓인 경우를 생각하는게 의미가 있을까요?

다시 말해 P(n-1) 이 거짓이면 어짜피 뒤에 걸 보지 않아도 Vacuous True 일텐데...

 

 

 

 

 

3. 재귀

 

수학적 귀납법은 재귀로 프로그래밍 상에 구현될 수 있습니다.

간단한 코드 하나를 보겠습니다. 해당 코드는 위에 증명된 명제 1+2+ ... + n 을 구현한 함수입니다.

int sum(int x)
{
	int i, s;
    s = 0
    for(i = 1; i <= x; i++)
   		s += 1;
    return s;
}

 

Base 일 때를 종료조건으로 하고,

Step 을 구현하면 재귀적으로 해당 함수를 구현 가능합니다.

 

int sum(int x)
{
	if(x <= 0) return 0;
    else
    	return x + sum(x-1);
}

 

추가로 재귀를 이해할 때는 재귀함수의 동작을 따라가면서 이해하지 말고 그냥 받아들이면 됩니다.

"종료조건은 이렇고, Step 은 이러면 ... 음 ... 잘 동작하겠네"

 

 

3.1 Time Complexity

 

해당 함수의 시간 복잡도는 어떻게 될까요?

 

T(n) 은 sum(x) 를 돌릴 때 걸리는 시간이라고 할 때,

T(n) = 1 + T(n-1) = 1 + 1 + T(n-2) = ... = n

따라서 T(n) = O(n) 입니다.

 

 

 

 

 

 

4. Arrays

• 정의 : 연속된 주소와 동일한 Type 을 갖는 자료 구조
• 장점 : n 개 중 k 번째 요소 접근을 상수시간에 가능. 탐색이 빠르다.
• 단점 : 크기 변화에 비용이 크다. 삽입 삭제가 느릴 수 있다.
• 사용 : 변화가 없거나 드문 자료

 

4.1 Linear Search(* 선형 탐색)

 

가장 간단한 탐색 방법입니다. 처음부터 끝까지 돌면서 찾고 싶은 요소를 찾습니다.

시간 복잡도는 O(n), 자료의 길이만큼 소모됩니다.

int linearSearch(int a[], int n, int target)
{
	/*
	@param a is array
	@param n is length of array
	@param target is item to search
	@output is index of item in array
	*/
    
    int i;
    for(i = 0; i < n; i++)
    {
    	if(a[i] == target) 
        	return i;
    }
    else
    	return -1;
}

 

 

4.2 Binary Search (* 이진 탐색)

정렬된 자료에서 사용합니다. 시간복잡도가 O(logn) 으로 선형 탐색에 비해 매우 빠릅니다.

 

반복문을 통한 구현과 재귀를 사용한 구현이 있습니다.

// binary search with for loop
int binarySearch(int a[], int n, int target)

	int l, m, r;
    l = 0;
    r = n - 1;
    while(l >= r)
    {
    	m = (l + r) / 2
        if(a[m] == target)
        	return m;
        else if(a[m] > target)
        	r = m - 1;
        else // a[m] < target
        	l = m + 1;
 	}
    return -1;
}

 

해당 탐색을 Invariant 를 통해 증명해보겠습니다.

 

Invariant : 만약 어떤 i 에 대해서 a[i] = target 이라면, l <= i <= r 이 항상 성립한다. 그리고 어떤 경우에도 이 Invariant 가 깨지지 않으면 참이라고 할 수 있다. 해당 코드에서 Invariant 를 깰 코드는 없고, 이는 최초에 성립한다.

 

최초에 l 은 r 보다 작고 i 는 이 두 index 사이에 존재한다. while 은 l 이 r 보다 작거나 같을 때 까지만 반복되니 l > r 일 가능성은 없다. 그리고 i 가 m 보다 작으면 r 을 줄이고, m 보다 크면 l 을 늘려서 i 에 대해 좁혀나간다. 그래서 결국엔 l = i = r 이 성립한다.

 

a[i] = target 인 i 가 없다면 -1 을 return 하고 끝난다.

a[i] = target 인 i 가 있다면 루프 안에서 i 값이 return 된다.