알고리즘과 수학적 귀납법

난1렙이요·2024년 9월 3일
알고리즘학교 공부

알고리즘

목록 보기
2/15

  고등학교 시절에도 배웠지만, 수학적 귀납법은 알고리즘의 기초이자 명확히 지켜야 할 규칙임.

수학적 귀납법의 기본형

수학적 귀납법의 기본형 : P(1)이 참이고, P(n-1) -> P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.
여기서 P(1)은 Base, P(n-1) -> P(n)은 Step이라 함

Example

  • P(x) == "x>0" 일 때
  • P(1) == "1>0" == true
  • P(n-1) == "n-1>0" == "n>1"
  • P(n) == "(n+1)-1>0" == "n>0"
  • P(n-1) == true => P(n) == true

수학적 귀납법의 강한 형태

수학적 귀납법의 기본형 : P(1)이 참이고, P(1), P(2), ... P(n-1) -> P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

좀 더 엄격한 형태. 대부분 기본형을 쓰므로 알고 있기만 하자

명제와 공허참

P(n-1) -> P(n)에서 P(n-1)이 true인지, false인지는 관계가 없음.

명제 P->Q의 의미

  • P가 참, Q가 참 -> 전체는 참
  • P가 참, Q가 거짓 -> 전체는 거짓
  • P가 거짓, Q가 참 -> 전체는 참 ????
  • P가 거짓, Q가 참 -> 전체는 참 ????
PQtruth
truetruetrue
truefalsefalse
falsetruetrue
falsefalsetrue

P가 참이든, 거짓이든, 상관이 없다! P가 거짓일때를 공허참(vacuous truth)이라고 함.

P : 7시에 일어난다, Q : 학교에 간다
여기서 명제 P -> Q는 하나의 약속이다. P라는 조건이 발생했을 때, Q를 지켰는가? 다시 말해 약속을 지켰는가?

  • 7시에 일어나서 학교에 갔다 -> P == true 일 때 Q == true이므로 true
  • 7시에 일어났지만 학교에 가지 않았다 -> P == true 일 때 Q == false이므로 false
  • 7시에 못 일어나서 학교에 갔다/가지 않았다 -> P == false 약속의 전제 자체가 깨졌으므로 학교에 가든, 가지 않든 상관이 없음.
  • 다시 말해 전제 자체가 깨지면 정확히 알 수 있는 방법이 없으므로 true라고 하는 것. 그러나 약속을 지킨 것은 아니므로 공허참(vaccum truth)라고 하는 것

n이 자연수이고, n>3 일때, n^2>10인 것은 모두 동의 할 것임. 이 때 n = 1인 것은 고려할 필요가 없으며, 공허참이라고 하는 것

"P(1)이 참이고, P(n-1) -> P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다." 에서 P(n-1)이 참일때만 P(n)이 참인지를 확인하면 된다. P(n-1)이 거짓이면 말 할 필요가 없기 때문

재귀와 명제(정확성)

일반적으로 1부터 x까지 더하는 코드

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

재귀를 이용한 1부터 x까지 더하는 코드

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

sum(3)을 하면 어떻게 될까? sum(3) -> sum(2) -> sum(1) -> sum(0) -> 0 -> 1 -> 2 -> 3... 이렇게 될 것이다. 이것은 따라 들어가는 방법인데, 재귀에서는 별로 효율적이지 않다. 만약 sum(1000)을 하면? 그렇기에 우리는 재귀에서 증명의 방법을 통해 푸는것이 더 좋다.

  • 수학적 귀납법 : sum(x)는 1+2+...+x를 리턴한다(항상)
    • Base : sum(1)은 1을 리턴한다.
    • Step : sum(x-1) -> sum(x)을 증명하면 된다.
      다시 말해 "sum(x-1)이 1+2+...+x-1"을 리턴하면 "sum(x)은 1+2+...+x"를 리턴한다는 것을 증명하면 된다.
      여기서 sum(x-1)이 거짓이면 증명을 할 필요가 없다. 그러므로 sum(x-1)이 사실이라고 가정을 하고 말하자.
      • sum(x)는 x + sum(x-1)을 리턴한다. sum(x-1)은 1+2+...+x-1와 같다고 가정했으므로 sum(x) 는 x+1+2+...+x-1이므로 1+2+...+x라고 말할 수 있다.
      • sum(x-1)이 1+2+...+x-1은 신경 쓸 필요가 없으므로 성립한다.

그러므로 sum(x)는 1+2+...+x를 리턴한다.

시간복잡도

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

재귀식을 복잡도로 표현하려면 식이 필요하다.

r(n) = 1 + r(n-1)
	 = 1 + 1 + r(n-2) = ... = n
     ∴r(n) = O(n)

이진 탐색

일반적인 이진탐색

int search(int a[], int n, int x){
	int l, r, m;
    l = 0;
    r = n-1;ㅣ
    while(l <= r){
    	m = (l+r)/2;
        if(a[m] == x) return m;
        else if(a[m] > x) r = m-1;
        else l = m+1;
    }
    return -1;
}
  • Invariant(불변) : 만약 어떤 i에 대해서 a[i] == x라면, l <= i <= r이 항상 성립한다.
    • Invariant는 최초에 성립하고, 깨질 수 있는 코드는 없음.

