3.1 스택

삽입, 삭제가 top에서만 이루어진다.

LIFO(Last In First Out)

* 시스템 스택: 프로그램이 런타임에 함수 호출 시 사용

처음 top을 -1로 정해 빈 스택 확인

3.1.1 추상자료형

생성

삽입, isFull: 스택이 가득 찼는지 확인한 후 삽입

삭제, isEmpty: 스택이 비어있는지 확인 후 삭제

push(item);
item = pop();

3.2 동적 배열을 이용한 스택

위의 방식처럼 MAX_STACK_SIZE를 통해 스택을 생성하는 경우 최적의 크기를 알아야 한다는 결점 -> 동적 할당된 배열을 통해 해결

처음 스택의 크기를 1로 설정하여 배열 생성

스택이 가득 차있는 경우 realloc( )을 이용하여 기존 스택의 크기를 2배로 증가

: 시간 비용이 많이 드는 것처럼 보이지만 아니다!

​ => 메모리 할당에 O(1), 스택 원소 복사에 O(1)의 시간 복잡도가 요구된다는 가정하에 O(스택_크기)의 시간 복잡도(스택 크기는 2의 멱수)

​ => 2^k^의 원소에 대한 총 시간 복잡도 다음과 같다.
$$
{O(\sum\limits_{i=1}^{k}2^i)} = O(2^{k+1}) = O(2^k)
$$

3.3 큐

삽입과 삭제가 다른 끝에서 발생하는 리스트

삽입되는 끝: rear

삭제되는 끝: front

스택에서는 top만 이용하는 것과 달리 rear, front 2개의 변수 사용

* 작업 스케줄링: 우선순위를 사용하지 않는 OS에서 작업을 들어오는 순서대로 처리

​

3.3.1 추상자료형

생성

삽입, isFull: 큐가 가득 찼는지 확인 후 삽입

삭제, isEmpty: 큐가 비었는지 확인 후 삭제

rear가 MAX_QUEUE_SIZE-1가 됐을 때(큐가 가득 찼을 때), 전체 큐를 이동시켜 front가 -1이 되도록 이동 -> 비용 多

=> 원형 큐를 이용해 해결: (MAX_QUEUE_SIZE-1) + (1) = (0), (0) - (1) = (MAX_QUEUE_SIZE-1) : 모듈러 연산 이용

​ * 원형 큐의 문제점: 큐가 가득 차거나 비어있을 때 모두 rear == front, 구분 불가

​ => 큐가 가득 차기 직전에 큐의 크기를 늘려서 rear == front인 상황이 비어있는 경우만 존재하도록 제한

3.4 동적 할당 배열을 이용한 원형 큐

realloc을 이용해 배열의 크기를 2배로 만들고 추가적인 작업 필요

[0]	[1]	[2]	[3]	[4]	[5]
C	D	E		A	B

front = 3, rear = 2

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]
C	D	E		A	B

front = 3, rear = 2

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]
C	D	E								A	B

front = 9, rear = 2

[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]
A	B	C	D	E

front = 11, rear = 4

1. 새로운 큐 newQueue 생성
2. 뒷부분에 해당하는 queue[front+1]부터 queue[capacity-1]까지를 newQueue[0]부터 newQueue[capacity-front-2]에 복사
3. 앞부분에 해당하는 queue[0]부터 queue[rear]까지를 newQueue[capacity-front-1]부터 newQueue[capacity-front-1+rear]에 복사

3.5 미로 문제

3.6 수식 계산

3.6.1 수식

연산 순서를 결정하는 상위 계층 존재

안쪽 괄호 먼저 계산

C에서의 연산자 순서

1. ->

   ( ): 함수 호출

   [ ]: 배열

   ->, .: 구조체 또는 공용체 멤버

2. ->

   --, ++: 후위 연산자

3. <-

   --, ++: 전위 연산자

   !: not

   ~: 보수

   , +: 단항(부호)

   &, *: 역참조, 참조

   sizeof: 크기(바이트 단위)

4. <-

   (type): typecast

5. ->

   *, /. %: 곱

6. ->

   +, -: 합, 차

7. ->

   <<, >>: shift

8. ->

   >, =>, <, <=: 비교

9. ->

   ==, !=: 등위

10. ->

    &: 비트연산자 and

11. ->

    ^: 비트연산자 xor

12. ->

    |: 비트연산자 or

13. ->

    &&: 논리연산자 and

