gnuykob_sw

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

1. 탐색

- 다수의 레코드 집합에서 특정 키 값과 일치하는 레코드를 찾는 작업이다.

- 레코드는 객체의 속성에 해당하는 필드들의 집합으로 표현된다.

2. 순차 탐색

- 정렬되지 않은 레코드들에 대해 조건에 맞는 목표 키를 찾을 때까지 순차적으로 비교를 반복하는 작업이다.

- 정렬과 같은 요구 조건이 없어서 알고리즘은 단순하지만, 최상의 경우(1)와 최악의 경우(n) 탐색 성능에 큰 편차가 발생할 수 있다.

- 레코드 수(n)가 클수록 탐색 시간이 많이 걸린다

- 순차 탐색 알고리즘의 평균 비교 횟수 : (n + 1) / 2

#include <stdio.h>

int seq_search(int num[], int key, int n);

void main()
{
    int pos;
    int num[] = {12, 5, 6, 19, 23, 3, 7, 34, 89, 45, 22};
    
    pos = seq_search(num, 89, 11);
    printf("position = %d\n", pos);
    
    pos = seq_search(num, 43, 11);
    printf("position = %d\n", pos);
}

int seq_search(int num[], int key, int n)
{
    int i;
    for (i = 0; i < n; i++)
        if (num [i] == key) return i;
        
    return -1;
}

3. 이진 탐색

- 항목들을 정렬한 후 탐색을 적용한다.

- 겹치는 값이 없어야 한다.

- 오름차순으로 정렬된 항목들에 대해 중간값을 찾아 탐색 키와 비교한다.

- 탐색 키와 중간 값이 같으면 중간 값의 위치(인덱스)를 반환하고 탐색을 종료한다.

- 탐색 키가 중간 값보다 작으면 중간 값의 왼쪽에 있는 항목들로, 중간 값보다 크면 중간 값 오른쪽에 있는 항목들로 탐색 범위를 변경한다.

- 변경된 범위 항목에 대해 위의 과정을 반복한다.

- 탐색 대상 항목 수가 0이면 탐색 키를 찾지 못한 경우로 탐색을 종료한다.

- 시간 복잡도는 O(log₂ⁿ ) 이므로 순차 탐색에 비해 속도가 빠르다.

#include <stdio.h>

int binary_search(int mylist[], key, left, right);

void main() 
{
    int pos, size = 9;
    int mylist[] = {0, 1, 5, 9, 13, 17, 23, 32, 45};
    
    pos = binary_search(mylist, 45, 0, size-1);
    print("position = %d\n", pos);
    
    pos = binary_search(mylist, 8, 0, size-1);
    print("position = %d\n", pos);
}

int binary_search(int mylist[], key, left, right)
{
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (key == mylist[mid]
            return mid;
        else if (key < mylist[mid])
            right = mid - 1;
        else if (key > mylist[mid])
            left = mid + 1;
    }
    return -1
}

4. 보간 탐색

- 항목들이 정렬되어 있을 때 키 값의 차이와 위치의 차이가 비례한다는 가정을 바탕으로 한다.

- 탐색 키와 탐색 경계 값과의 차이를 고려하여 비교 키의 위치를 결정한다. 

- (list[right] - list[left]) : (key - list[left]) = (right - left) : (탐색 위치 - left)

- (양쪽 경계 값들의 차이) : (키 값과 왼쪽 경계 값의 차이) = (양쪽 범위의 거리) : (탐색 위치와 왼쪽 경계의 거리 차이)

#include <stdio.h>

int interpolate_serarch (int list[], int size, int key);

void main()
{
    int size = 12;
    int key = 39;
    int pos;
    int list[] = {2, 3, 5, 7, 8, 10, 13, 20, 25, 39, 45, 55};
    
    pos = interpolate_search(list, size, key);
    printf("%d is in %d\n", key, pos);
    key = 2;
    
    pos = interpolate_search(list, size, key);
    printf("%d is in %d\n", key, pos);
    key = 55;
    
    pos = interpolate_search(list, size, key);
    printf("%d is in %d\n", key, pos);
}

int interpolate_search(int list[], int size, int key)
{
    int pos;
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        pos = left + (key - list[left]) * (right - left) / (list[right] - list[left]);
        if (list[pos] < key)
            left = pos + 1;
        else if (list[pos] > key)
            right = pos - 1;
        else return pos;
    }
    return -1;
}

5. 해싱 탐색

- 탐색 키에 직접 산술적인 연산을 적용하여 탐색 키의 정보가 저장되어 있는 테이블 상의 위치를 계산하고 이 주소를 통해서 정보에 접근하는 방식이다.

- 즉, 반복적인 비교를 수행하는 것이 아니라, 키 자체에 있는 해답을 해시 함수를 통해 찾아내는 것이다.

- 시간 복잡도는 이론적으로 O(1)로 입력의 수 n에 상관없이 일정한 상수 시간을 갖는다.

- (ex) Dictionary

    - Entry (key, value)  // (word, definition)

    - Applications

        - Word / Thesaurus references

        - Spelling checker in word processor or editor

        - Electronic signature encoding/decoding

    - Operations

        - determine if a particular symbol(key) exists in the table (단순조회)

        - retrieve the attributes of a key (키의 속성값을 참조하는 연산)

        - modify the attributes of a key (키의 속성값 변경)

        - insert a new entry with a key and value (새로운 entry 추가)

        - delete an entry (entry 삭제)

5-1. Terms

- 해시 테이블 : 명칭(identifier)들이 저장된 고정된 크기의 표

- 명칭 밀도(ID) : 전체 명칭의 개수(T) 중 해시 테이블에 적재된 명칭 개수(n)의 비율 = n / T

- 적재 밀도(LD) : 해시 테이블의 크기에 대해 적재된 명칭 개수의 비율 = n / N

- 동의어(synonym) : 해시 테이블의 동일한 버켓 주소로 매핑된 서로 다른 명칭들, f(i₁) = f(i₂) 이면 i₁와 i₂는 동의어이다.

- 오버플로우 (overflow) : 명칭 i가 이미 꽉 찬 버켓으로 해싱(매핑)되는 경우 오버플로우가 발생한다고 말한다.

- 충돌 (collision) : 두 개의 서로 다른 명칭이 해시 테이블의 같은 버켓 주소로 매핑되면 충돌이 발생한다고 한다. 버켓의 크기가 1이면 충돌과 오버플로우가 동시에 발생한다.

- 해시 함수 : 해시 함수는 계산이 쉬워야 하고 명칭 간의 충돌을 최소화하여야 한다. 또한, 비대칭 편중분포를 막아야 한다.

    - 균등 해시 함수 : 각 버켓에 적재될 확률이 1/b 인 해시 함수 (P[f(x) = i] = 1 / b

    - 중간 제곱 해시 함수 : 명칭을 2진수로 변환한 후 제곱한 결과값에서 중간의 일부분을 해시 테이블 주소로 활용하는 함수, 테이블에 2ⁿ개의 버켓이 존재한다면 n개의 비트를 추출한다. collision을 최소화하기 위해 사용된다. 

    - 나눗셈 해시 함수 : 명칭을 특정 수로 나눈 나머지를 해시 테이블 주소로 사용하는 방법,예를 들어 해시 테이블 크기가 D라면 명칭 x를 D로 나눈 나머지 (0 ~ D-1)을 주소 값으로 사용한다. 이때 D는 분포에 영향을 주기 때문에 "소수"를 사용하는 것이 가장 좋고, 짝수는 사용하지 않는다. 나누는 수로 짝수를 사용하면 편중분포가 나타나기 때문이다.

    - 폴딩 해시 함수 : 명칭에 해당하는 비트 열을 해시 테이블 크기만큼 여러번 접어서 주소값으로 사용하는 것이다.

        - 이동 폴딩 : 명칭을 k 자리수로 분할한 뒤 순서대로 더한 결과값을 오른쪽에서 k자리 만큼 추출하여 주소 값으로 사용

        - 경계 폴딩 : 분할한 문자열에서 짝수 번째 문자열을 뒤집어서 덧셈을 수행한 후 k 자리의 문자열을 추출하여 사용

    - 키 분석 해시 함수 : 명칭의 구성과 내용을 미리 예측할 수 있는 경우에는 명칭을 분석하여 해시 테이블 주소로 사용할 키 값을 추출하는 방법을 사용할 수 있다. 예를 들어서 명칭이 학번일 경우, 앞의 두 자리는 입학년도임을 알고 그 부분은 배제하고 생각할 수 있다.

5-2. Static Hashing

- 해시 테이블의 크기가 고정되어있어 프로그램을 변경하지 않는 한 크기가 변경되지 않는 해싱 탐색 방법이다.

cf) Dynamic Hashing - 키 충돌 빈도에 따라 유연하게 해시 테이블 크기를 재구성하는 방법이다.

5-3. Hash Table 생성

// 해시 테이블 선언문

#define TABLE_SIZE 13

struct bucket
{
    int flag;
    char key[10];
};

struct bucket hash_table[TABLE_SIZE];

// 해시 테이블 초기화

void init_table()
{
    int i;
    for (i = 0; i < TABLE_SIZE; i++)
        hash_table[i].flag = 0;
}

5-4. Overflow 처리 방법

- Linear Probing 선형 탐색

    - static hashing 인 경우에 적용 가능하다.

    - overflow가 발생했을 때 선형적으로(순차적으로) 다른 비어있는 slot을 찾아가는 방법이다.

    - 이 결과 다른 home bucket으로 값이 저장될 수 있다.

    - HT[f(x) + j] % TABLE_SIZE, where 0 ≤ j ≤ TABLE_SIZE

    - 선형탐색에 의한 명칭 삽입 처리시 다음의 4가지 겨우 중 한 가지가 발생한다.

    1) 탐색된 버켓에 삽입하려는 명칭이 이미 저장되어 있는 경우 : 중복된 명칭으로 보고하고 오류 처리 or 특정 필드 값 갱신

    2) 탐색된 버켓이 비어 있는 경우 : 해당 버켓에 명칭 저장

    3) 탐색된 버켓이 x가 아닌 다른 명칭을 포함하고 있는 경우 : 다음 버켓 탐색 지속

    4) 탐색 결과 홈 버켓ㅇ로 다시 돌아온 경우 : 전체 버켓이 모두 꽉 찬 상태 → 오류 보고 후 종료

    - 문제점 : 명칭들이 서로 모여서 클러스터를 형성한다. 충돌 횟수가 증가할수록 탐색 속도도 느려진다. 

- 해시 함수 정의 

    - 키 (명칭)들을 ASCII 숫자값으로 변환한 뒤 해시 주소를 계산하는 방법이다.

// sum of ASCII codes of string chars

int transform (char *key)
{
    int number = 0;
    while (*key)                // NULL 값이 아니면
        number += *(key++);     // 정수 + 문자 -> 문자가 ASCII 코드로 변환됨
    return number;
}

int hash (char *key)
{
    return (transform(key) % TABLE_SIZE);
}

    - (ex)

이 경우 number는 F, O, R 의 ASCII 코드의 합이 된다. 그리고 그 합을 table size로 나눈 나머지가 주소가 된다.

5-5. Overflow 해결방법

- Linear probing 선형탐색법

    - ht[(f(x) +i) % b], 0 ≤ i ≤ b-1