재귀적인 이진탐색

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

  • Invariant(불변) : 만약 어떤 i에 대해서 a[i] == x라면, l <= i <= r이 항상 성립한다.

    • Invariant는 최초에 성립하고, 깨질 수 있는 코드는 없음.

  • 수학적 귀납법 : 만약 어떤 i에 대해 a[i] == x 면 i를 리턴한다.

    • Base : n==0이면 어떤 i에 대해서 a[i] == x가 성립할 방법이 없고, 함수는 항상 -1을 리턴한다.
    • Step
      • Case 1 : a[m] == x면 m을 리턴
      • Case 2 : a[m] > x면 a[m], a[m+1], ... a[n]중 x와 같은 값은 없다.(정렬되어 있기 때문) 따라서 a[i] == x가 되려면 a[0], a[1], ... ,a[m-1] 중 하나다. 귀납적으로 search(a, m-1, x)가 정확하다고 가정하면 성립한다.
      • Case 3 : 반대로 a[m] < x면 a[0], a[1], ... a[m-1]중 x와 같은 값은 없다.(정렬되어 있기 때문) 따라서 a[i] == x가 되려면 a[m+1], a[m+2], ... ,a[n] 중 하나다. 귀납적으로 search(a+m+1, n-m-1, x)가 정확하다고 가정하면 성립한다.

  • 시간복잡도

r(n) = 1 + r(n/2)
	 = 1 + 1 + r(n/4) = ... = log n
     ∴r(n) = O(log n)

선택 정렬

일반적인 선택정렬

int sort(int a[], int n)
{
	int i, j, m, t;
    for (i = 0; i < n; i++){
    	m=i
    	for(j = i; j < n; j++){
        	if(a[m] > a[j]) m==j;
        }
        t = a[i];
        a[i] = a[m];
        a[m] = t;
    }
    return;
}

입력 : a[0], a[1] ... a[n-1]

Sorting이 완료된 후 저장된 값들을 b[0], b[1], ... b[n-1]이면

  • {a[0], a[1] ... a[n-1]} = {b[0], b[1], ... b[n-1]}

  • b[0] < b[1] < ... < b[n-1]

  • Invariant(불변) : k번째 루프가 끝났을 때

    • a[0] < a[1] < ... < a[k-1] -> a[0] < a[1] < ... < a[n-1]
    • a[k-1] < a[x] if x > k-1

    BASE : k = 0이면 P가 거짓이므로 true(vacouse true)
    STEP :
    k번째 루프가 끝났을 때

    • a[0] < a[1] < ... < a[k-1] -> a[0] < a[1] < ... < a[n-1]
    • a[k-1] < a[x] if x > k-1

    k+1번째 루프가 돌고 있을때

    • a[k], a[k+1] ... a[n-1]중 최솟값을 a[k] 자리로 옮김

    k+1번째 루프가 끝났을 때

    • a[0] < a[1] < ... < a[k-1] < a[k]
    • a[k] < a[x] if x > k

재귀적인 선택정렬

int sort(int a[], int n)
{
	int i, j, m, t;
    m = 0;
    for (i = 0; i < n; i++){
    	if(a[m] > a[j]) m = j;
    }
    t = a[0];
    a[0] = a[m];
    a[m] = t;
    sort(a+1, n-1);
    return;
}

BASE : n=1이면 1개를 정렬하는 것이므로 할 게 없음. TRUE
STEP :
n-1번째 루프가 끝났을 때 sort()함수가 성공한다면

  • 즉, a[1] < a[2] ... < a[n-1]이면

n번째 루프가 끝났을 때 sort()함수가 성공한다.

  • a[0] < a[1] < a[2] ... < a[n-1]

병합 정렬

int sort(int a[], int n)
{
	int h;
    int b[n];
    h = n/2;
    //copy a[] to b[]
    sort(b,h);
    sort(b+h, n-h);
    // Merge two halves in b to a
    return;
}

base : n=1. 할 일이 없음
step : n/2일때, 재귀 호출이 성공한다면

  • 즉, 재귀 호출이 끝난 뒤 b[0] < b[1] < ... <b[n/2] 이고, b[n/2+1] < ... < b[n]이면

n일땐 재귀 호출이 성공한다.
b[0] < b[1] < ... <b[n/2] < b[n/2+1] < ... < b[n]이다.

퀵 정렬

int qsort(int a[], int n)
{
	int d;
    int p = a[0];
    Rearrange a[] so that
    //a[d] == p,
    //a[0], a[1], ... , a[d-1] < p
    //a[d+1], a[d+2], ..., a[n-1] > p
    qsort(a,d);
    qsort(a+d+1, n-d-1);
    return;
}
profile
난1렙이요
다크 모드의 노예
이전 포스트

알고리즘 개요와 홀팅 문제(The HALTING Problem)

다음 포스트

Prim Algorithm

0개의 댓글