14. ->

    ||: 논리연산자 or

15. <-

    ?:: 조건연산자

16. <-

    =, +=, -=, /=, %=, <<=, >>=, &=, ^=, |=: 할당

17. ->

    ,: 콤마

3.6.2 전위식

대부분의 컴파일러가 사용하는 수식

계산 시 왼쪽에서 오른쪽으로 스캔

연산자를 만날 때까지 스택에 피연산자 삽입

연산자를 만나면 스택에서 필요한 피연산자를 삭제 후 계산 결과를 삽입

* 입력받은 숫자가 ASCII 값이기 때문에 '0'을 빼서 원하는 값을 갖도록 한다. ex ) '1' - '0' = 1

** 호출되는 함수에서 case문을 사용 시 각 케이스에 return을 사용하면 break 불필요

3.6.3 중위식 -> 전위식

1. 수식의 모든 계산에 괄호
2. 연산자를 닫는 괄호로 이동
3. 괄호 제거

스택을 이용한 수식 전환

괄호가 없는 식

피연산자는 즉시 출력

연산자를 만나면 top에 있는 연산자와 비교하여 우선순위가 낮을 때까지 pop한 후 push

수식의 끝에 도달했을 때 스택이 비어있지 않다면 모두 pop

괄호가 있는 식

위와 동일한 방식으로 진행하되 닫는 괄호가 나올 경우 여는 괄호까지의 연산자 pop

여는 괄호는

• 스택 내부에서의 우선순위(isp)는 가장 낮아야 하고 - 스택에 들어간 이후 다른 토큰이 스택에 들어갈 수 있기 때문
• 삽입 시 우선순위(icp)는 가장 높아야 한다. - 입력 시 반드시 스택에 들어가 위해

분석: O(n)

* 중위식 -> 후위식

1. 입력된 문자열 뒤집기
2. 뒤집어진 문자열을 전위식으로 정리
3. 전위식 뒤집기

3.7 다중 스택과 큐

• m의 메모리에 n개의 스택을 사용하는 경우

  공간을 n등분하여 boundary로 구분 (# of boundary = n+1)

  • top[i] == boundary[i+1]: stackFull
  • top[i] == boundary[i]: stackEmpty
• 다른 스택에 여유 공간이 있는데 꽉 찬 스택(i)에 삽입이 발생하는 경우
  1. 사용하지 않고, i < j < n을 만족하는 최소의 j를 찾아 i+1부터 j까지 오른쪽으로 한 스택씩 이동
  2. 1로 해결되지 않은 경우, 사용하지 않고, 0 <= j < i를 만족하는 최대의 i를 찾아 0부터 i까지 왼쪽으로 한 스택 씩 이동
  3. 2로 해결되지 않은 경우, stackFull

worst case: O(MEMORY_SIZE)

* 단어

• shortcomming 결점
• * This is not the case 사실이 아니다
• intriguing 흥미로운
• precedence 상위
• mnemonics 기억술
• auxiliary 보조적인
• empirically 경험적으로
• futile 쓸모없는

2.1 배열

2.1.1 추상자료형

대부분의 언어가 제공하는 배열의 표준연산: 생성, 검색, 저장

2.1.2 C에서의 배열

배열의 첫 원소의 주소를 base address라고 한다.

int list[5]에서의 base address는 list[0]의 주소
list[i]의 주소는 base address + i*sizeof(int)
(list2+i) = &list2[i], *(list2+i) = list2[i] (자료형의 크기를 곱하지 않는다.)

2.2 동적 할당 배열

2.2.1 1차원 배열

배열의 크기를 매우 크게 정하면
프로그램이 실행 시간에 실패하는 가능성은 떨어지지만,
메모리 부족으로 인해 컴파일에 실패할 가능성 증가

2.2.2 2차원 배열

할당

int **list;

MALLOC(list, rows*sizeof(*list));
// list = (int **)malloc(rows*sizeof(*list));
for(int i = 0; i < rows; ++i)
    MALLOC(list[i], cols*sizeof(**list));
    // list[i] = (int *)malloc(cols*sizeof(**list));

해제

for(int i = 0; i < rows; ++i)
    free(list[i]);
free(list);

calloc: 할당 후 0으로 초기화
realloc: 크기 조정

2.3 구조체와 공용체

2.3.1 구조체

cf ) 배열 - 동일 자료형
필드(멤버)로 구성
멤버 연산자 '.'
typedef 사용
패딩비트 사용