- Quadratic probing 이차조사법

    - ht[f(x)], ht[f(x) + i²) % b], ht[f(x) - i²) % b], ..., 

    - 선형탐색법을 양방향으로 번갈아 탐색하는 방법이라고 볼 수 있다.

    - 선형탐색법은 한 방향으로 계속 탐색하기 때문에 cluster를 형성하기 쉬웠고, 이 방법은 그것을 해결할 수 있다.

- Rehashing 재해싱

    - overflow가 발생할 때마다 또 다른 해시 함수를 통해서 새로운 버켓을 탐색하는 방법이다.

    - 준비한 모든 해시 함수를 적용해도 빈 버켓 주소를 찾지 못하면 오류를 보고하거나 준비된 처리를 시행한다.

- Chaining 해시 체인

    - 각 버켓을 연결 리스트로 구현하여 특정 버켓에 충돌되는 명칭들을 연결 리스트로 관리하는 방법이다.

    - 근본적으로 overflow를 방지할 수 있다.

    - 하지만, 버켓 수에 비례하는 연결 리스트가 필요하며 원래 해싱 탐색 시간인 O(1)에 연결 리스트 탐색 시간 O(n)이 추가적으로 ㅣㄹ요하다. 

    - 각 연결 리스트에는 버켓의 헤드 노드가 존재한다.

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

1. 순서 리스트

- 원소들을 순서에 따라 배열한 리스트이다.

- (ex) days of week, months of year, ...

- C언어의 경우 같은 자료형으로 이루어져 있다.

- Array 배열

    - 선언한 뒤 원소의 개수를 바꿀 수 없다.

    -따라서 크기를 잘 설정하지 않으면 공간이 부족하거나 메모리 낭비가 발생할 수 있다.

    - 메모리에서 연속적으로 할당되며, 인덱스로 접근한다.

    - 중간에 원소를 추가하거나 제거하기도 어렵다.

- Linked list 연결 리스트

    - 메모리에 분산된 장소로 저장되어 있다.

    - 즉, 노드들이 메모리에 흩어져 있지만, 포인터로 연결되기 때문에 순서는 존재한다.

    - 크기 조절이 가능하다.

    - 중간에 원소 변경도 가능하다.

    - 하지만, 관리를 잘못했을 때 overhead 등 심각한 오류가 발생할 수 있다.

    - 사용자가 직접 연결 리스트의 노드를 실행 중에 관리하는 것을 '동적 메모리 관리'라고 한다.

2. 연결 리스트

- 특징

    - 원소들은 메모리 상에서 물리적으로 분산되어 있다.

    - 논리적으로는 포인터로 연속적으로 연결되어 있다.

    - 원소들은 필요할 때 생성될 수 있다.

- 표현

    - 연결 리스트의 원소는 '노드'라고 부르며 구조체로 선언된다.

    - 데이터 필드 : 정보를 저장한다. 데이터 필드를 추가함으로써 구조체를 확장할 수 있다.

    - 링크 포인터 필드 : 노드와 다음 노드를 연결하는 연결 포인터이다.

    - 연결 리스트의 노드는 자신과 동일한 구조체 자료형을 참조하기 때문에 자기 참조형 구조체라고도 부른다.

- ex

#include <stdio.h>

typedef struct node_type * note_ptr;

struct node_type
{
    int data;
    note_ptr link;
};

void main()
{
    struct node_type node1, node2, node3;
    node1.data = 7;
    node2.data = 11;
    node3.data = 13;
    node1.link = &node2;
    node2.link = &node3;
    node3.link = NULL;
    printf("%d %d %d", node1.data, node2.data, node3.data);
}

3개의 노드가 링크로 연결된 연결 리스트 예제이다. 

노드는 node_type 구조체형으로 선언되고, 링크 포인터는 구조체에 대한 포인터이며 node_ptr로 선언된다.

이 연결 리스트는 정적 메모리 공간에 노드 객체를 생성하여 연결한 경우이다.

따라서 실행 중에는 노드를 위한 공간을 할당할 수 없다.

- 연결 리스트 노드의 멤버에 접근할 때에는 ' -> ' 화살표 연산자를 사용한다.

- node1 -> data

- 필요 없는 노드는 free함수를 통해 해제하고 힙 공간으로 반환하는 것이 좋다.

따라서 위의 코드는 다음과 같이 나타낼 수 있다.

//node1.data = 7;
node1 -> data = 7;

//node2.data = 11;
node2 -> data = 11;

//node1.link = &node2;
node1 -> link = node2;

//node2.link = &node3;
node2 -> link = node3;

printf("node1 : %d", node1 -> data);

- 자료형으로 선언된 변수인 node1, node2, node3 은 정적 공간에 할당된 반면, malloc 함수에 의해 생성된 연결 리스트 노드들은 힙 메모리에 저장되어 있다. 

3. 동적 메모리 할당

- 정적 메모리 : 컴파일 할 때 메모리가 할당된다. 자료형이 있고, 선언되는 모든 변수가 정적 메모리를 가진다.

- 동적 메모리 : 실행될 때 메모리가 할당된다.

3-1. Operators

- malloc 

    - 지정된 크기의 메모리 할당을 요청한다.

    - 할당된 장소의 주소를 반환한다.

    - malloc으로 할당된 메모리 공간은 free() 를 선언하기 전까지 사라지지 않는다.

- free 

    - 할당된 메모리 공간을 해제하는 함수이다.

    - 해제하지 않으면 메모리 고갈이 발생한다.

3-2. Example (dynamic memory == heap memory)

void heap_test()
{
    int *pi;
    float *pf;
    
    pi = (int *) malloc (sizeof(int));
    pf = (float *) malloc (sizeof(float));
    *pi = 1024;
    *pf = 3.14;
    
    printf("%d, %f, %u\n", *pi, *pf, &pi);
    free(pi);
    free(pf);
}

처음 *pi와 *pf는 정적 메모리 공간에 할당되었다.

    pi = (int *) malloc (sizeof(int));
    pf = (float *) malloc (sizeof(float));

이 두 문장으로 pi와 pf 에 각각 동적 메모리 공간을 가리키는 포인터를 할당하였다.

    *pi = 1024;
    *pf = 3.14;

이 두 문장은 각각의 포인터가 참조하는 공간에 해당하는 값을 저장하는 실행문이다. 

따라서 메모리 공간이 아래와 같이 할당되었을 때, 프린트문을 실행하면 결과값은 다음과 같이 나온다.

1024, 3.14, 100

4. 단방향 연결 리스트

- 노드들이 한 방향으로만 연결된 경우를 단방향 연결 리스트라고 한다.

- 첫번째 노드를 참조하는 포인터를 '리스트 포인터'라고 한다.

- 이를 통해 리스트 노드들을 탐색한다.

- 노드 삽입

    - malloc 함수로 삽입할 노드를 생성하고, 그 주소를 포인터 노드에 할당한다.

    - 생성된 노드의 데이터 필드에 값을 저장하고, 링크 필드에 NULL을 저장한다.

    - 연결 리스트 포인터가 list라고 가정할 때 

        1) 연결 리스트가 비어 있는 경우 (empty)

            - 삽입할 노드가 유일한 노드이므로 이 노드가 첫 노드가 되도록 리스트 포인터(list)에 노드의 주소 값을 저장하고 종료한다.

        2) 비어 있지 않은 경우

            - 리스트 중간에 삽입되는 경우 (앞 노드가 있는 경우)

            → 앞 노드의 링크 필드 값을 노드의 링크에 저장한다.

            → 앞 노드의 링크 필드에 노드의 주소 값을 저장하고 종료한다.

            - 리스트 맨 앞에 삽입되는 경우

            → 삽입할 노드의 링크 필드에 연결리스트 포인터 값 지정한다.

            → 연결리스트 포인터가 노드를 가리키도록하고 종료한다.

- malloc 함수로 새 공간을 요청해도 가용 힙 메모리가 더 이상 없다면 주소 값 대신 NULL 값이 반환된다.

- 선언

typedef struct list_node *list_ptr;
struct list_node {
    char data[4];
    list_ptr link;
};
list_ptr ptr = NULL;

- macro function for empty list

#define IS_EMPTY(ptr) (!ptr)

ptr이 NULL값이면 IS_EMPTY(ptr)은 1을 반환한다.

- 노드 초기화

ptr = (list_ptr) malloc (sizeof(struct list_node));
strcpy(ptr -> data, "com");
ptr -> link = NULL;

- 노드 삽입

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

node_ptr list;
void insert_node(node_ptr prev, int data);
void print_list(node_ptr list);

void main()
{
    node_ptr node1, node2, node3;
    
    node1 = (node_ptr) malloc(sizeof(struct node_ytpe);
    node1 -> data = 100;
    node1 -> link = NULL:
    list = node1;
    
    node2 = (node_ptr) malloc(sizeof(struct node_ytpe);
    node2 -> data = 200;
    node2 -> link = NULL:
    list = node2;
    
    print_list(list);
    insert_node(node1, 150);
    printf_list(list);
}

void insert_node(node_ptr prev, int data)
{
    node_ptr node;
    node = (node_ptr) malloc (sizeof(struct node_type));
    if (!node) exit(1);
    node -> data = data;
    node -> link = NULL;
    
    if (!list) {
        list = node;
    }
    else if(prev) {
        node -> link = prev -> link;
        prev -> link = node;
    }
    else {
        node -> link = list;
        list = node;
    }
}

void print_list (node_ptr list) 
{
    while (list) {
        printf("%d ", list -> data);
        list = list -> link;
    }
    printf("\n");
         
}               

- 노드 삭제

    1) 리스트가 비어 있는 경우 

        - 그대로 종료한다.

    2) 리스트에 노드가 존재하는 경우 

    2-1) 중간 노드 삭제

        - 삭제 노드의 앞 노드의 링크 필드에 삭제할 노드의 링크를 저장한다.

    2-2) 맨 앞 노드 삭제

        - 리스트 포인터에 삭제할 노드의 링크를 저장한다.

    - 노드를 삭제하고 종료한다.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

node_ptr list;
void delete_node (node_ptr prev, node_ptr node);
void print_list (node_ptr list);

void main()
{
    node_ptr node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type));
    node1 -> data = 100;
    node1 -> link = NULL;
    list = node1;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 200;
    node2 -> link = NULL;
    node1 -> link = node2;
    
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 300;
    node3 -> link = NULL;
    node2 -> link = node3;
    
    print_list(list);
    delete_node(node1, node2); // node1 : prev, node2 : delete
    print_list(list);
}

void delete_node(node_ptr prev, node_ptr node)
{
    if (prev) {
        prev -> link = node -> link;
    }
    else {
        list = node -> link;
    }
    free(node);
}

void print_list(node_ptr list)
{
    while(list) {
        printf("%d", list -> data);
        list = lsit -> link;
    }
    printf("\n");
}

5. 연결 리스트 연산자

5-1. 연결 리스트 길이

- 노드 수로 계산한다.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

int length_list(node_ptr list);

void main()
{
    node_ptr list, node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type));
    node1 -> data = 100;
    node1 -> link = NULL;
    list = node1;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 200;
    node2 -> link = NULL;
    node1 -> link = node2;
    
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 300;
    node3 -> link = NULL;
    node2 -> link = node3;
    
    printf("list lentgh is %d\n", length_list(list));
}

int lentgh_list (node_ptr list)
{
    int count = 0;
    node_ptr temp = list;
    while (temp)
    {
        count ++;
        temp = temp -> link;
    }
    return count;
}

5-2. 연결 리스트의 결합

- 두 개의 연결 리스트를 연결하여 하나로 합치는 것이다. 

