[C++ 자료구조론] 1장 기본 개념

대형 컴퓨터 시스템

💡 설계 및 구현 방법론

• 데이터 추상화
• 알고리즘 명세
• 성능 분석과 측정

대형 컴퓨터 프로그램

• 복잡하게 상호작용하는 부품들로 구성된 시스템 like 하드웨어
• 시스템 생명 주기가 있음 why? 유지보수를 위해

 

시스템 생명 주기 System Life Cycle

💡 요구사항 - 분석 - 설계 - 정제와 코딩 - 검증 (과정을 하나라도 생략하면 안 된다.)

• 요구사항 requirement
  • 프로젝트들의 목적을 정의한 명세들의 집합
  • 고객의 요구에 맞게 입력과 출력에 관한 정보를 기술
• 분석 analysis
  • 문제들을 다룰 수 있는 작은 단위들로 나눔 = 분할 정복 Divide and Conquer
  • 상향식 bottom-up VS 하향식 top-down
    • 상향식은 C의 함수처럼 기능 위주로 나눈다. 버그 난 곳을 찾기 어렵다
    • 하향식은 C++의 class처럼 객체 위주로 나눈다 → 객체지향
• 설계 design
  • 추상 데이터 타입 Abstract data type 생성
    • 메모리를 적게 차지하고 처리 시간을 빠르게 하는 게 목표 → 데이터 추상화 필요
    • so 자료구조의 핵심은 데이터 추상화!
    • 데이터 추상화는 이 데이터가 무엇이고 어떻게 구현할 것인가를 명확하게 구분하는 것
  • 알고리즘 명세와 설계 기법 고려
• 정제와 코딩 refinement and coding
  • 데이터 객체에 대한 표현 선택 → 알고리즘의 효율성 결정
  • 수행되는 연산에 대한 알고리즘 작성
• 검증 verification
  • 정확성 증명 correctness proof
    • 수학적 기법들을 이용해서 증명
    • 대형 시스템의 완벽한 증명이 어려움 → 정확성이 증명된 알고리즘 선택
  • 테스트 testing
    • 프로그램의 정확한 수행 검증
    • 프로그램의 성능 검사
  • 오류 제거 error removal
    • 독립적 단위로 테스트 후 전체 시스템으로 통합

 

객체 지향 설계

객체 지향적 분해

• 응용 분야의 개체를 모델링하는 객체의 집합
• 소프트웨어의 재사용성 조장
  • 예) 학생 객체를 상담 프로그램에도, 수강신청에도 사용할 수 있다.
• 변화에 유연한 소프트웨어 시스템
• 직관적
  • 직관적 → 프로그래머가 이해하기 쉬운 코드 → 유지보수가 쉽다.

기본 정의와 개념

• 객체 object
  • 계산을 수행(함수)하고 상태(변수)를 갖는 개체
  • 데이터 + 절차적 요소
  • 모든 객체는 클래스에 속함.
• 객체 지향 프로그래밍 object-oriented programming
  • 객체는 기본적인 구성단위 building block
  • 각 객체는 어떤 타입(클래스)의 인스턴스 instance
  • 클래스는 상속 inheritance 관계로 연관됨
    • 상속은 코드 재사용성이 높음

 

C++

역사

• FORTRAN → Pascal, C → Modula → Smalltalk, Objective-C, C++
• C의 장점
  • 효율성 - 하드웨어 직접 제어 가능
  • 유연성 - 대부분의 응용 분야에 사용 가능
  • 가용성 - 모든 컴퓨터에 C 컴파일러 존재

데이터 타입

• 데이터 타입 data type
  • 객체들과 이 객체들에 대한 연산 operation의 집합
• C++ 데이터 타입
  • 기본 데이터 타입
    • char, int, float, double
    • • 수식어 short, long, signed, unsigned
  • 파생 데이터 타입
    • pointer, reference
  • 데이터를 묶어주는 구조
    • array, struct, class
    💡 배열 array를 설명하시오. 인덱스로 데이터에 접근할 수 있고, 같은 자료형을 담은 자료구조 - 메모리를 연속적으로 사용하지 않을 수도 있다.
  • 추상 데이터 타입 abstract data type; ADT
    • 객체와 연산에 대한 명세가 객체의 표현과 연산의 구현으로부터 분리된 방식으로 구성된 데이터 타입

기초

• C++ 프로그램의 구성
  • 헤더 파일
    • .h 접미사
    • 선언 저장에 사용 - 추상화되어 있음
    • 시스템/사용자 정의 파일
    • 전처리기 명령 #include를 사용하여 파일에 포함시킴
  • 소스 화일
    • .cpp 접미사
    • 소스 코드 저장에 사용
• 프로그램 실행 과정
  • 컴파일 → 링크 → 적재
