gnuykob_sw

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "자료구조", 유석종 교수님

1. Computer System

- 알고리즘 : 문제를 풀기 위한 명령어들의 모음 (데이터 처리 방법)

- 데이터 : 측정된 값들의 모음

- 자료구조 : 데이터를 효과적으로 저장, 관리, 처리하기 위한 구조체, 방법론

2. Algorithm

- 문제 해결에 필요한 명령어들의 집합

- 조건

    - input : 명시적 입력은 없어도 된다. (하지만, 묵시적 입력은 필요하다.)

    - output: 하나 이상의 출력이 필요하다.

    - definiteness 명확성 : 명령문은 모호하지 않고 명확해야 한다.

    - finiteness 유한성 : 명령어의 수는 유한해야 한다.

    - effectiveness 유효성 : 명령어는 실행 가능해야 한다.

- 표현 방법 : 수도코드, 자연어, flow chart, 프로그래밍 언어 ..

- 종류 : search, sort, compute, decision ..

- (ex) Prime Numbers

1) n이 소수인지 

int prime (int n)
{
    if (n < 2) return 0;
    for (i = 2; i < n; i++)
        if (n % i == 0) return 0;
        
    return 1;
}

2) 2와 n 사이의 모든 소수

int prime2 (int n)
{
    if (n < 2) return 0;
    
    for (i = 2; i < n; i++) {
        prime = 1;
        for (j = 2; j < i; j++) {
            if (i % j == 0) {
                prime = 0;
                break;
            }
        }
        if (prime) printf("%d", i);
    }
}

3. Huffman Coding Tree

- 빈도수에 따른 문자 압축 (요약) 방법

- (ex) "time and tide wait for no man"

- 방법

빈도수 순서로 문자들을 나열하고 빈도수의 합이 증가되는 방향으로 계속 더한다. 

더할 땐 값이 같거나 작은 것과 더한다.

각각의 연결 선에 0과 1의 label을 붙여준다. 왼쪽이 0, 오른쪽이 1이다.

가장 위에서부터 각각의 문자까지 내려오면서 label을 읽는다.

예를 들어 e는 29 - 17 - 7- 4- 2 순서대로 내려오기 때문에 0011 의 값을 갖는다.

10101010110 을 읽으면 101 / 0101 / 0110 → not 이 된다.

각 문자가 갖는 이진수 값을 '허프만 코드' 라고 부른다.

허프만 코딩 방법으로 저장한 문자의 저장 공간은 Sum(Freq * bits) 비트가 필요하다.

원래 문자를 저장할 때 필요한 공간은 '문자 수 x 비트(8)' 인데, 허프만 코드를 이용하면 데이터의 비트 수가 줄어들기 때문에 공간 복잡도를 57%나 낮출 수 있다. 

4. System Life Cycle

: Requirement → Analysis → Design → Inplementation → Verification → Release (+ improve)

4-1. Requirement

- 프로젝트의 목표를 정의하는 일련의 설계 명세서

- functions, platforms, input, output, constraints, users 등을 정의한다.

- (ex) Reservation system (flight ticket), Billing system (mobile phone, utility), Recruitment agency

4-2. Analysis

- 프로젝트를 여러개의 작은 서브 모듈로 세분화하는 전략이다.

- (ex) ticket reservation system → clients, contents, payment .. 

- top-down approach :  주 목표에서 구성 요소까지 계층을 만든다.

    - program → subroutines → instructions

    - 가장 많이 쓰는 방식이다.

- bottom-up approach : 구성요소들로부터 전체 시스템을 구성하는 방식이다.

4-3. Design

- 각 모듈에 대한 객체와 함수들을 정의한다.

- (ex) clinets → sign up/in, history, contents

4-4. Implementation

- 객체와 알고리즘에 대한 실행 가능한 코드를 작성한다.

- 플랫폼 : Web, Mobile App, Package, Embedded

4-5. Verification

- 알고리즘의 정확성 증명

- testing

    - black box test : 오직 input과 output 으로만 테스트

    - white box test : black box test + 내부 코드까지 확인

- Debugging

5. Data types

- 객체와 그 객체에 작용하는 관련된 연산자들의 모음

- (ex) Integer data type 

    - objects : {INT_MIN, ..., -2, -1, 0, 1, 2, ... INT_MAX}

    - operations : {+, -, *, /, %, ...}

        - INT MAX (4bytes) = 2^31 - 1 = 2,147,483,647

-Built-in data types

    - Basic type : char, int, float

    - Composite type : array, structure

    - Pointer type

    - User-defined data type : object type

    - sizeof() 함수로 크기 알 수 있다.

- (ex) Factorial

#include <stdio.h>
void factorial (int n);

void main() 
{
    factorial(20);
}

void factorial (int n);
{
    int i, j;
    int total;
    
    for(i = 2; i <= n; i++) {
        total = 1;
        for (j = 2; j <= i; j++) {
            total = total * j;
        }
        printf("%d! = %d\n", i, total);
    }
}

이 코드를 실행하면 12! 까지는 정확한 결과가 나오지만, 그 뒤로는 틀린 결과가 나온다. 

total 변수의 자료형인 intrk chleo 2,147,483,647까지만 저장 가능하기 때문이다. 

이러한 현상을 오버플로우라고 부르며, 더 큰 자료형을 사용함으로써 해결할 수 있다. 

6. Abstract Data Type 추상 자료형 (ADT)

- 사용자 정의 자료형이다. 

- 새로운 객체의 속성과 연산자를 정의한다.

- 공통적인 속성과 행동을 갖는 객체들을 자료형으로 정의 → 자료 추상화

- 명세부와 구현부로 이루어진다.

    - 명세부 : 객체를 자료형으로 정의 (객체의 속성 선언)

    - 구현부 : 객체에 적용 가능한 연산자 함수 정의

- 연산자

    - 생성자 : 새로운 객체 생성

    - 변형자 : 기존의 객체를 이용하여 새로운 객체 생성

    - 참조자 : 기존 객체의 속성값 참조

- 파이썬, C++, 자바에서 추상 자료형인 클래스 지원

- C는 지원하지 않는다.

- (ex) BankAccount 추상 자료형 수도코드

class BankAccount
{
    int account_id;
    int account_type;    // 0: checking, 1: saving
    char owner_name[20];
    float balance = 0;
    
    deposit(amount) {
        balance = balance + amount;
    }
    
    withdraw(amount) {
        balance = balance - amount;
    }
    
    init(name, type, money) {
        owner_name = name;
        account_type = type;
        deposit(money);
    }
}

BankAccount myaccount("Kim", 0, 10000);

- (ex) Natural number 추상 자료형

structure NaturalNum is

    Objects : an ordered subrange of integers [0, INT_MAX]
    
    Functions : for all x, y ∈ NaturalNum, TRUE, FLASE ∈ Boolean and 
                where +, -, <, = are integer operations
    
    NaturalNum Zero() ::= 0
    
    Boolean Is_Zero(x) ::= if (x) return FALSE else return TRUE
    
    NaturalNum add (x, y) ::= if((x + y) <= INT_MAX) return x + y else return INT_MAX
    
    NaturalNum Subtract(x, y) ::= if(x < y) return 0 else return x - y
    
    Boolean Equal(x, y) ::= if(x == y) return TRUE else return FALSE
    
    NaturalNum Successor(x) ::= if(x == INT_MAX) return x else return x + 1
    
end NaturalNum