- 결합 연산은 앞 리스트의 노드 수에 비례하여 시간이 걸리므로, 시간복잡도는 O(첫번째 리스트의 길이) 가 된다.

- 첫 번째 리스트가 빈 리스트라면 두 번째 리스트를 그대로 반환하고 종료한다.

- 첫 번째 리스트가 빈 리스트가 아니라면 두 번째 리스트를 확인한다.

    - 두 번째 리스트가 빈 리스트라면 첫 번째 리스트를 그대로 반환하고 종료한다.

    - 두 번째 리스트가 빈 리스트가 아니라면 결합하기 위해 첫 번째 리스트의 마지막 노드를 탐색하고, 마지막 노드의 링크 필드에 두 번째 리스트 포인터(list2)를 저장한 후 첫 번째 리스트 포인터(list1)를 반환하고 종료한다.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

node_ptr concat_list(node_ptr list1, note_ptr list2);
void print_list(list1);

void main()
{
    node_ptr list1, list2, node1, node2;
    list1 = (node_ptr) malloc (sizeof(struct node_type));
    list1 -> data = 100;
    
    node1 = (node_ptr) malloc (sizeof(struct node_type);
    node1 -> data = 150;
    node1 -> link = NULL;
    
    list1 -> link = node1;
    
    list2 = (node_ptr) malloc (sizeof(struct node_type));
    list2 -> data = 200;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 250;
    node2 -> link = NULL;
    
    list2 -> link = node2;
    
    print_list(list1);
    print_list(list2);
    list1 = concat_list(list1, list2);
    print_list(list1);
}

node_ptr concat_list (node_ptr list1, node_ptr list2)
{
    node_ptr temp;
    if (!list1)
        return list2;
    else {
        if (list2) {
            temp = list1;
            while (temp -> link)
                temp = temp -> link;
                
            temp -> link = list2;
        }
        return list1;
    }
}

void print_list(node_ptr list)
{
    while (list) {
        printf("%d", list -> data);
        list = list -> link;
    }
}

6. 순환 연결 리스트

- 연결 리스트의 마지막 노드의 링크가 NULL이 아니고, 그 리스트의 첫 노드에 다시 연결되어 있는 형태를 말한다.

- 시작 노드가 변경되어도 전체 노드들이 여전히 연결되어 있는 상태이기 때문에 시작 노드 변경이 용이하다.

- 순환 연결 리스트의 길이

    - 시작노드로 다시 되돌아올 때가 전체 노드를 모두 탐색한 시점이다.

    - do - while 문 사용

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type
{
    int data;
    node_ptr link;
};

int clist_length(node_ptr list);

void main() 
{
    node_ptr list, node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type);
    node1 -> data = 7;
    list = node1;
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 11;
    node1 -> link = node2;
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 13;
    node2 -> link = node3;
    node3 -> link = node1;
    
    printf("circular list length = %d", clist_length(list));
}

int clist_length(node_ptr list)
{
    node_ptr move;
    int num = 0;
    if (list) {
        move = list;
        do {
            num ++;
            move = move -> link;
        } while (move != list);
    }
    
    return num;
}

7. 역순 연결 리스트

- 리스트 노드의 연결 순서를 반대로 뒤집어서 리스트로 반환하는 형식이다.

- (ex) [7 - 11 - 13] → [13 - 11 - 7]

- 시간 복잡도는 리스트의 길이(노드의 개수)에 비례한다.

- 리스트가 비어있거나 노드가 1개만 있는 경우 그대로 리스트 포인터(one)를 반환하고 종료한다.

- 리스트에 노드가 2개 이상인 경우 2개의 임시 포인터 변수(two, three)를 더 사용하여 연결 순서를 변환한다.

    - 노드 포인터(three)가 노드 포인터(two)를 참조하게 한다.

    - 노드 포인터(two)가 노드 포인터(one)를 참조하게 한다.

    - 노드 포인터(one)를 다음 노드로 이동시킨다.

    - 노드 포인터(two)의 링크 필드에 노드 포인터(three) 값을 저장하여 두 노드를 연결 시킨다.

    - 노드 포인터(one)가 NULL이 아닐 때까지 반복한다.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type * node_ptr;
struct node_type 
{
    int data;
    node_ptr link;
};

node_ptr reverse_list(node_ptr);
void print_list(node_ptr);

void main()
{
    node_ptr list, node1, node2, node3;
    node1 = (node_ptr) malloc (sizeof(struct node_type));
    node1 -> data = 7;
    list = node1;
    
    node2 = (node_ptr) malloc (sizeof(struct node_type));
    node2 -> data = 11;
    node1 -> link = node2;
    
    node3 = (node_ptr) malloc (sizeof(struct node_type));
    node3 -> data = 13;
    node2 -> link = node3;
    node3 -> link = NULL;
    
    print_list(list);
    list = reverse_list(list);
    print_list(list);
}

node_ptr reverse_list(node_ptr one)
{
    node_ptr two, three;
    two = NULL;
    while (one) {
         three = two;
         two = one;
         one = one -> link;
         two -> link = three;
    }
    return two;
}