• 포인터 선언
  • 객체의 메모리 주소 저장

  int i=25;
  int *np = &i;

• 참조 타입 선언
  • 객체에 대한 또 다른 이름을 제공

  int i=5;
  int& j=i;
  i=7;
  printf(“i=%d, j=%d”, i, j);  // i=7, j=7

• 파일 입출력
  • 헤더 화일 fstream 필요

  #include <iostream>
  #include <fstream>
  
  main(){
      ofstream outFile("my.out", ios::out);
      if (!outFile){
          cerr << "cannot open my.out" << endl; //표준 오류 장치
          return;
      }
      int n = 50; float f = 20.3;
      outFile << "n: " << n << endl;
      outFile << "f: " << f << endl;
  }

• 매개변수 전달
  • 값에 의한 전달
    • 전달된 객체는 그 함수의 지역 저장소에 복사
    • 실인자에 영향을 주지 않음
  • 참조에 의한 전달
    • 인자 리스트의 타입 명세자에 & 첨가
    • 전달된 객체의 주소만 함수의 지역 저장소에 복사
    • 실인자에 직접 접근
    • 전달된 객체가 큰 메모리를 요구하는 경우 더 빨리 수행
  • 상수 참조
    • 인자 변경 불가
    • const T& a
• 함수 다중화 function overloading
  • 함수의 인자 리스트가 다르기만 하면 같은 이름을 가진 함수가 둘 이상 존재할 수 있음
• inline 함수
  • 함수 정의에 키워드 inline을 첨가해서 선언
  • 함수 호출과 인자 복사의 오버헤드를 줄임
    • why? 함수를 부르는 게 아니라 코드에 직접 대입하기 때문
• new/delete 연산자
  • 실행 시간에 heap를 할당받거나 반환
  • new 다음에 반드시 delete를 해야 한다.
• 예외 처리
  • try 블록에 발생할 수 있는 예외를 포함시켜서 처리
  • catch 블록은 예외 타입을 나타내는 한 인자를 가짐
• union
  • 제일 큰 멤버에 맞는 저장장소 할당
  • 보다 효율적인 기억 장소 사용
• static(정적) 클래스 데이터 멤버
  • 클래스에 대한 전역 변수 → 모든 클래스 객체가 하나의 사본을 공유
  • 클래스 외부에서 정의

 

데이터 추상화와 캡슐화

• 데이터 캡슐화 data encapsulation
  • 정보 은닉 information hiding like private, protected
  • 외부로부터 데이터 객체의 자세한 구현을 은닉
    • why? 굳이 보여줄 필요도 없고, 아무나 보고 수정하지 못하도록
• 데이터 추상화 data abstraction
  • 객체의 명세 specification와 구현 implementation을 분리
  • 무엇 what과 어떻게 how를 명확하게 구분
• 장점
  • 소프트웨어 개발의 간소화
    • 복잡한 작업을 부분 작업들로 분해
  • 테스트와 디버깅
    • 각 부분 작업을 독자적으로 테스팅, 디버깅
    • 버그 검사할 부분이 줄어든다.
  • 재사용성
    • 자료 구조에 대한 코드와 연산을 추출해서 다른 소프트웨어 시스템에서도 사용
  • 테이터 타입의 표현에 대한 수정
    • 테이터 타입의 내부 구현에 직접 접근하는 연산들만 수정

 

알고리즘

알고리즘 algorithm

• 특정 작업을 수행하는 명령어들의 유한 집합
• 요건
  • 입력 : 외부에서 제공되는 데이터가 0개 이상
  • 출력 : 적어도 한 개 이상의 결과 생성
  • 명확성 : 각 명령은 명확하고 모호하지 않아야 함
  • 유한성 : 알고리즘대로 수행하면 어떤 경우에도 반드시 종료
  • 유효성 : 반드시 실행 가능해야 함

선택 정렬

• n ≥ 1 개의 서로 다른 정수의 집합을 정렬
• 정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 놓는다
• a[i]에서부터 a[n-1]까지의 정수 값을 검사한 결과 a[j]가 가장 작은 값 a[i]와 a[j]를 서로 교환한다.

void SelectionSort(int *a, const int n) {
    // n개의 정수 a[0]부터 a[n-1]까지 비감소 순으로 정렬한다.
    for (int i = 0; i < n; i++) {
        int j = i;

        // a[i]와 a[n-1] 사이에 가장 작은 정수를 찾는다.
        for (int k = i + 1; k < n; k++)
            if (a[k] < a[j]) j = k;
        swap(a[i], a[j])
    }
}

이원 탐색

• 이미 정렬된 배열 a[0]...a[n-1]에서 x = a[j]인 j를 반환
• a[middle]과 x를 비교해 범위 재설정
  • x < a[middle] → right = middle-1
  • x == a[middle] → middle 반환
  • x > a[middle] → left = middle+1