typedef struct _Human{
    char name[10];    // char pad[2]; 패딩비트
    int age;
    float salary;
} Human;

sizeof(Human);    // 20 ( 패딩비트 )

구조체의 대입 연산은 가능하지만 비교 연산은 불가능 // 비교 연산 시 각각의 멤버 변수에 대해서 비교
구조체 멤버로 구조체 사용 가능

2.3.2 공용체

공용체의 필드는 메모리 공간 공유 -> 한 필드만 주어진 시간에 기능을 한다.
크기는 가장 큰 필드의 크기
구조체와 같이 패딩비트 사용

union {
    char name[10];
    int age;
} info;

sizeof(info);    // 12 ( sizeof(name) > sizeof(age), 패딩비트 )

2.3.3 자기 참조 구조체

하나 이상의 멤버가 자신의 포인터인 구조체

typedef struct _List *ListPointer;
typedef struct _List{
    char data;
    ListPointer link;
} List;

2.4 다항식

2.5 희소행렬

2.6 다차원 배열의 표현

다차원 배열을 표현할 때 배열의 배열 꼴이 아닌 선형 리스트의 1차원 배열과 같은 꼴로 나타내는 경우 주소 공식이 복잡해진다.
다차원 배열 a[upper_0][upper_1][upper_2]...[upper_n-1]의 element 수: upper_0*upper_1*upper_2*...*upper_n-1

본 책에서는 다차원 배열의 표현법인 row major order와 column major order 중 row major order만 고려

A[upper_0][upper_1]은 upper_0줄이 각각 upper_1개의 element를 가지고 있는 형태이므로

A[0][0]의 주소를 a라고 할 때, A[i][0]의 주소는 a+i*upper1, A[i][j]의 주소는 a+i*upper_1+j

B[upper_0][upper_1][upper_2]는 upper_0 개의 upper_1*upper_2 2차원 배열로 구성된 형태이므로
B[0][0][0]의 주소를 b라고 할 때, B[i][0][0]의 주소는 b+i*upper1*upper2, B[i][j][k]의 주소는 b+i*upper_1*upper_2+j*upper_2+k

일반화하여, C[upper_0][upper_1]...[upper_n-1]에서
C[0][0]...[0]의 주소를 c라고 할 때,
C[i_0][i_1]...[i_n-1]의 주소는 c+sigma{j=0

n-1}(i_j*a_j), a_j = pi{k=j+1

n-1}(upper_k)

2.7 문자열

2.7.1 추상자료형

생성, 읽기 or 출력, 합성(연쇄), 비교, 삽입, 삭제, 찾기

2.7.2 C에서의 문자열

끝이 널문자(\0)로 끝나는 문자 배열

char s[100] = {"dog"};
// vs
char s[] = {"dog"};

strcat(s, t)를 호출했을 때, s에 t를 추가할 공간이 없다면 overwrite될 가능성 존재

* 참고: http://www.jbox.dk/sanos/source/lib/string.c.html
\ strspn에서의 control map의 비트를 설정하는 부분이 이해가 되지않는다.

insert = strncpy -> strcat -> strcat

2.7.3 패턴 매칭

strstr으로 가능

가장 쉬운 방법은 각 문자에 대해서 순차적으로 비교: O(nm)의 계산 시간 필요
비교하는 문자열의 길이를 고려하는 것으로 1차 개선
첫, 끝 글자를 비교하여 2차 개선
2번의 개선하더라도 최악의 경우에는 O(nm)의 계산 시간 필요

KMP 알고리즘의 계산 시간은 O(n+m)
\ KMP 알고리즘

* 단어

• sparse 부족한
• consecutive 연속적인
• retrieve 검색하다
• bracket 대괄호
• abbreviate 줄여 쓰다
• retrieve 검색하다
• stipulation 약정

1.1. 시스템 생명 주기

1.1.1 요구사항

모든 대형 프로그래밍 프로젝트는 프로젝트의 목적을 정의한 명세로부터 시작
입력과 출력에 대한 정보

1.1.2 분석

접근법 : 상향식(bottom-up), 하향식(top-down)

• 상향식 : 프로그래머의 master plan 없음 -> 각 프로그램의 연관이 적고, 에러를 발생시키는 부분 많다.
• 하향식 : 최종 제품을 관리할 수 있는 부분으로 나눔, 문제에 대한 대안책을 개발하고 비교하는 단계

1.1.3 설계