void print_list(node_ptr list)
{
    while(list) {
        printf(%d ", list -> data);
        list = list -> link;
    }
}

8. 양방향 연결 리스트          

- 각 노드가 자신의 이전과 이후 노드에 대한 링크 포인터를 가지고 있다.

- 노드 삽입 또는 삭제 시 앞 노드를 추가로 알려줄 필요가 없기 때문에 편리하다.

- 대표적으로 이진 트리에 사용된다.

- node == node -> llink -> rlink == node -> rlink -> llink

- 단방향 연결 리스트와 달리 모든 노드의 링크 필드 값을 채워야 한다.

- 따라서 삭제할 수 없는 head 노드가 사용된다.

- 시작 노드의 llink 필드는 head 노드를 참조하도록 초기화된다.                  

// 양방향 연결 리스트의 선언

typedef struct node_type * node_ptr;
struct node_type 
{
    node_ptr llink;
    int data;
    node_ptr rlink;
};

- 노드 삽입

    - 노드의 llink를 prev 노드로 연결한다.

    - 노드의 rlink를 prev 다음 노드로 연결한다.

    - prev 다음 노드의 llink가 노드를 참조하도록 연결한다.

    - prev 노드의 rlink가 노드를 참조하도록 연결한다.

#include <stdio.h>
#include <stdlib.h>

typedef struct dll_node_type * dll_node_ptr;
struct dll_node_type 
{
    dll_node_ptr llink;
    int data;
    dll_node_ptr rlink;
};

void insert_dll (dll_node_ptr prev, dll_node_ptr node);
void print_dll_list (dll_node_ptr list1);

void main()
{
    dll_node_ptr head, list, node1, node2, node3;
    head = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 -> data = 7;
    list = node1;
    
    head -> llink = NULL;
    head -> rlink = node1;
    node1 -> llink = head;
    
    node2 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node2 -> data = 13;
    node2 -> llink = node1;
    node2 -> rlink = head;
    node1 -> rlink = node2;
    
    node3 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node3 -> data = 11;
    node3 -> llink = NULL;
    node3 -> rlink = NULL;
    head -> llink = node2;
    
    print_dll_list(head, list);
    insert_dll(node1, node3);
    print_dll_list(head, list);
}

void insert_dll (dll_node_ptr prev, dll_node_ptr node)
{
    node -> llink = prev;
    node -> rlink = prev -> rlink;
    prev -> rlink -> llink = node;
    prev -> rlink = nodel
}

void print_dll_list (dll_node_ptr head, dll_node_ptr list) 
{
    while (list != head) {
        printf("%d ", list -> data);
        list = list -> rlink;
    }
    printf("\n");
}

- 노드 삭제

    - head 노드는 삭제가 불가능하다.

    - 일반 노드의 삭제일 경우 삭제할 노드의 이전 노드의 rlink에 삭제할 노드의 다음 노드 주소를 저장한다.

    - 삭제할 노드의 다음 노드의 llink에 노드 이전 노드를 복사한다.

#include <stdio.h>
#include <stdlib.h>

typedef struct dll_node_type * dll_node_ptr;
struct dll_node_type 
{
    dll_node_ptr llink;
    int data;
    dll_node_ptr rlink;
};

void delete_dll (dll_node_ptr head, dll_node_ptr node);
void print_dll_list (dll_node_ptr head, dll_node_ptr list);

void main()
{
    dll_node_ptr head, list, node1, node2, node3;
    head = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node1 -> data = 7;
    list = node1;
    
    head -> llink = NULL;
    head -> rlink = node1;
    node1 -> llink = head;
    
    node2 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node2 -> data = 13;
    node2 -> llink = node1;
    node1 -> rlink = node2;
    
    node3 = (dll_node_ptr) malloc (sizeof(struct dll_node_type));
    node3 -> data = 11;
    node3 -> llink = node2;
    node3 -> rlink = head;
    node2 -> rlink = node3;
    head -> llink = node3;
    
    print_dll_list(head, list);
    insert_dll(node1, node3);
    print_dll_list(head, list);
}

void insert_dll (dll_node_ptr prev, dll_node_ptr node)
{
    node -> llink = prev;
    node -> rlink = prev -> rlink;
    prev -> rlink -> llink = node;
    prev -> rlink = nodel
}

void print_dll_list (dll_node_ptr head, dll_node_ptr list) 
{
    while (list != head) {
        printf("%d ", list -> data);
        list = list -> rlink;
    }
    printf("\n");
}

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

1. 다차원 배열

- 2차원 이상의 배열을 다차원 배열이라고 한다.

- 논리적으로는 m차원이지만, 물리적으로는 1차원으로 메모리 상에 표현됟나.

- m차원 배열 A : int A[n₀][n₁] ··· [nₘ₋₁];

- 배열 A에 저장되는 원소의 총 개수 : n₀ x n₁ x ··· nₘ₋₁

   예를 들어 A[10][9][8]로 선언된 배열 원소의 총 개수는 10 x 9 x 8 = 720개이다.

1-1. 행 우선 순서 (Row-major order)

- 기본 주소에서부터 행을 기준으로 원소가 저장된다. 

- 배열 원소의 오른쪽 차원의 인덱스가 먼저 증가되고, 상한 경계에 도달하면 바로 왼쪽 옆자리가 1씩 증가된다.

- 이런식으로 인덱스 값이 오른쪽에서 왼쪽 방향으로 증가하면서 메모리에 저장된다.

- (ex) A[0][0] → A[0][1] → A[1][0] → A[1][1] → A[2][0] → A[2][1]

1-2.  열 우선 순서

- 열을 우선적으로 채워가는 형식이다.

- 배열 원소의 왼쪽 차원의 인덱스가 먼저 증가되고, 상한 경계에 도달하면 바로 오른쪽 옆자리가 1씩 증가된다.

- (ex) A[0][0] → A[1][0] → A[2][0] → A[0][1] → A[1][1] → A[2][1]

2. 원소의 주소

2-1. 1차원 배열

- 원소의 위치는 시작주소(α) + 오프셋(offset) 값으로 계산된다.

- n개의 원소를 가지고 있는 1차원 배열 A의 시작 주소가 α이고, 각 원소에 s바이트가 할당된다고 할 때,

 &A[0] = α + 0 * s

 &A[1] = α + 1 * s

 ...

 &A[n-1] = α + (n-1) * s

→ &A[i] = α + i * s

2-2. 2차원 배열

- A[u₀][u₁]으로 선언된 2차원 배열에서 A[i][j] 주소는 α + (i * u₁ + j) * s 이다.  // 행 우선 순서일 때

- 열 우선 순서일 때의 주소는  α + (i + u₀ * j) * s 이다.

2-3. 3차원 배열

- A[u₀][u₁][u₂] 으로 행 우선 순서로 선언된 2차원 배열에서 A[i][j][k]의 주소는 α + (i * u₁ * u₂ + j * u₂ + k) * s이다.

- 열 우선 순서로 저장된 배열의 주소는 α + (i * u₁ * u₂ + j + u₁ * k) * s이다.

3. Stack 스택

- 선형 리스트의 특별한 형태로, 한 방향으로 쌓아둔 것을 의미한다.

- 후입 선출 구조이다. (LIFO : Last-In, First-Out)

- 함수 호출 관리, 문법 검사, 연산식 평가 등에 활용된다.

- S = [a₀, a₁, ..., aₙ₋₁] 형식으로 원소들의 리스트로 정의할 수 있다.

- aₙ₋₁ 이 가장 나중에 삽입된 원소이다.

- 스택에 원소를 추가하는 연산을 "push"라고 하고, 원소를 삭제하는 연산을 "pop"이라고 한다.

- top 포인터는 가장 나중에 삽입된 원소를 가리키며, 그 위치에 해당하는 배열 인덱스 값을 갖는다.

- 빈 스택에서 top 포인터는 -1 값을 갖는다.

- 1차원 배열로 구성된 스택에 최초로 들어오는 원소는 stack[0]에 저장된다.

- (ex) Function Call

    - A()가 실행 중일 때 B를 호출하면, B()가 끝날 때까지 A()는 멈춰있다.

    - 새로운 함수가 실행될 때마다 현재 실행 중인 함수의 환경 변수를 시스템 스택에 Stack Frame 형태로 저장해야 한다.

    - Stack Frame (Activation record)

        - 지역 변수

        - 재개할 때 다음에 실행될 명령어의 주소

        - 이전 stack frame의 포인터

#define STACK_SIZE 100
int stack[STACK_SIZE];
int top = -1;

void push(int item);
int pop;
void print_stack();

void main() 
{
    push(3);
    push(4);
    push(5);
    pop();
    print_stack();
    pop();
    print_stack();
    pop();
    print_stack();
    pop();
    print_stack();
}

void print_stack()
{
    int i;
    for(i = 0; i <= top; i++)
        printf("%d", stack[i]);
    
    printf("\n");
}

void push(int item)
{
    if (top >= STACK_SIZE - 1){
        printf("stack full");
        return;
    }
    
    stack[++top] = item;
    print_stack();
}

int pop()
{
    if (top < 0) {
        printf("stack empty");
        return -999;
    }
    return stack[top--];
}

- 실행 결과

3

3 4

3 4 5

3 4

3

stack empty

4. Queue 큐

- 처리를 기다리고 있는 원소들의 리스트라고 볼 수 있다.

- 스택과 같은 선형 리스트 구조이다.

- 스택과 다른 점은 "선입 선출" 방식이라는 것이다. (FIFO : First-In, First-Out)

- 새로운 원소는 큐의 맨 뒤(rear)에 삽입되고, 큐의 맨 앞(front)원소가 가장 먼저 삭제된다.

- Q = [a₀, a₁, ..., aₙ₋₁] 형식으로 정의할 수 있으며, a₀가 가장 먼저 삽입된 원소이고, aₙ₋₁가 가장 나중에 삽입된 원소이다.

- 큐의 맨 앞과 맨 뒤를 가리키기 위한 두 개의 포인터 (front, rear) 가 필요하다.

- 원소가 삽입될 때에는 rear 포인터가, 삭제될 때에는 front 포인터가 각각 사용된다.

- rear 포인터 값이 큐의 상한 경계와 같으면 full queue로 판단하고, rear와 front 포인터의 값이 같으면 empty queue로 간주한다.

#define QUEUE_SIZE 100
int queue[QUEUE_SIZE];
int rear = -1;
int front = -1;
void print_queue();
void addq(int item);
int deleteq();

void main()
{
    int temp;
    
    addq(3);
    addq(5);
    addq(7);
    temp = deleteq();
    print_queue;
}

void print_queue()
{
    int i;
    
    for (i = front + 1; i <= rearl i ++)
        printf("%d", queue[i]);
    
    printf("\n");
}

void addq(int item)
{
    if(rear == QUEUE_SIZE - 1) {
        printf("Queue Full. item not added");
        return;
    }
    queue[++rear] = item;
    print_queue;
}

int deleteq()
{
    if (front == rear) {
        printf("Queue empty.");
        return -999;
    }
    return queue[++front];
}

- 실행 결과

3

3 5

3 5 7

5 7

4-1. 일반 큐

- 원소의 삽입, 삭제 시 rear와 front 포인터 값이 모두 증가된다.

- 삽입 삭제 빈도가 증가할수록 큐에서 원소들의 저장 위치가 점점 오른쪽으로 이동하게 되고, 왼쪽에 빈공간이 생기게 된다.

- 따라서 원소가 다 차지 않았음에도 queue full 신호가 발생할 수 있다.

- 큐의 빈공간을 재사용하기 위해서는 원소들을 왼쪽으로 이동시키는 작업을 주기적으로 해주어야 한다. 이를 해결한 자료구조가 "순환 큐"이다.

4-2. 순환 큐

- 큐의 오른쪽 끝을 반대편 끝과 연결하여 원소가 이동할 필요 없이 전체 공간을 모두 사용할 수 있다.

- 일반 큐와 마찬가지로 front와 rear 포인터 값이 같을 때를 empty queue로 정의한다.

- front와 rear의 초기값은 각각 0이다. 

- 순환 큐의 모든 공간에 원소가 삽입되면 front와 rear 값이 또 같아지게 된다.

- 이런 상황을 피하기 위해 rear = front - 1인 시점, 즉 원소가 n-1개 삽입된 상태를 full queue로 간주한다.

#include <stdio.h>
#define QUEUE_SIZE 100
int front, rear;
int cqueue[QUEUE_SIZE];
void addcq(int item);
int deletecq;
void print_queue();

void main()
{
    int temp;
    front = rear = 0;
    
    addcq(11);
    addcq(13);
    addcq(17);
    addcq(19);
    
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
    temp = deletecq();
    print_queue();
}

void addcq(int item)
{
    if (front == ((rear + 1) % QUEUE_SIZE) {
        printf("queue full");
        return;
    }
    rear = (rear + 1) % QUEUE_SIZE;
    cqueue[rear] = item;
    print_queue();
}

int deletecq()
{
    if (front == rear) {
        printf("queue empty");
        return -999;
    }
    front = (front + 1) % QUEUE_SIZE;
    return cqueue[front];
}

void print_queue()
{
    int i = front;
    while (i != rear) {
        i = (i + 1) % QUEUE_SIZE;
        printf("%d", cqueue[i]);
    }
    printf("\n");
}

- 일반 큐와는 달리 순환 큐이기 때문에 if (front == ((rear + 1) % QUEUE_SIZE) 와 같이 "%" 연산자를 사용해야 한다.

- (ex) QUEUE_SIZE = 6이면 인덱스는 0 ~ 5가 존재한다. 이번에 마지막 칸인 인덱스가 5인 칸에 값을 넣었다면 그 다음칸은 6 % 6 인 0이 되어야 한다. 그리고 그것이 front 값과 같기 때문에 full queue가 되었음을 알 수 있다.

5. Deque 

- Double ended queue

- 양방향으로 삽입과 삭제가 모두 가능한 자료구조이다.

6. 수식 평가

- 수식은 연산자와 피연산자로 구성된 문장이다.

- 연산자는 산술 연산자, 논리 연산자, 대입 연산자 등이 있다.

- 피연산자는 변수 또는 상수가 될 수 있다.

- 표기법

    - 중위 표기법

        - a / b - c + d * e - a * c

    - 후위 표기법

        - ab / c - d e * + a c *

    - 전위 표기법

        - - + - / a b c * d e * a c

6.1 후위 수식 계산 알고리즘

    - 수식을 왼쪽에서 오른쪽으로 스캔한다.

    - 수식에서 들어온 입력이 피연산자이면 스택에 넣는다.

    - 입력이 연산자이면 스택에서 피연산자를 2개 꺼내서 계산한 후 결과 값을 다시 스택에 넣는다. 

- 수식 평가 스택

#include <stdio.h>
#include <string.h>
#define STACK_SIZE 100
#define EXPR_SIZE 100

typedef enum
{
    open_b, close_b, plus, minus, times, divide, mod, eos, operand
} priority;        // 열거형 -> 0, 1, 2, ..., 8

int stack[STACK_SIZE];    // 수식 평가 스택
char expr[EXPR_SIZE];     // 수식 문자열
int pos = 0;              // 문자열 현재 위치
char sym;
int sym_type;
int top = -1;

- 후위 수식 평가

int eval_postfix();
void push(int item);
int pop();

void main()
{
    // strcpy(expr, "57 * 9 + 34 / -");        // 5 * 7 + 9 - 3 / 4
    strcpy(expr, "936 + 5 - / 7 * 64 - *");    // 9 / (3 + 6 - 5) * 7 * (6 - 4)
    eval_postfix();
}

int eval_postifx()
{
    char sym;
    int op1, op2;
    sym = read_item();
    while (sym_type != eos) {
        if (sym_type == operand)
            push(sym - '0');
        else {
            op2 = pop();
            op1 = pop();
            switch (sym_type) {
                case plus : push(op1 + op2);
                case minus : push(op1 - op2);
                case times : push(op1 * op2);
                case divide : push(op1 / op2);
                case mod : push(op1 % op2);
            }
        }
        sym = read_item();
    }
    return pop();
}
 
void push (int item) 
{
    if (top >= STACK_SIZE - 1) {
        printf("stack full");
        return;
    } 
    stack[++top] = item;
    print_stack;
}

int pop() 
{
    if (top < 0) {
        printf("empty stack");
        return -999;
    }
    return stack[top--];
}

- 심볼 입력

char read_item()
{
    char sym;
    sym = expr[pos++];
    
    switch (sym)
    { 
        case '(' : sym_type = open_b;
            break;
        case ')' : sym_type = close_b;
            break;
        case '+' : sym_type = plus;
            break;
        case '-' : sym_type = minus;
            break;
        case '*' : sym_type = times;
            break;
        case '/' : sym_type = divide;
            break;
        case '%' : sym_type = mod;
            break;
        case '\0' : sym_type = eos;
            break;
        default : sym_type = operand;    // 피연산자
    }
    
    return sym;
}

- 실행 결과

9 3 6 + 5 - / 7 * 6 4 - *

9

9 3

9 3 6

9 9

9 9 5

9 4

2

2 7

14

14 6

14 6 4

14 2

28

6-2. 중위 수식 → 후위 수식

    - 입력이 피연산자이면 그대로 출력한다.

    - 입력의 우선 순위가 스택 top의 연산자보다 높거나, 스택이 비어있으면 입력을 스택에 넣는다.

    - 스택의 연산자 우선 순위가 입력보다 크거나 같으면 스택 연산자를 pop하고 입력을 스택에 넣는다.

    - 입력이 '(' 이면, ')'이 들어올 때까지 다음 연산자를 위의 규칙을 따라서 스택에 넣는다.

    - 입력이 ')' 이면, '('이 나올 때까지 스택에서 계속 연산자를 pop해서 출력하고 '(' 은 출력하지 않고 버린다.

    - 입력이 문자열의 끝(eos)이면, 스택의 모든 연산자를 꺼내서 출력한다.

- (ex)

a + (b * c + d) * e

#include <stdio.h>
#include <ctype.h>
#define STACK_SIZE 100

char token_stack[STACK_SIZE];
int token_top = -1;
void infix_to_postfix();
int precedence(char op);
void push_token(char sym);
char pop_token();

void main()
{
    infix_to_postfix();
}

void infix_to_postfix()
{
    char expr[50], sym, token;
    int pos = 0;
    
    printf("Enter the expression :: ");
    scanf("%s", expr);
    
    while ((token = expr[pos++]) != '\0') {
        if (isalnum(token))          // 알파벳 또는 숫자
            printf("%c", token);
        else if (token == '(')
            push_token(token);
        else if (token == ')') {
            while ((sym = pop_token()) != '(')
                pirntf("%c", sym);
        }
        else {
            while(precedence(token_stack[token_top]) >= precedence(token) && 
                  token_top != -1) {
                  printf("%c", pop_token());
            }
            push_token(token);
        }
    }
    while (token_top != -1) 
        printf("%c", pop_token());
}

int precedence (char op)
{
    if (op == '(')
        return 0;
    else if (op == '+' || op == '-')
        return 1;
    else if (op == '*' || op == '/' || op == '%')
        return 2;
}

void push_token(char sym)
{
    if (token_top < STACK_SIZE -1)
        token_stack[++token_top] = sym;
    else
        printf("token stack full\n");
}

char pop_token()
{
    if (token_top >= 0)
        return token_stack[token_top--];
        
    printf("token stack empty\n");
    return ' ';
}
            

- 실행 결과

Enter the expression :: a + (b * c + d) * e

a b c * d + e * +

Enter the expression :: 5 * 7 + (4 - 3) / 6 % 9

5 7 * 4 3 - 6 / 9 % +

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

1. 성능 분석 (실행 가능한 기준)

    - 공간 복잡도 (space complexity) : 필요한 메모리 양

    - 시간 복잡도 (time complexity) : 프로그램 수행 시간

2. 공간 복잡도 

- Fixed space requirements (Sc)

    - 실행 도중에 변하지 않는 것

    - 명령어, 단순 변수, 고정된 구조체 변수, 상수 등

    - 공간 복잡도에 고려하지 않는다.

- Variable space requirement (Sv)

    - 프로그램 실행 중에 요구되는 공간으로 가변적이고 예측이 어렵다.

    - 함수 간 배열 전달, 재귀 호출 등

    - 위험 요소를 내포하고 있으며, 공간 복잡도 평가에서 더욱 중요하다.

- S = (Sc +) Sv

- (ex1)

float abc (float a, float b, float c)
{
    return a + b + b * c + (a + b - c) / (a + b) + 4.00;
}

    -input과 output이 단순 변수로만 이루어져 있고, 명령어도 단순 계산이기 때문에 고정 메모리 공간만 활용하는 코드이다. 

    -Sv(abc) = 0

- (ex2)

float Sum (float list[], int n)
{
    int i;
    float total = 0;
    
    for (i = 0l i < n; i++)
        total = total + list[i];
    
    return total;
}

     - 함수를 호출할 때 배열이 전달되었기 때문에 가변 메모리 공간도 활용한다. 

     - 이 경우 시간 복잡도는 배열 전달 방법에 따라 결정된다.

- (ex3)

float rsum(float list[], int n)
{
    if (n)
        return rsum(list, n-1) + list[n-1];
    else
        return 0;
}

    - 배열이 전달되었고, 재귀 호출이 사용되었기 때문에 가변 메모리 공간을 사용한다.

    - 이 때 rsum함수가 처음을 제외하고 n번 호출되었다.

    - 한 번 호출될 때마다 float list[], int n, rsum(list, n-1) 이 세가지 환경 변수들 (매개 변수 저장공간, 함수 회귀 주소) 이 저장되며, 각각 4bytes의 크기를 갖고 있기 때문에 S = 12n 이다. 

- Call by value 

    - 함수에 배열 "값"을 직접 전달하는 방식이다.

    - 배열 크기에 비례하는 추가적인 메모리 공간이 요구된다.

    - Sv(sum) = n    // n == array size

    - (ex) Pascal

- Call by reference

    - 함수에 배열 "주소"를 전달하는 방식이다.

    - 추가적인 메모리 공간이 필요하지 않다.

    - Sv(sum) = 0

    - (ex) C

3. 시간 복잡도

- Time complexity (T)

    - 알고리즘을 수행하는데 필요한 시간이다. 

    - 컴파일 시간(Tc)과 실행 시간(Te)으로 구성되는데, 컴파일은 완료되고 나면 더이상 수행되지 않으므로 실행 시간을 더 중요시한다.

    - 실행 시간은 컴퓨터 하드웨어 환경에 따라 다르다.

    - 따라서 실제 수행 시간보다는 명령문의 수를 시간 복잡도로 간주하여 사용한다.

- 실행 명령문 표

    - 한 문장에 포함된 명령문의 수 (steps) 를 결정한다.

    - 이 문장이 반복 실행되는 빈도 (frequency) 를 결정한다.

    - (명령문 수) x (빈도)로 이 문장의 총 실행 횟수를 계산한다.

    - 이 때 함수 헤더, 변수 선언, 블록의 시작과 끝은 명령문으로 간주하지 않는다.

    - Σ steps * frequency

- iterative sum 

float sum (float list[], int n) {     // 1
    int i;                            // 2
    float temp = 0;                   // 3
    for (i = 0; i < n; i++)           // 4
        temp += list[i];              // 5
    return temp;                      // 6
}                                     // 7

- recursive sum

float rsum (float list[], int n) {            // 1
    if(n)                                     // 2
        return rsum(lsit, n-1) + list[n-1];   // 3
    return 0;                                 // 4
}                                             // 5

- matrix addition

void add() {                              // 1
    int i, j;                             // 2
    for (i = 0; i < rows; i++)            // 3
        for (j = 0; j < cols; j++)        // 4
            c[i][j] = a[i][j] + b[i][j];  // 5
}                                         // 6

4. 점근적 표기법 

- 입력의 수 n이 매우 커질 때 알고리즘의 복잡도가 증가하는 패턴을 근사적으로 표현하는 것이다. 

- 알고리즘의 성능을 비교하는 데 사용한다.

- n이 매우 증가하는 경우를 가정하여 시간 복잡도의 상한선, 하한선, 상한-하한선의 존재 유무에 따라 O, Ω, θ 등의 기호로 근사적인 복잡도를 표현한다.

- 예를 들어, 두 프로그램의 시간 복잡도가 각각 n² + n, 10n 이라고 가정하자.

  n이 작을 땐 계수에 따라 좌우되겠지만, 결국 n이 커질 경우 다항식의 차수가 더 큰 영향을 미친다.

    - (n <= 9) n² + n <= 10n

    - (n > 9) n² + n > 10n

- 이와 같이 두 개의 시간 복잡도 함수의 실행 명령문의 수가 바뀌는 시점을 분기점이라고 한다. 

- 일반적으로 n이 매우 큰 경우의 수행 성능이 더 중요하다.

4-1. Big Oh O 

- "상한선"

- n₀ 이상인 모든 n에 대해서 f(n) ≦ c·g(n)을 만족하는 양의 상수 c와 n₀가  존재한다면 시잔 복잡도 함수 f(n) = O(g(n))이라고 표기할 수 있다. 이 반대의 경우도 성립한다. 

- f(n) = O(g(n)) 이라고 표기할 수 있다면, 이 알고리즘의 수행 시간이 상한선 c·g(n)을 넘지 않는다는 의미이다.

- (ex1) 

    - f(n) = 10n + 10,000 ∈ O(n)

    - c = 20, n₀ = 1,000 이라고 결정한다면

    - f(n) ≦ 20n for all n ≥ 1,000 인 상황에서 Big Oh를 사용할 수 있다.

- (ex2)

    - f(n) = n³ + n² + n ∈ O(n) 

    - c = 3, n₀ = 1 이라고 결정한다면

    - f(n) ≦ 3n³ for all n ≥ 1 인 상황에서 Big Oh를 사용할 수 있다.

- c는 최고차항의 계수와 f(n)의 항 수로 결정할 수 있다.

- n₀는 그래프를 통해서 결정할 수 있다.

- O(1) 은 n에 관계없이 항상 일정한 명령어 수 k를 갖는다는 의미이다.

4-2. Big Omega Ω

- "하한선"

- n₀ 이상인 모든 n에 대해서 f(n) ≥ c·g(n) 을 만족하는 양의 상수 c와 n₀가 존재한다면, 시간 복잡도 함수 f(n) = Ω(g(n))이라고 표기할 수 있다. 반대의 경우도 성립한다.

- n₀ 이상인 모든 n에 대해서 f(n)의 수행 시간은 하한선인 c·g(n) 보다 항상 많이 걸린다. 이 알고리즘의 수행 시간은 최소한 하한선 이상으로 걸린다는 의미이다.

4-3. Big Theta θ

- "상한-하한선"

- n₀ 이상인 모든 n에 대해서 c₁·g(n) ≤ f(n) ≤ c₂·g(n)  을 만족하는 양의 상수 c₁, c₂, n₀가 존재한다면, 시간 복잡도 함수 f(n) = θ(g(n))이라고 표기할 수 있다. 반대의 경우도 성립한다.

- n₀ 이상인 모든 n에 대해서 f(n)의 수행 시간은 하한선 (c₁·g(n))과 상한선 (c₂·g(n)) 사이에 존재한다는 의미이다.

4-4. 시간 복잡도 함수의 종류

- O(1) = constant (Fast)

- O(log n) = logarithm

- O(n) = linear

- O(n log n) = log linear

- O(n²) = quadratic

- O(n³) = cubic

- O(2ⁿ) = exponential

- O(n!) = factorial (Slow)

- O(1) ~ O(n²) : 다루기 쉽기 때문에 n이 클 때 유용하다.

- O(2ⁿ) ~ O(n!) : 다루기 어렵기 때문에 n이 아주 작을 때 유용하다.

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

1. 재귀호출

- 함수가 실행 중에 자기 자신을 다시 호출하는 것이다.

- 같은 작업을 반복하는데 조금씩 상황이 바뀌는 경우에 사용한다.

- 함수에 반드시 종결 조건이 있어야 한다.

- Divide & Conquer 전략에 사용된다.

- 재귀 호출문은 if-else나 while문을 활용한 반복문으로 바꿀 수 있다.

- 컴파일러의 관점에서 재귀 호출은 새로운 함수를 호출하는 것과 같다.

- 따라서 함수를 호출할 때마다 함수의 지역 변수, 복귀 주소 등 컨텍스트 정보를 활성 레코드에 저장해야 한다.

- 장점 : 알고리즘을 깔끔하게 표현할 수 있다.

- 단점 : 함수를 실행할 때마다 메모리에 환경 변수를 저장하기 때문에 메모리의 소모가 일어난다.

2. 팩토리얼 예제

- n! = 1 x 2 x ... x (n-1) x n = (n-1)! x n

- 같은 일 (곱셈) 을 반복하면서 n = 0이면 n! = 1 이라는 종결 조건이 포함되어있기 때문에 재귀 호출을 사용할 수 있다.

long factorial (int n)
{
    if (n == 0)
        return 1;
    else 
        return n * factorial (n-1);
}

이와 같이 n = 0 이면 1을, n > 0 이면 n * (n-1)! 을 반환하는 형식으로 표현할 수 있다.

3. 최대공약수 (GCD) 예제

- 공통으로 나누는 수 중 가장 큰 수 

- 조건 (by 유클리드 호제법)

    - gcd (x, y) = gcd (y, x % y)  (if (y > 0))

    - gcd (x, 0) = x

ind gcd (x, y)
{
    if (y == 0)
        return x;
    else return gcd (y, x % y);
}

4. Binary Search 이진 탐색

- 정렬된 항목 리스트에 대해서 중간값과 크기를 비교하고 그 결과에 따라 가능성이 있는 절반의 리스트에 대해서만 과정을 반복하는 탐색 알고리즘이다.

- 한 번 비교할 때마다 탐색 대상 원소의 수가 절반으로 감소한다.

- 원소의 수가 n개일 때 이진탐색은 총 log₂ⁿ 번의 비교 횟수를 요구한다. 따라서 순차 탐색보다 속도가 빠르다.

- 조건은 리스트 안에 겹치는 숫자가 없어야 한다는 것이다. 

-while문과 if문을 이용한 이진탐색

#include <stdio.h>
int binsearch (int mylist[], int item, int left, int right);

void main()
{
    int pos, maxnum = 12, item = 60;
    int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
    pos = binsearch(mylist, item, 0, maxnum - 1);
    printf("position = %d", pos);
}

int binsearch (int list[], int item, int left, int right)
{
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (list[mid] == item)
            return mid;
        else {
            if (item < list[mid]
                right = mid - 1;
            else
                left = mid + 1;
        }
    }
    return -1;
}

- 재귀호출 형식의 이진탐색

#include <stdio.h>
int rbinsearch (int mylist[], int item, int left, int right);

void main()
{
    int pos, maxnum = 12, item = 60;
    int mylist[] = {5, 8, 9, 11, 13, 17, 23, 42, 45, 52, 60, 72};
    pos = binsearch(mylist, item, 0, maxnum - 1);
    printf("position = %d", pos);
}

int rbinsearch (int list[], int item, int left, int right)
{
    int mid;
    if (left <= right)
    {
        mid = (left + right) / 2;
        if (item == list[mid] 
            return mid;
        else if (list[mid] < item)
            return rbinsearch(list, item, mid + 1, right);
        else 
            return rbinsearch (list, item, left, mid - 1);
     }
     return -1;
 }
        

5. 하노이 타워 예제

- 세 개의 기둥과 크기가 다양한 원판이 존재한다. 

- 해결할 문제는 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮기는 것이다.

- 조건

    - 한 번에 하나의 원판만 옮길 수 있다.

    - 큰 원판이 작은 원판 위에 놓일 수 없다.

- 알고리즘

    - 세 개의 기둥 A, B, C 가 있고, A에서 B로 n개의 원판을 옮긴다.

    1) A에서 (n-1)개의 원판을 C로 옮긴다.

    2) A에 남은 1개의 원판을 B로 옮긴다.

    3) C에 있는 (n-1)개를 B로 옮긴다. 

- 기둥 a = 1, b = 2, c = 6 - a - b // a, b 제외한 빈 기둥이 c

- 총 이동횟수 : 2ⁿ - 1

#include <stdio.h>
void htower(int n, int a, int b);

int count = 0;

void main()
{
    int n;
    count = 0;
    printf("Enter disc number = ");
    scanf("%d", &n);
    htower(n, 1, 2);
    printf("# move for %d discs : %d\n", n, count);
}

void htower (int n, int a, int b)
{
    int c;
    count ++;
    if (n == 1)
        printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, b);
        
    else {
        c = 6 - a - b;
        htower(n-1, a, c);
        printf("Disc %d, moved from Pole (%d) to (%d)\n", n, a, c);
        htower(n-1, c, b);
    }
}