int BinarySearch (int*a, const int x, const int n)
{// Search the sorted array a[0],…,a[n-1] for x.
    int left=0, right =n-1;

    while (left <= right) {// there are more elements
        int middle = (left+right)/2;

        if (x < a[middle]) right = middle-1;
        else if (x > a[middle]) left = middle+1;
        else return middle;
    }

    return -1; // not found
}

Recursive 알고리즘

• 수행이 완료되기 전에 자기 자신을 다시 호출
• 기술 방법
  1. 주어진 입력에 대해 함수가 마땅히 수행해야 할 작업에 대한 명령문 구성
  2. 자신에 대한 재귀적 호출이 제대로 이루어질 때 목적을 달성할 수 있는지 검증
  3. 함수를 유한한 횟수로 순환 호출하면 완료 조건을 만족시키는지 확인
  4. 완료 조건을 만족시켰을 때 함수가 올바른 계산을 하는지 확인

int BinarySearch(int *a, const int x, const int left, const int right)
{//정렬된 배열 a[left], ..., a[right]에서 x 탐색
    if(left <= right){
        int middle = (left + right) /2;

        if(x < a[middle]) return BinarySearch(a, x, left, middle-1);
        else if(x > a[middle]) return BinarySearch(a, x, middle+1, right);
        return middle;
    }
    return -1; //발견되지 않음
}

순열 생성기

• 주어진 집합의 모든 가능한 순열 출력

void Permutations(char *a, const int k, const int m)
{// a[k], ..., a[m]에 대한 모든 순열 생성
    if(k == m){ //순열을 출력
        for (int i = 0 ; i <= m; i++)
            cout << a[i] << " ";
        cout << endl;
    } else { //a[k:m]에는 하나 이상의 순열이 있다. 이 순열을 재귀적으로 생성
        for(i=k;i<=m;i++) {
            swap(a[k], a[i]);
            Permutations(a, k+1, m);
            swap(a[k], a[i]);
        }
    }
}

 

표준 템플릿 라이브러리 STL

accumulate STL 알고리즘

• accumulate(start, end, initialValue)
  • 순차에 있는 원소들을 합산
• copy(start, end, to)
  • start, start+1,..., end-1에서 to, to+1, ..., to+end-start로 복사
• next_permutation(start,end)
  • [start,end) 범위에 있는 원소들의 다음으로 큰 사전식 순열 생성
  • 그러한 다음 순열이 존재하면 true 반환
• sort(start, end)
• count(start, end, value)
• fill(start, end, value)

sort 실습

• 헤더 파일에서 사용한 함수는? sort()
• 디버그 하지 않고 시작 : Ctrl + F5
• 중단점 설정 및 해제 : F9
• 디버깅 시작 : F5
• 한 단계씩 코드 실행 : F11
• 프로시저(함수) 단위 실행 : F10

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 오름차순 정렬
bool myfunction(int i, int j) { return (i < j); }

// struct는 default가 public
struct myclass {
    bool operator() (int i, int j) { return (i < j); }
} myobject;