프로그램에 필요한 데이터 오브젝트와 동작 관점에서 접근

• 데이터 오브젝트 관점 : ADT(추상 데이터 타입)
• 동작 관점 : 알고리즘과 알고리즘 설계 전략

1.1.4 구현

데이터 오브젝트 표현 방법 선택, 관련된 효율적인 알고리즘 결정

1.1.5 검증

• 정확성 증명 : 증명은 시간이 오래 걸리고 어려움 -> 증명된 알고리즘을 선택하여 에러 감소

  코딩 전 또는 중간에 가능

• 테스트 : 동작하는 코드와 테스트 데이터 필요, 테스트 데이터는 모든 가능한 케이스를 포함

  running time도 중요

• 에러 제거 : 설계와 코딩에 따라 쉬워진다.

1.2 포인터와 동적 메모리 할당

1.2.1 포인터

포인터형의 값은 메모리 주소

• & : 주소 연산자
• * : 역참조 연산자

int i, *pi;
pi = &i;

사칙연산과 비교 연산 가능

크기는 컴퓨터(OS)에 따라 다르다.

※ null pointer는 아무것도 가리키지 않는 상태 -> 역참조 불가

if(!ptr)
    ptr = malloc();

1.2.2 동적 메모리 할당

공간을 예측할 수 없을 때 heap 구조를 사용하여 런타임에 할당

• malloc() : 성공 시 시작 포인터, 실패 시 null 리턴
• free() : 메모리 해제, 일반적으로 자료형 생략

메모리 부족으로 인한 malloc 실패를 위한 전처리

#define MALLOC(p, s) \
    if(!((p) = malloc(s)) { \
        fprintf(stderr, "Insufficient memory");    \
        exit(EXIT_FAILURE);    \
    }

동적으로 할당된 위치를 잃게 되면 허상 포인터(dangling pointer)가 될 수 있다.

원인과 해결

무질서한 malloc()과 free() 호출 -> free() 이후 NULL로 리셋,

스택에 할당된 지역 변수의 주소를 리턴하는 경우 -> static으로 정의

1.2.3 포인터의 위험성

포인터 자료형의 형 변환 주의

1.3 알고리즘 명세

1.3.1 도입

• 입·출력
• 명확성, 유한성, 효율성

알고리즘 - 프로그램 : 유한성 O - X

예제 1 - 선택 정렬

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

※ 정수형 한정 (^연산자 활용)

#define SWAP(a, b) ((a)^=(b), (b)^=(a), (a)^=(b))

※ math.h 라이브러리 함수 rand()는 프로그램을 실행할 때마다 같은 결괏값을 내기 때문에 다른 값을 원한다면

srand(time(NULLL))을 사용할 수 있다.

예제 2 - 이진 탐색

#define COMPARE(x, y) (((x) < (y)) ? -1 : ((x) == (y)) ? 0 : 1))
while(left <= right){
    middle = (left + right) / 2;
    switch(COMPARE(list[middle], searchNum)){
        case -1 : left = middle + 1;
            break;
        case 0  : return middle;
        case 1  : right = middle-1
    }
}

c에서는 함수의 그룹이 따로 컴파일 가능 -> 논리적으로 관련된 알고리즘의 그룹을 포함하는 라이브러리 생성

1.3.2 재귀 알고리즘

예제 3 - 이진 탐색

if(left <= right){
    middle = (left + right) / 2;
    switch(COMPARE(list[middle], searchNum)){
        case -1 : return binsearch(list, searchnum, middle + 1, right);
        case 0  : return middle;
        case 1  : return binsearch(list, searchnum, left, middle - 1);
    }
}

예제 4 - 순열

for(j = i; j <= n; ++j){
    SWAP(list[i], list[j]);
    perm(list, i+1, n);
    SWAP(list[i], list[j]);
}

※ 재귀 함수 종류

• 원시 재귀 함수 : 반복 수를 앎 -> for loop 가능
• 일반 재귀 함수 : 반복 수 모름 -> for loop 불가 ex) 아커만 함수 (stack을 사용하여 해결 가능)

1.4 데이터 추상화

1.4.1 데이터 그룹화

• 배열 : 같은 자료형
• 구조체 : 다른 자료형

1.4.2 자료형 : 객체 + 연산자

종류

• 이미 정의된 자료형 ex) char, int, float, double, ...
• 사용자 정의 자료형

추상 자료형(ADT)

명세와 표현, 실행이 별개