- Time complexity 시간 복잡도 

    - t(1) = 1 : 하나의 디스크 옮기는데 필요한 시간

    - time to move n disks : t(n)

        - t(n) = 2 t(n-1) + 1

                 = 2 (2 t(n-2) + 1) + 1

                 = ...

                 = 2ⁿ⁻¹ + 2ⁿ⁻² + ... + 2¹ + 2⁰

                 = 2ⁿ - 1 ≅ 2ⁿ

    - t(n) = O(2ⁿ) 

    → n 이 크면 사용하지 않는 것이 좋다.

6. Permutation 순열

- 순서를 다르게 나열하는 방법의 수

- {a, b, c, d}  → ₄P₄ = 4! = 24

a) (a, Perm (b, c, d))  →  Perm(b, c, d) = (b, Perm (c, d)), (c, Perm (b, d)), (d, Perm (b, c)) 

b) (b, Perm (a, c, d))

c) (c, Perm (a, b, d))

d) (d, Perm (a, b, c))

// i : start index of range
// n : end index of range

void perm(char list[], itn i, int n)
{
    int j;
    if (i == n)      // list print
    { 
        for (j = 0; j <= n; j++)
            printf("%c", list[j]);
        printf("   ");
    }
    else {
        for (j = i; j <= n; j++) {
            Swap(list[i], list[j]);    // 두 수 교환
            perm(list, i + 1; n);
            Swap(list[i], list[j]);
        }
    }
}
    

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

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

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "데이터사이언스개론", 박동철 교수님