int main() {
    int myints[] = { 32,71,12,45,26,80,53,33 };
    vector<int> myvector(myints, myints + 8); // 32 71 12 45 26 80 53 33
    vector<int>::iterator it; // using default comparison (operator <):

    // index 0부터 3까지 오름차순 정렬
    sort(myvector.begin(), myvector.begin() + 4); //(12 32 45 71)26 80 53 33

    // using function as comp - index 4부터 끝까지 오름차순 정렬
    sort(myvector.begin() + 4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

    // using object as comp
    sort(myvector.begin(), myvector.end(), myobject); //(12 26 32 33 45 53 71 80)

    // print out content:
    cout << "myvector contains:";
    for (it = myvector.begin(); it != myvector.end(); ++it)
        cout << " " << *it; cout << endl;

    return 0;
}

 

성능 평가 performance evaluation

공간 복잡도

• 프로그램을 실행시켜 완료하는 데 필요한 메모리 양
• 고정 부분
  • 보통 명령어 공간, 단순 변수, 집합체, 상수를 위한 공간
• 가변 부분
  • 변수, 참조된 변수가 필요로 하는 공간, 재귀 스택 공간
    • 함수를 부르면 스택에 메모리를 할당한다.
• 프로그램 P의 공간 요구 S(P) = c + Sp
  • c : 상수
  • Sp : 인스턴스 특성
    • 문제에 따라 달라지는 값
    • 인스턴스로 인해 필요로 하는 공간

float Abc(float a, float b, float c) {
    return a+b+b*c+(a+b-c)/(a+b)+4.0;
} // a,b,c가 일정 -> Sp = 0

line float Sum(float *a, const int n) {
    float s = 0;
    for(int i = 0 ; i < n ; i++)
        s+= a[i];
    return s;
} // Sp(n) = 0

line float Rsum(float *a, const int n) {
    if(n<=0) return 0;
    else return(Rsum(a, n-1) + a[n-1]);
} // Rsum을 호출하면 n, a, 반환값, 반환 주소 등 적어도 4개의 워드가 필요하다
  // 재귀 깊이가 n + 1이므로 재귀 스택 공간은 4(n + 1)이 필요

시간 복잡도

• 프로그램을 완전히 실행시키는데 필요한 시간
• T(P) = 컴파일 시간 + 실행시간 tp
  • 컴파일 시간은 바꾸기 어렵고
  • 실행 시간은 ADD, SUB, MUL, DIV 각 연산의 실행 횟수와 관련 있다.

프로그램 단계수

• 주석 : 0
• 선언문 0
• 함수문 : 0
  • 비용이 이미 호출 문에 할당
• 산술식 및 지정문 : 1
• 반복문 : 제어 부분에 대해서만 단계수 고려
• 스위치 문 각 조건의 비용 = 자기의 비용 + 앞서 나온 모든 조건의 비용
• if-else 문
  • , , <statement 2>에 따라 각각 단계수가 할당
• 함수 호출
  • 인스턴스 특성 의존 값에 의한 전달 인자 포함하지 않을 경우: 1
  • 인스턴스 특성 의존 값에 인한 전달 인자 포함할 경우 : 값 인자 크기의 합
  • 재귀적인 경우 : 호출되는 함수의 인스턴스 특성 의존 지역 변수도 고려
• 메모리 관리 명령문 : 1
  • new/delete
• 분기문 : 1
  • 인스턴스 특성 관련 return 경우 : 단계 수

단계 수 테이블

• s/e
  • step per execution
  • 그 명령문의 실행 결과로 count가 변화하는 양

line float Sum(float * a, const int n) {              // 0 1
    float s = 0;                          	      // 1 1
    for(int i = 0 ; i < n ; i++)          	      // 1 n+1
        s+= a[i];                         	      // 1 n
    return s;                             	      // 1 1
}                                         	      // 0 1
                                          	      // 총 단계 수 2n+3

line void Add(int **a, int **b, int**c, int m, int n)
{                                                     // 0 0
    for (int i = 0; i < m; i++)                       // 1 m+1
        for (int j = 0; j <n; j++)                    // 1 m(n+1)
            c[i][j] = a[i][j] + b[i][j];              // 1 mn
}                                                     // 0 1
                                                      // 총 단계수 2mn+2m+1

void Sum(float *a, contst int n) 
{                                 		     // 0 1
    for (int i = 0; i < n; i++)   		     // 1 n+1
        count += 2;               		     // 1 n
    count += 3;                   		     // 1 1
}                                 		     // 0 1
                                  		     // 총 단계 수 2n+3

line float Rsum(float * a, const int n)      	     // n=0         n>0
{                                            	     // 0 1         0 1
    if (n <= 0) return 0;                    	     // 1 1         1 0
    else return (Rsum(a, n-1) + a[n-1]);     	     // 1+t(n-1) 0  1+t(n-1) 1
}                                            	     // 0 1         0 1

void Fibonacci(int n)       
{//피보나치 수 Fn계산                                 // 0 1
    if(n<=1) cout << n << endl;                      // 1 0
    else {                                           // 1 1
        int fn; int fnm2 = 0; int fnm1 = 1;          // 2 1
        for(int i = 2 ; i <=n ;i++)                  // 1 n
        {                                            // 1 0
            fn = fnm1 + fnm2;                        // 1 n-1
            fnm2 = fnm1;                             // 1 n-1
            fnm1 = fn;                               // 1 n-1
        }                                            // 1 0
        cout << fn << endl;                          // 1 1
    }                                                // 1 0 
}                                                    // 1 0
                                                     // 4n-2

 

점근 표기법

빅오 big ‘oh’

• upperbound, worstcase를 생각해본다.
• 모든 n, n≥n0에 대해 f(n)≤cg(n)인 조건을 만족시키는 두 양의 상수 c와 n0가 존재하면 f(n)=O(g(n))
• O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!)

오메가 omega

• lowerbound 찾기
• 모든 n, n≥n0에 대해 f(n) ≥ cg(n)을 만족시키는 두 양의 상수 c와 n0가 존재하면 f(n) = Ω(g(n))

세타 theta

• 점근적 해석
• 모든 n, n≥n0에 대해 c1g(n)≤ f(n) ≤ c2g(n)을 만족시키는 세 양의 상수 c1, c2와 n0가 존재하면, f(n) = θ(g(n))