1장: 기본 개념

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 본격적인