1. Data Science Process

데이터 사이언스의 기본 원리는 데이터 마이닝이다. 데이터 마이닝은 상당히 잘 이해된 단계를 가진 process이다.

데이터 사이언티스트는 실생활의 문제를 하위 작업으로 분리한다.

하위 작업들의 솔루션들이 모여서 전체적인 문제를 해결할 수 있다.

문제의 기저가 되는 공통적인 데이터 마이닝 작업이 존재한다. 

(ex) classification, regression, clustering, association rule discovery

좋은 데이터 과학자가 되기 위해서는 다양한 공통적인 데이터 마이닝 작업을 해결하는 방법을 알아야 하고, 문제를 이렇게 공통적인 작업들로 나눌 수 있어야 한다.

각각의 하위 작업들은 그에 맞는 데이터 마이닝 기법으로 병렬처리 된다. 작업을 나눌 때 마이닝 방법을 생각해놓는 것이 좋다.

2. Common Data Mining Tasks

- classification : 분류 

- regression (a.k.a. value estimation) : 회귀 (value 추정)

- similarity matching : 유사도 매칭

- clustering : 군집화

- co-occurrence grouping (a.k.a. association rule discovery) : 동시발생 (관계 규칙 발견)

- profiling (a.k.a. behavior description) : 프로파일링 (행동 묘사)

- link prediction : 연관성 예측 (ex. recommendation)

- data reduction : 데이터 사이즈 줄이기 (불필요한 데이터 제거, 형태 변환 등)

- causal modeling : 인과관계 모델링

2-1. Classification 분류

모집단의 각 개체가 어떠한 클래스의 집합에 속할지 예측하는 방법이다. 

주로 상호배타적인 클래스로 분류할 때 사용한다.

분류에서 끝나는 것이 아니고, 분류를 학습하여 "예측" 하는 데 활용한다. → 지도학습에 활용

각각의 개체를 instance라고 하고, 속성을 attribute라고 한다.

예측의 대상이 되는 속성(클래스)를 classificaiton target 이라고 한다.

그리고 그 타겟들은 이미 상호배타적으로 설정되어 있다.

예를 들면, 연봉, 성별, 나이 등의 데이터로 이 사람이 어떠한 물건을 살지 안살지 예측하는 것이다.

이때 타겟은 "물건을 산다" 라는 속성이고, 클래스는 Yes 또는 No 이다.

일반적인 과정 : 훈련 데이터셋 → 데이터의 클래스를 묘사하는 모델 설정 (모델링) → 새로운 인스턴스가 주어질 때, 해당 모델을 적용하여 추측된 클래스 생성

비슷한 작업으로 scoring이나 class probability estimation 이 있다.

이는 각 개체가 각 클래스에 속할 확률을 도출하는 것이다.

예를 들어, 위의 예시에서 (Lee, 42000, male, 44) → (YES : 80%, NO : 20%) 이렇게 각 개체에 대해 클래스를 가질 확률을 계산한다.

2-2. Regression 회귀

각 개체가 특정 변수에 대해 어떠한 숫자 값을 가질 것을 예측하는 모델이다.

value estimation 이라고도 불린다.

예를 들어, 특정한 키의 사람은 어떤 값의 몸무게를 가질지 예측하는 것이다.

일반적인 과정 : 훈련 데이터셋이 주어질 때, 각 개인에 대해 특정 변수 값을 묘사하는 모델 설정 → 새로운 개체에 모델을 적용하여 측정된 값 생성

classification과의 차이점

- classification은 인스턴스의 "클래스"를 예측하는 것이다.  (ex. YES / NO)

- regression은 인스턴스와 관련된 "숫자 값"을 예측하는 것이다.   (ex. 178)

2-3. Similarity Matching 유사도 매칭

알고있는 데이터를 기반으로 유사한 데이터를 찾는 모델이다.

일반적인 과정 : 두 개체 사이의 거리 측정 → 한 개체에 대해서 가장 작은 거리를 갖는 개체 탐색

데이터의 종류가 다양하기 때문에 거리 측정에서는 유클리드 거리, 코사인 거리 등 다양한 종류의 거리를 사용한다.

(유클리드 거리) 예를 들어서, User 3 = (5, 4, 7, 4, 7), User 4 = (7, 1, 7, 3, 8) → distance ≅ 3.87

2-4. Clustering 군집화

비슷한 개체를 하나의 군집으로 묶는 모델이다. 

유사도를 측정하기 위해 "거리"를 사용한다. 

산점도에서 자연스럽게 형성되는 그룹을 분석할 때 유용하다. → 비지도학습에 활용

예를 들면, 주로 어떤 종류의 고객을 보유하고 있는지 파악할 때 사용된다.

2-5. Co-occurrence grouping 동시발생

개체들 사이의 동시 발생을 통해 관계를 찾는 모델이다. 

예를 들어서, 마트 판매 상품을 분석해보니 기저귀를 살 때 맥주도 같이 사는 손님의 비율이 높았다.

이와 같이 분석을 통해 특별 프로모션, 상품 진열, 세트 판매, 추천 등 마케팅에 활용할 수 있다.

2-6. Profiling 행동 특성 묘사

개인이나 집단의 전형적인 행동을 특징짓는 모델이다. 

normal한 행동특성에서 벗어난 행동을 탐지할 때 매우 유용하다.

프로필은 normal한 행동을 묘사하기 때문에, 갑자기 그것에 벗어난 행동을 할 때 알림을 주는 것이다.

한 예시로는 사기 탐지에 사용된다.

2-7. Link Prediction 연관성 예측

데이터 아이템들 사이의 연관성을 예측하는 모델이다. 

일반적으로 연결고리가 존재한다고 제안하고, 그 강도를 추정함으로써 사용된다.

"추천" 알고리즘에 매우 유용하다. SNS에서 친구를 추천해주거나, 넷플릭스 등에서 영화를 추천할 때 주로 사용된다.

2-8. Data Reduction 데이터 사이즈 감소

큰 데이터셋을 중요한 정보를 많이 포함하는 작은 데이터셋으로 사이즈를 줄이는 것이다.

작은 데이터셋은 다루기 쉽고, 정보나 향상된 인사이트를 보다 더 잘 드러낸다. 

하지만, 정보의 손실 또한 일어나기 쉽다는 단점이 있다.

