gnuykob_sw

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

1. Structure 구조체

- 자료형이 상이한 여러 멤버들을 하나의 자료로 묶어서 처리할 수 있는 복합 자료형

1-1. 구조체 변수 선언

// ex1

struct student
{
    int age;
    int grade;
    char major[20];
} kim, lee;

// ex2

struct
{ 
    int age;
    int grade;
    char major[20];
} kim, lee;

// ex3

struct student
{
    int age;
    int grade;
    char major[20];
};
struct student kim, lee;

세 가지 모두 kim과 lee라는 구조체 변수를 선언하는 문장이다.

첫 번째 방식과 같이 구조체의 이름을 줄 수 있고, 두 번째 방식과 같이 구조체 변수를 생성할 수 있다. 세 번째 방식은 구조체 변수를 struct 키워드를 이용해서 선언하는 방식이다. 

- 구조체 변수를 통해서 멤버에 값 저장

student.grade = 3;
strcpy(kim.major, "Software Convergence");

이와 같이 "." 연산자를 사용한다.

1-2. 구조체 자료형 선언

- 일반적으로 구조체를 사용할 때에는 typedef와 함께 사용되는데, typedef 키워드는 struct student_type{...}와 같이 긴 자료형 이름을 student 로 대체하여 구조체 변수를 선언할 수 있게 해준다.

// ex1

typedef struct student_type
{
    char name[10];
    int grade;
    char major[20];
} student;

// ex2

typedef struct
{ 
    char name[10];
    int grade;
    char major[20];
} student;

student kim, lee;

이처럼 struct만 쓴다면 } 이후 나오는 것은 그 구조체 자료형을 가진 "변수" 인 반면, typedef struct로 선언을 했을 때 } 뒤에 나오는 것은 구조체 "자료형" 이다.

1-3. 구조체 할당과 비교

- 할당

    - 동일한 자료형의 구조체 변수 간에 직접적인 할당 명령문은 가능하다.

    - (ex)

    studnet kim, lee;

    kim = lee; 

- 비교

    - 구조체 변수 간 직접 비교는 허용되지 않는다.

    - 구조체 멤버 별로 비교해주어야 한다.

    - (ex) 

    if (kim == lee) ...  // 오류 !!

    if (strcmp(kim.name, lee.name) ...

    if (kim.age != lee.name) ...

    if (kim.grade == lee.grade) ...

    이런식으로 멤버별로 비교해주면 된다.

    - 문자열 비교를 위해 사용된 strcmp 함수는 두 인자 값이 "다를" 경우 1을 반환한다.

1-4. 내장형 구조체

- 다른 구조체 변수를 멤버로 갖는 구조체

#include <stdio.h>
#include <string.h>

typedef struct Contact_type
{
    char phone[20];
    char email[20];
    char address[20];
} Contact;

typedef struct Student_type
{ 
    char name[20];
    int age;
    char major[20];
    int grade;
    Contact contact;
} Student;

void main() 
{
    Student kim;
    
    strcpy(kim.name, "ChulSoo Kim");
    kim.age = 22;
    strcpy(kim.major, "Software Convergence");
    kim.grade = 3;
    strcpy(kim.contact.phone, "010-3606-0418");
    strcpy(kim.contact.email, "kim@naver.com");
    strcpy(kim.contact.address, "Seoul, Korea");
}

student 구조체 안에 contact 구조체를 넣은 형태이다. 

2. Pointer 포인터

- 메모리 주소를 값으로 갖는 변수

- 간접 참조를 통해 원본 데이터를 공유하거나 변경할 수 있다.

- call by reference, 연결리스트 동적 메모리 관리 등에 사용된다.

2-1. "&" 과 "*"

- &

    - 모든 변수에 붙일 수 있는 "주소" 연산자이다. 

    - 해당 변수의 메모리 주소 값을 반환한다.

- *

    - 사용되는 위치에 따라 의미가 달라진다.

    - 반드시 포인터형 변수에만 적용해야 한다.

    - int i =3, j;

    - int *p;

    - p = &i;

        - i의 주소를 p에 할당한다.

    - kim = *p;

        - kim 변수에 p가 가리키는 주소에 저장된 "값"을 대입한다.

    - *p = j;

        - p가 참조하는 "공간"에 j의 값을 저장한다.

3. Array 배열

- 자료형이 동일한 원소들의 유한집합

- <index, value> → item

- 선언 이후 배열의 크기를 변경할 수 없다.

- 배열의 원소 수가 n개 라면 유효한 배열 인덱스의 범위는 [0, n-1] 이다. 

- 배열의 첫 번째 원소인 A[0] 을 "시작 주소 (α)"라고 부른다.   

   이후 원소들은 연속적인 메모리 주소에 저장된다. (α + sizeof(data type))

    - (ex) int → 4bytes 

    α = 100100 → 100104 → 100108 → ...

- 배열 이름 A는 시작 주소를 값을 갖고 있는 "포인터 상수"이다. 선언에 사용된 이름은 이후 다른 값(주소)을 가질 수 없다.

- A == &A[0]    : A[0]의 주소

- *A == A[0]   : A[0]의 값

3-1. 함수에 배열 전달

- 시작 주소를 가지고 있는 "배열 이름"만 전달하면 된다.

- 배열 포인터 관점에서는 call by value이지만, 배열의 관점에서는 call by reference 라고 볼 수 있다.

- int list[] == int *list

- 배열 이름 + 정수 → 첫번째 원소에서 정수의 원소 개수만큼 떨어져 있는 원소의 주소

- (ex) oneArray = 100 → oneArray + 1 = 104, oneArray +2 = 108

4. Polynomial 다항식

- 항들의 집합

- 다항식 추상자료형 연산자

    - Zero()

    - IsZero()

    - Coef (poly, expon)     : 계수 찾기

    - Lead_Exp (poly)     : 최고차항 지수

    - Attach (poly, coef, expon)     : 항 추가

    - Remove (poly, expon)

    - SingleMult (poly, coef, expon)     : 다항식과 단항의 곱셈

    - Add (poly1, poly2)

    - Mult (poly1, poly2)

- (ex) 다항식 배열 선언

#define MAX_TERMS 50

struct polynomial
{
    float coef;
    int expon;
};

struct polynomial terms[MAX_TERMS];

int avail = 0;

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

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