[자료구조] 자료구조개론

- 본격적인 자료구조에 대해 배우기 전에 자료구조를 익히기 위한 사전 지식을 배워보자.
- 여러 부분을 다뤄야해서 다소 광범위한 느낌이 있다.
- 모든 코드는 C++이 기준이다.

변수

int a = 129;

• 변수는 기본적으로 위와 같이 선언한다.
• 변수는 a와 같은 이름과 위 코드에서는 보이지 않지만 해당 값이 저장된 메모리 상의 주소, int와 같은 자료의 타입으로 구성된다고 할 수 있다.
• 이 중 특히 타입은 해당 값의 '크기'와 '해석 방법'을 정의하기 때문에 중요하다. (int는 4바이트의 크기를 가지고 숫자로 해석되지만, char는 1바이트의 크기를 가지고 아스키 코드를 통해 문자로 해석된다.)

포인터

int a, x;
int *p, *r;
int **q;
x = a + *p; // 가능
q = p + q; // 불가능
p = p + r; // 불가능 -> 일반적으로 의미가 없다. 
a = p - r; // 가능 -> 때때로 의미가 있다. (주소A와 주소B 사이의 거리)
p = p + 3; // 가능 

• 포인터는 타입이 주소인 변수라고 할 수 있다. 변수 자체를 주소로 해석한다.
• 앞에 붙은 int는 해당 변수 자체의 타입이라기 보단 메모리 상의 해당 주소로 이동했을 때 해당 주소에 어떤 타입에 변수가 있을지를 표기한 것이다. (크기가 얼마인지, 해석은 어떻게 하는지)
• 이러한 포인터 변수를 사용할 때, '*'를 붙이면 해당 변수의 주소에 있는 값을 가져온다.
• '**'도 가능하다. 이렇게 하면 *p로 가져온 값을 주소값으로 보고 처리한다. 즉, *p로 불러온 값이 300이라면 300번지의 값을 불러오는 것ㄷ이다.
• 일반적인 변수에 '&'를 붙이면 이러한 포인터 변수에서 활용할 수 있는 주소값을 가져온다.
• 주소에 일정 수를 더할 때 시스템적으로 해당 수만큼 더해지지 않고 자료형인 'int의 크기 * 해당 수'만큼 더해진다. 이는 시스템상에서 정해진 것이다.

수학적 귀납법과 알고리즘

- 수학적 귀납법

"P(1)이 참이고, P(N-1) -> P(N)이 참이면 P(N)은 모든 자연수 N에 대해 참이다."

이 때 P(1)을 Base, P(N-1) -> P(N)을 Step이라 한다.

 

- P -> Q의 의미

중간고사를 잘보면 치킨을 사주어야 한다.

• P가 참이면 Q가 참이다 -> 전체는 참이다. (중간고사를 잘봐서 치킨을 사줬다. -> OK)
• P가 참이면 Q는 거짓이다. -> 전체는 거짓이다. (중간고사를 잘봤는데 치킨을 안 사줬다. -> NO)
• P가 거짓이면 Q는 참이다. -> 전체는 참이다. (중간고사를 못봤는데 치킨을 사줬다. -> OK)
• P가 거짓이면 Q는 거짓이다. -> 전체는 참이다. (중간고사를 못봤는데 치킨을 안사줬다. -> OK)

여기서 해당 명제의 의미는 중요하지 않다. 의미가 없어도 참,거짓은 존재할 수 있다.

만약 P가 거짓이라면, 전체가 참이 되기 때문에 더 이상 증명할 수 없다. (물론 여기서의 전체는 의미가 없다.)
따라서 P는 무조건 참이라고 믿고, Q에 대한 증명을 행한다.

 

(EX)

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

전체 증명인 'sum(x)는 항상 1부터 x까지의 합을 리턴한다.'를 증명하기 위해서는
base : sum(1) = 1이 참임을 증명하고,
step : sum(x-1)은 무조건 참이라고 믿고, sum(x)에 대한 증명을 행하면 된다.

배열

• 정의 : 연속된 주소, 동일한 타입
• 장점 : n개 중 k번째 access가 상수 시간 내에 처리됨. 따라서 search가 빠름
• 단점 : 크기변화에 대한 비용이 크다. 따라서 insert나 delete가 느릴 수 있다.
• 사용 : 변화가 없거나 드문 자료

이진 검색에 대한 증명

- 반복문으로 구현한 코드에 대한 증명

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에 의한 증명을 사용한다.
invariant : 만약 어떤 i에 대해 a[i] = x 이면 l <= i <= r 이 항상 성립한다.

(해당 invariant는 최초에 성립하고, invariant가 깨질 수 있는 코드가 없다는 것을 증명한다.)
a[i] = x 인 i가 없다면 루프 종료 후 -1을 리턴한다.
a[i] = x 인 i가 있다면 반드시 루프 안에서 끝난다.

 

- 재귀로 구현한 코드에 대한 증명

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

주장 : 어떤 i에 대해 a[i] = x 라면 위 함수는 i를 리턴한다
Base : n = 0 인 경우 함수는 -1을 리턴한다.
Step :

• a[m] = x 의 경우 m을 리턴하므로 주장이 성립된다.
• a[m] > x 인 경우 a[m],a[m-1],...,a[n-1] 중 x와 같은 값이 없고 따라서 a[i] = x 인 경우가 있다면 i는 0,1,...,m-1 중 하나이다. 귀납적으로 search(a, m-1, x)가 정확하다고 가정하면, 주장은 성립된다.
• a[m] < x 인 경우도 비슷하다.

-> 보통 증명을 행할 땐 invariant와 귀납법 모두를 활용하여 증명을 행한다. 위에선 invariant를 자연스럽게 당연하다고 인지하고 증명을 처리했지만, 그래선 제대로 증명을 했다고 할 수 없다. 따라서 전체 원리를 꿰뚫는 invariant를 찾고 해당 invariant를 귀납법을 통해 증명해낸다.