2-9. Causal Modeling 인과관계 모델링

다른 사건에 실질적으로 영향을 주는 사건을 찾는 모델이다. 

예를 들어 담배피는 사람들 중에 이가 누런 사람과 폐암에 걸린 사람들이 있다고 할 때,

이 누래짐과 폐암이 담배때문에 발생한건지, 아니면 그냥 그런 사람들이 담배를 피는건지 인과관계를 파악하는 것이다.

3. Supervised 지도학습 vs. Unsupervised 비지도학습 Methods

3-1. Supervised

- 지도학습은 training data를 통해 이미 정답을 알고 학습을 시키는 것이다.

- 명시되어 있는 특정한 타겟이 존재한다.

- (ex) classification

Supervised data mining

- 알고싶은 특정한 타겟이 존재한다 → 답이 존재한다.

- training dataset이 반드시 존재한다 → 각각의 target value가 존재하는

- target value는 label 이라고도 부른다. 

- (ex) classification, regression, causal modeling

3-2. Unsupervised

- 비지도학습은 정답을 모르고 학습을 시키는 것이다.

- 정의해야 할 명시되어 있는 특정한 타겟이 없다.

- (ex) clustering

Unsupervised data mining

- 특정한 타겟이 아닌, 어떠한 패턴을 찾는 것이 목적이다.

- training dataset이 필요하지 않다.

- (ex) clustering, co-occurrence grouping, profiling

4. Classification vs. Regression

둘 다 supervised data mining task이다.

4-1. Classification

- 타겟이 카테고리 값이다. (ex. YES / NO, HIGH / MID / LOW)

- (ex) 이 고객이 인센티브를 받으면 이 상품을 구매할까? → YES / NO

고객이 인센티브를 받으면 (S1, S2, S3) 중에서 어떤걸 구매할 가능성이 높을까? → S1 / S2 / S3

4-2. Regression

- 타겟이 숫자 값이다. (ex. 2.5, 68)

- (ex) 이 고객이 이 서비스에 얼마를 쓸까? → $2,500

5. Data Mining and its Results

데이터 마이닝에는 두가지 단계가 있다.

5-1. Mining phase

: Historical Data (Training Data) → Data mining → Model

- training data를 통해 패턴 찾기 or 모델링

- training data는 모든 값이 명시되어 있어야 한다.

5-2. Use phase

: New data item → Model → Result

- 새로운 데이터에 패턴이나 모델 적용 → 예측

- 새로운 데이터는 알려지지 않은 class value가 존재한다.

6. Data Mining Process

: CRISP - DM (Cross Industry Standard Process for Data Mining)

산업을 통틀어서 데이터 마이닝을 위한 표준화된 Process이다.

: Business Understanding → Data Understanding → Data Preparation → Modeling → Evaluation → Deployment

기본적인 틀은 저 순서이고, 계속적인 평가를 통해 이전 과정으로 돌아가기도 하고 수정을 거듭하면서 점차 성능이 향상된다.

6-1. Business Understanding

- 해결해야 할 비즈니스 문제를 이해한다.

    -대부분 모호하거나 폭넓거나 이해하기 어려운 문제이다.

- 해결해야 할 비즈니스 문제를 하나 이상의 데이터 사이언스 문제로 간주한다.

    - 데이터 과학자들에 의해 공식화된 창의적인 문제가 성공의 열쇠가 된다.

- 문제를 여러 개의 하위 작업으로 나누고, 각각의 데이터 사이언스 문제를 해결할 방법을 디자인한다.

    - classification, regression, clustering 등

    - 각 문제에 맞는 효과적인 툴을 사용할 수 있다.

- 문제를 재구성하고 해결책을 설계하는 것은 반복적인 발견의 과정이다.

6-2. Data Understanding

- Data

    - 세운 해결책들에 이용가능한 원상태의 데이터셋이 존재한다.

    - (ex) a customer database, a transaction database, a marketing response database

- 각 데이터의 강점과 한계점을 이해한다.

    - 문제와 완벽하게 알맞는 데이터는 거의 존재하지 않는다.

    - 각 데이터로 할 수 있는 것과 없는 것을 찾고, 해당 데이터로 문제를 해결할 수 있을지 생각한다.

    - (ex) classification 을 하기 위해서는 라벨이 존재하는 데이터가 필요하다. 

- 데이터에 더 투자가 필요한지 결정한다.

    - 몇몇 데이터는 무료이지만, 몇몇 데이터는 얻기 위해 노력이 필요하거나 돈을 지불해야 한다.

6-3. Data Preparation

- 데이터를 정리해서 보다 유용한 형태로 변환한다.

    - 몇몇 데이터 분석 툴들은 특정한 형태의 데이터만 요구하기 때문이다.

- 일반적인 예시들

    - converting data to tabular format : 테이블 형식의 데이터로 변환

    - removing or inferring missing values : 결측치 제거하거나 유추

    - converting data to different types : (ex) 'male', 'female' → 0, 1  타입 변경 

    - normalizing or scaling numerical values : (ex) [-100, 100] → [0, 1]  범위 조절

    - cleaning data : (ex) Age : 999 → ? 데이터 정리

- 데이터 마이닝 결과의 질은 이 단계에 달려있다.

    - (ex) 결측치, 비정상 값, 정규화되지 않은 값

6-4. Modeling

- 가장 주요한 단계이다.

- output

   - 데이터의 규칙을 나타내는 모델이나 패턴의 일종을 생성한다.

- 데이터 마이닝의 근본적인 아이디어를 이해하는 것이 매우 중요하다.

    - 존재하는 데이터 마이닝 기술과 알고리즘을 이해하자.

6-5. Evaluation

- 데이터 마이닝 결과를 엄격하게 평가한다.

    - 다음 단계로 넘어가기 전에 그 결과가 유효하고 신뢰할 수 있다는 확신을 얻어야 한다.

- Examples

    - 모델의 예측 정확도 추정 (ex. 90%?)

    - training data를 넘어서는 모델의 보편성 확인 (overfitting 되지 않았는지)

    - 허위 경보의 비율 추정

- 결과를 즉각적으로 적용하는 대신, 일반적으로 통제된 상황에서 모델을 먼저 테스트하는 것이 바람직하다.

    - 그것이 더 쉽고 저렴하고 빠르고 안전하다.

- 데이터 사이언티스트는 그 모델과 평과 결과를 다른 데이터 사이언티스트들 외에 이해관계자들에게 쉽게 설명해야 한다.

    - 매니저, 고위 관계자, 프로그래머 등

6-6. Deployment

- 실제 상황에 데이터 마이닝 결과 (시스템)을 적용한다.

- 일반적인 시나리오

    - 새로운 예측 모델이 구현된다.

    - 그 모델은 기존의 정보 시스템과 통합된다.

- 많은 경우

    - Data Science Team : 프로토타입을 제작하고 평가한다.

    - Data Engineering Team : 모델을 생산 시스템에 적용한다.

- 적용 이후, 과정은 첫번째 단계로 되돌아간다.

    - 이 과정을 통해 얻은 통찰력과 경험을 통해 더욱 개선된 해결책을 제시할 수 있다.

7. Other Analytics Techniques & Technologies

- 데이터 마이닝 외에도 데이터 분석을 위한 다양한 기술들이 있다.

    - 통계학, 데이터베이스 시스템, 머신러닝 등

- 이러한 기술들을 익혀두는 것이 중요하다. 

    - 그것들의 목표가 무엇인지, 어떠한 역할을 하는지, 그것들의 차별점이 무엇인지

- 데이터 과학자에게 중요한 기술은 어떤 종류의 분석 기술이 특정한 문제를 해결하는데 적합한지 인지할 수 있는 것이다.

7-1. Statistics 통계학

- 분석의 바탕이 되는 많은 지식들을 제공한다.

- Examples

    - Data Summary (means, median, variance 등)

    - Understanding different data distributions

    - Testing hypotheses : 가설 테스트

    - Quantifying uncertainty : 불확실성 증명

    - Measuring correlation : 연관관계 측정

- 많은 기술들이 데이터에서 도출하는 모델이나 패턴들은 통계학에 근본을 두고 있다.

7-2. Database Querying

- Database system

    - 데이터 삽입, 질의 (쿼리), 업데이트 및 관리 할 수 있는 소프트웨어 응용 프로그램 

- Database query

    - 데이터나 데이터의 통계에 대한 특정한 요청

    - 데이터를 통해서 얻고자 하는 질문

        - (ex) 지정된 데이터 검색, 정렬, 요약 통계량 계산

    - 기술적 언어로 공식화되고 데이터베이스 시스템에 질문을 제기함

        - (ex) SQL (Structured Query Language)

- Data science vs. databases technologies

    - 데이터 사이언스에서 데이터베이스 시스템에 저장된 관심있는 데이터를 찾거나 조사하기 위해 데이터베이스 기술을 사용할 수 있다.

7-3. Machine Learning

- 컴퓨터 시스템이 명시적인 프로그래밍 없이, 데이터를 가지고 학습할 수 있는 능력을 제공하는 것이다.

    - 인공지능의 한 분야이다.

- 모델을 개발하고 모델 성능을 향상시키는 데에 데이터를 활용한다.

    - (ex) decision tree, artificial neural networks (deep learning), support vector machines, clustering, bayesian networks,...

- 하지만,이들 사이의 경계가 모호해졌다.

- 데이터 마이닝과 머신러닝은 긴밀히 연결되어있다.

    - 데이터 마이닝의 한 분야가 머신러닝으로 파생되기 시작하였다.

    - 데이터 마이닝은 머신러닝의 한 가지이다.

        - KDD (Knowledge Discovery and Data mining)

        - 둘 사이에 기술과 알고리즘은 공유된다.

    - 데이터로부터 유용하고 유익한 패턴을 찾아낸다.

- 그럼에도 불구하고 머신러닝은 성능향상, 인지능력 향상에 더욱 집중되어 있다.

    - (ex) robotics and computer vision

    - (ex) agent가 이 환경에서 학습된 지식을 어떻게 활용하는가

- 데이터 마이닝은 데이터로부터 패턴, 규칙을 찾는 것에 더욱 집중되어 있다. 

    - 상업적 응용 프로그램 및 비즈니스 문제에 특히 활용된다.

8. Examples of Applying These Techniques

- "어떤 고객이 가장 수익성이 있는가?" : Database systems (profiable can be calculated from existing data., not predict)

- "수익성이 있는 고객과 평균의 고객들 간에 정말 차이가 있는가?" : Statistics (hypothesis testing)

- "하지만 이 고객들은 정말 누구인가? 특징화 할 수 있는가?" : Data mining (profiling)

- "어떤 특정한 새로운 고객이 수익성이 있을까? 얼마나?" : Data mining (classification, regression)

수업 출처) 숙명여자대학교 소프트웨어학부 수업 "데이터사이언스개론", 박동철 교수님

1. Intro

데이터 사이언스는 다양한 형태로부터 얻은 데이터로 지식이나 인사이트를 도출하는 융합적인 학문이다.

크게 컴퓨터 사이언스, 수학과 통계학, 경영학적 지식이 요구된다. 

데이터 엔지니어는 데이터를 다루기 위한 소프트웨어와 시스템을 디자인하고 개발한다. 프로그래밍과 데이터베이스 지식을 필요로 한다. 가장 중요한 것은 데이터를 분석하기 전 전처리하는 과정을 맡는다는 것이다.

통계학자는 통계학적 이론과 방법을 실생활에 적용하여 문제를 해결한다. 통계학과 수학적 지식을 필요로 한다.