명세 구성 : 함수명, 매개변수명, 반환형, 기능 (내부 표현, 세부 구현 X)

• 생성자(Creator / Constructor) : 새 인스턴스 생성, 필드 값 초기화
• 설정자(Transformers) : 필드 값 변경
• 접근자(Observers / Reporters) : 인스턴스에 대한 정보 제공 (변경 X)

※ Class / Object / Instance

• 붕어빵 틀 - Class
• 붕어빵 - Object
• 각 붕어빵 - Instance
• 붕어빵 굽기 - Instance화

※ ADT 정의

• 이름
• Object
• Function

1.5 성능 분석

1.5.1 공간 복잡도 : 완전히 실행하기 위해 필요한 메모리량

• 고정 공간 : 명령 공간(코드) + 변수(구조체, 상수)
• 가변 공간 : 각 인스턴스, 재귀 시 추가

공간 복잡도 분석 시 주로 가변 공간만 고려

언어에 따라 가변 공간의 크기가 다를 수 있다.

• 파스칼 : 배열 전달 시 값으로 전달 -> 가변 공간 O
• C : 배열 전달 시 주소로 전달 -> 가변 공간 X

1.5.2 시간 복잡도 : 완전히 실행하기 위해 필요한 시간

컴파일 시간 + 런타임

컴파일 시간은 인스턴스에 영향이 없으므로 거의 고정, 잘 동작하면 재컴파일 없이 실행

-> 시간 복잡도 분석 시 주로 런타임만 고려

system clock을 사용하여 측정 가능 -> 대안으로 연산 수

program step : 문법적으로, 의미적으로 의미 있는 세그먼트

(간단히 할당하는 문장 = 복잡한 계산 문장 = 한 단계)

재귀가 반복문에 비해 연산 수가 적을 수는 있지만 주로 더 느리다.

예제 11 - 행렬 합

rows x columns 행렬의 합의 경우 (2rows+1)*columns+1 회 연산, 즉 열이 큰 것이 행이 큰 것에 비해 영향이 크다.

-> "행 >> 열"인 경우 행렬을 바꿔줘야 한다.

Tabular method : Total = ∑Total steps = ∑( Steps/Execution(s/e) * Frequency )

• best case
• worst case
• average

1.5.3점근적(Asymptotic) 표기법

1 Big 'oh' : 상한

정의 : f(n) = O(g(n)), f(n) ≤ c * g(n)을 n>= n0에서 항상 만족시키는 양수 c가 존재한다.

예시 : 3n + 2 = O(n), 3n + 3 = O(n^2), 3n + 4 ≠ O(1)

교환 법칙 X

2 Omega : 하한

정의 : f(n) = Ω(g(n)), f(n) ≥ c * g(n)을 n>= n0에서 항상 만족시키는 양수 c가 존재한다.

예시 : 3n + 2 = Ω(n), 3n + 3 = Ω(1), 3n + 4 ≠ Ω(n^2)

교환법칙 X

3 Theta : 상한 & 하한

정의 : f(n) = θ(g(n)), c1 * g(n) ≤ f(n) ≤ c2 * g(n)을 n>= n0에서 항상 만족시키는 양수 c1, c2가 존재한다.

예시 : 3n + 2 = θ(n), 3n + 3 ≠ θ(1), 3n + 4 ≠ θ(n^2)

1.6 성능 측정

1.6.1 시간

라이브러리 함수 사용

1.6.2 테스트 데이터 생성

최악의 경우의 데이터셋을 만드는 것이 어려울 때 무작위 케이스 중 최악

평균 시간은 항상 구할 수 있는 것은 아니다.

* 단어

• rudiment 기본
• fleeting 순식간의
• rigorous 엄밀한
• delineate 묘사하다
• earnest 진지한
• akin 비슷한
• scrap 폐기하다
• abound 풍부하다
• arsenal 무기
• constraint 강제
• erroneous 잘못된
• feasible 실행할 수 있는
• flowchart 순서도
• discrepancy 모순
• syntactically 문법적으로
• semantically 의미적으로
• decipher 풀다
• extricate 구해 내다
• elapse 경과하다
• legitimate 본격적인

책 링크

이 카테고리에는 부족한 영어실력으로 원서로 자료구조를 공부하면서 정리한 내용을 올릴 예정이다.

추가로 기억하고 싶은 내용이나 책에 나오는 모르는 영단어도 정리 예정이다.