데이터 사이언티스트는 쉽게 말해서 둘 다 하는 사람이다. 분석적이고 기술적인 능력을 통해서 데이터로부터 인사이트를 도출한다. 위에서 말했듯이 프로그래밍, 통계, 경영학적 이해를 바탕으로 한다.

데이터 사이언티스트가 주로 필요로 하는 기술은 데이터 분석, 통계 분석 패키지 (R), 파이썬, 데이터 모델링, 머신러닝 등이다. 

주로 IT & 서비스 직군에서 근무하며, 교육이나 금융 분야에서도 데이터 과학자를 필요로 한다.

2. Data Science

최근 경영 산업은 전반적으로 데이터를 수집하는 능력을 가지고 있다. 

전략, 제조, 마케팅, 공급망 관리 등 모든 경영학적 측면에서 데이터 수집을 필요로 하고 있다. 

이제 거대한 양의 데이터가 생산되면서 대부분의 기업들은 경쟁우위로써 데이터 수집에 집중하고 있다.

과거에는 통계학자와 분석가가 데이터셋을 수작업으로 탐색했다면, 이제는 데이터의 양이 커지면서 수작업으로는 분석을 하기 어려워졌다.

컴퓨터와 네트워크가 중요해진 것이다.

이를 통해 데이터 과학의 원리와 기술을 더 넓은 분야에 적용하게 되었다.

3. Data Mining

데이터 마이닝은 큰 데이터셋에서 패턴을 찾는 과정이다.

경영학적 측면에서는 주로 고객의 행동을 분석하는 데 활용한다. 

고객의 패턴을 분석하여 타겟 마케팅, 온라인 광고, 추천, 신용 분석, 사기 탐색 등에 적용할 수 있다.

4. Data Science vs. Data Mining

데이터 사이언스는 데이터에서 지식을 도출하도록 하는 일련의 근본적인 원칙이다.

데이터 마이닝보다 좀 더 넓은 의미로 사용된다.

데이터 마이닝은 데이터로부터 숨겨진 패턴을 찾는 과정으로, 보통 데이터 수집 및 가공 이후 첫번째로 수행되는 과정이다.

즉, 데이터 마이닝 기술은 데이터 사이언스의 근본 원리를 실체화한 것이라고 볼 수 있다.

데이터로부터 지식을 도출할 때에는 자명하지 않으면서 수치적으로 도출되어야 한다. 

예를 들면 허리케인이 지나간 후 생수의 판매율이 20% 증가했다던가, 어떠한 과자가 기존보다 7배 많이 팔렸다던가 하는 형식으로 말이다.

또 한 가지 유명한 예시는 미국의 통신사 예시이다.

제한된 예산으로 고객이 다른 통신사로 넘어가는 것을 막을 방법을 찾아야 한다.

미국의 통신사 MegaTelco는 일반적으로 휴대폰 고객의 20%는 계약이 만료되면 다른 통신사로 떠나간다.

이제 휴대폰 시장이 포화되었기 때문에 통신사들은 고객을 유지하려고 노력하고 있다. 

회사는 몇몇 고객들의 계약 만료 전에 특별 상품을 제공하려고 한다.

이때 어떻게 최대한 고객이탈을 막을 수 있도록 상품을 제공할 고객을 고를 수 있을까.

이럴때 데이터 사이언스가 활용되는 것이다.

5. Data-Driven Decision Making (DDD)

데이터기반 의사 결정은 단순한 직관보다는 데이터 분석에 기초한 의사 결정이다. 

예를 들어, 광고를 할 때 한 사람의 경험과 직관에 기반하기보다는 소비자가 다른 광고에 어떻게 반응하는지에 대한 데이터 분석에 기초한다.

이 DDD에 데이터 사이언스가 필요하다. 

자동화된 데이터 분석을 통해 현상을 이해하기 위한 방법, 과정, 기술 등을 제공한다.

통계적으로 기업이 데이터기반 의사결정을 활용할수록 생산력이 4-6% 증가한다.

예를 들어, 마트의 고객은 주로 본인이 가던 곳만 가기 때문에 변화를 찾기 어렵지만, 아기가 태어남을 기점으로 한 번의 변화가 일어날 수 있다. 따라서 많은 상업자들은 아기가 태어난 것을 알고 새로운 고객에게 특별 상품(할인권 등)을 제공한다. 

하지만 미국의 마트 '타겟'은 이것을 넘어서서 아기가 태어나기 전, 임신 전부터 그것을 예측하여 마케팅을 했다. 그 결과 그들의 경쟁자보다 더 높은 이익을 얻을 수 있었다.

점점 더 많은 비즈니스 결정이 컴퓨터 시스템에 의해 자동화되고 있다.

미리 설계된 알고리즘을 통해 거의 실시간으로 데이터를 분석하고 의사 결정을 하고 있다.

예를 들면, 은행과 통신사에서는 사기 범죄를 제어하고, 소매 업체에서는 상품화 결정 시스템을 자동화한다. 아마존과 넷플릭스는 추천 시스템을, 광고 회사는 실시간 광고 결정 시스템을 자동화한다. 

6. Data Engineering vs. Data Science

데이터 엔지니어링과 데이터 사이언스는 다르다.

데이터 엔지니어링은 데이터를 처리하는 기술로, 시스템, 소프트웨어 디자인, 개발, 유지 및 보수 등을 포함한다. 

오라클과 같은 데이터 베이스 시스템과 하둡, 스파크와 같은 빅데이터 플랫폼 등의 소프트웨어를 개발하고 유지한다.

이들을 통해서 데이터 사이언스를 support한다.

데이터 사이언스는 앞에서도 말했지만, 데이터를 모으고 탐색하고 분석한다. 

데이터 엔지니어링 기술을 활용해서 데이터에 접근할 수 있다. 

7. Data Science and Big Data

빅데이터는 네트워크와 컴퓨팅 기술의 발달로 전통적인 데이터 처리 시스템으로 관리하기에는 너무 큰, 따라서 새로운 처리 기술이 필요한 데이터셋을 말한다.

빅데이터의 4가지 특징으로는 크기, 다양성, 속도, 정확성이 있다.

빅데이터 기술은 위의 4가지 특징 (4V)을 다룬다.

이를 위해 데이터 사이언스를 활용한다.

예시로는 Hadoop, HBase, MongoDB, Spark 등이 있다.

데이터와 데이터로부터 유용한 지식을 도출하는 능력은 핵심 전략 자산으로 간주되어야 한다.

이는 최상의 결과를 내기 위해 적절한 데이터와 데이터 사이언스 기술 두가지 모두에 투자해야한다는 것이다.

8. Data-Analytic Thinking

실생활 문제에 직면했을 때, 우리는 그 문제를 "분석적으로" 바라보아야 한다. 데이터가 성능을 향상시킬 수 있는지 여부와 그 방법을 정량적으로 평가해야 한다.

데이터 분석적 사고는 일련의 근본적인 개념과 원칙에 의해 가능해진다. 시스템적인 틀(framework) 을 구조화해야 한다.

데이터 분석적 사고를 통해서 다른 사람들과 능숙하게 교류할 수 있고, 데이터기반 의사 결정을 향상시킬 수 있으며 데이터 중심의 경쟁 위협을 바라보는 사고를 기를 수 있다.

최근 산업, 기업에서는 수익을 높이고 비용을 절감하기 위해 데이터 사이언스 팀을 만들고 있고, 주요 전략 요소에 데이터 마이닝을 사용하고 있다.

데이터 사이언티스트가 아니더라도 매니저, 마케터, 경영 전략가 등의 직업에서도 데이터 사이언스를 활용한다. 

9. Example of Fundamental Concepts

1) 자료에서 유용한 지식을 추출하기 위해 체계적인 절차를 밟는다.

체계적인 절차란 명확히 정의된 단계를 말한다. (ex) 문제 분석 -> 모델링 -> 면밀한 평가

이러한 과정은 데이터에 대한 우리의 생각을 구조화하기 위한 틀을 제공한다.

2) 대량의 데이터에서 관심있는 개체에 대한 정보 속성을 찾는다.

즉, 우리에게 필요한 정보를 제공하는 변수를 찾는 것이다.

3) overfitting을 피한다.

모델링을 하는 이유는 새로운 데이터를 "예측"하기 위함이다. 

overfitting된 모델은 특정 training data에만 적합할 뿐, 새로운 데이터에 대해서는 좋은 성능을 낼 수 없다. 

4) 마이닝 결과를 신중하고 객관적으로 평가한다.

우리가 도출한 결과가 얼마나 더 나은지 공식화 해야 한다.

단순히 더 낫다가 아니라 얼마나 더 나은지 보여주어야 한다.

10. Engineering side of Data Science

데이터 사이언티스트는 두가지 종류의 능력을 갖춰야 한다.

1) Science

- 이론적인 개념과 원칙을 실제 상황에 적용하는 능력

- ex) logistic regression, support vector machines

2) Technology

- 트렌드에 맞는 (상황에 맞는, 인기있는) 프로그래밍 언어와 툴을 사용하는 능력

- ex) Hadoop, MongoDB, Spark, TensorFlow 

최근에는 특정 종류의 소프트웨어 툴에 익숙하지 않은 데이터 과학자를 상상하기 힘들다. 

그럼에도 우리는 기술보다 과학에 조금 더 집중해야 한다. 우세한 기술들은 빠르게 바뀌기 때문이다.

수업출처) 숙명여자대학교 통계학과 '통계수학' 수업, 윤재은 교수님

1. 역행렬

: 정방행렬 A 에 대해서 AB = BA = I 를 만족하는 정방행렬 B, A⁻¹로 표시

역행렬이 존재하기 위한 조건은 A가 정방행렬이면서 det(A) ≠ 0이어야 한다.

* 2차 정방행렬 역행렬 구하는 방법

A = [a b; c d]

|A| = ad - bc

A⁻¹ = 1 / (ad - bc) [d -b; -c a]

2. 역행렬 성질

Th3.1 > 정방행렬 A의 역행렬이 존재하는 경우 그 역행렬은 유일하다.

Th3.2 > A의 역행렬이 존재하기 위한 필요충분조건은 |A| ≠ 0이다.

Th3.3 > A가 가역행렬이면 A⁻¹ 역시 가역이며 (A⁻¹)⁻¹ = A 이다.

** 가역 = 정칙 = 역행렬 존재

Th3.4 > (A⁻¹)T = (AT)⁻¹

Th3.5 > A와 B가 각각 정칙이면 AB 역시 정칙이며 다음이 성립한다.

> (AB)⁻¹ = B⁻¹ A⁻¹

> (ABC)⁻¹ = C⁻¹ B⁻¹ A⁻¹

Th3.6

> A가 가역행렬일 때 kA도 가역행렬이고 (kA)⁻¹ = 1/k A⁻¹ 이다.

> A가 가역행렬일 때 Aⁿ 도 가역행렬이고, (Aⁿ)⁻¹ = (A⁻¹)ⁿ 이다.

Th3.7> A가 정칙일 때, PA = QA 이면 P = Q 이다.

Th3.8 > Ax = b 에서 A가 정칙이면 x = A⁻¹ b 이다.

→ 연립방정식의 풀이에 활용할 수 있음

3. 행렬의 분할

: 행렬을 블록화하여 간단히 나타낼 수 있다.

* 분할행렬의 전치행렬은 각각의 분할된 행렬을 전치한 것과 같다.

* 분할행렬의 곱