자료구조 3주차

Array for Search, Insert, Delete

• Search, Insert, Delete
  • 자료구조의 가장 중요한 연산들
  • 모든 자료구조에 해당하는 것은 아님
  • Item : 저장되는 대상을 부를 이름
    • 정수만 가능한 것으로 생각하자…일단은
  • file system에 file을 넣고 빼고 하는 과정
• Array
  • 메모리에 연속되게 저장됨
• How to Store Items in an Array?
  • Packed vs Unpacked
    • Packed : 한쪽으로 모임
    • Unpacked : 사용 안 하는 자리가 중간 중간 존재
    • 배열이 항상 가득 찬 것은 아님
    • 빈 자리를 한 쪽으로 모은다?
  • Sorted vs Unsorted
    • Item들이 정렬된 상태를 유지하느냐 아니냐
  • Item의 개수를 표시하는 변수가 따로 필요
    • 값이 할당되어 있지 않는 부분을 따로 알려주는 게 없음
    • 프로그래머가 자기 마음대로 방법을 정해야 함

---

1. Packed, UnSorted 성능

• Search : O(n) - 최악의 상황 가정
• Insert : [Search, O(n)], O(1)
  • Search 시간 + 상수 시간 = O(n)+O(1) = O(n)
• Delete : [Search, O(n)], O(1) == O(n)
  • 지우고 맨 끝에 있는 값을 그 자리로 옮김
• Search가 크기 때문에 n이 클 땐 시간 크게 걸림
• n이 크더라도 아카이브 같은 경우엔 사용

2. Packed, Sorted

• Binary Search!!
• Item의 개수를 표시하는 변수가 따로 필요
  • Search : O(log n)
  • Insert : [Search, O(log n)], O(n)
    • Sorted니까 정해진 위치에 넣어야 하므로 중간에 들어가게 되면
    • 나머지를 옆으로 하나씩 복사하므로 시간이 O(n)이 걸림
  • Delete : [Search, O(log n)], O(n)
  • Search는 빠르지만 Insert, Delete가 느림

3. Unpacked, UnSorted

• 빈 자리들이 흩어져 있음

• Item별로 사용 중인지 아닌지 표시 필요
  • Search : O(n)
  • Insert : [Search, O(n)], O(n)
    • → 기술추가 시 : O(1)
    • Free List Head 변수를 추가
      • 해당 값의 인덱스에 할당 된 변수는 다음 빈 값의 인덱스 값을 가짐
      • 맨 마지막은 특수한 의미 부여한 숫자를 값으로 가짐
    1. 안 쓰는 칸을 찾은 뒤에
    2. 값을 넣기
  • Delete: [Search, O(n)], O(1)
    • 자료형 하나 당 저장할당량이 크다면 이게 더 효율적!
      • 안쓴다고 표시만 하면 되기 때문(Marking)
• 디렉토리는 어떤 가정을 하고 있냐면 n이 아주 크지 않다고(별로 안 크다) 가정함

4. Unpacked, Sorted

• Binary Search!!!……????

• 기술 두 번째!

• 과정
  • 처음 넣을 때는 packed 형태로 들어감
  • 첫 delete를 하기 전까진 중간에 빈 자리 생성 x
  • 위 그림의 X는 모두 delete된 자리라는 것을 알 수 있음
  • 제일 오른쪽 자리에 대한 변수가 필요
  • 지워졌더라도 값은 그대로 살려두는 것
  • 살아있는 값들과 죽어있는 값들 모두를 봤을 때 sorting이 된 것으로 유지
• 성능
  • Search : O(n) → 기술 추가 → O(log n)
  • Insert : [Search, O(log n)], O(n)
    • 삽입할 위치가 죽어있는 값들이 있는 위치라면 그냥 그 값을 덮어쓰면 되지만 모두 살아있는 값이면 옆으로 한 칸씩 밀어야함(빈 자리까지)
  • Delete: [Search, O(log n)], O(1)
  • 즉 Delete가 매우 빠름
• 성능이 어떻게 될 지 생각을 해보자

---

1. Packed, Unsorted 코드 구현

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int A[100];
int S, loc;

int srch(int x) {
    for (int i = 0; i < S; i++) {
        if (A[i] == x) {
            loc = i;
            return 1;
        }
    }
    return -1;
}
void insert(int x) {
    A[S] = x;
    S++;
}
void del(int x) {
    A[loc] = A[S - 1];
    S--;
}
int main() {
    char c;
    int x, i;
    while (1) {
        printf("S = %d\n", S);
        for (i = 0; i < S; i++) {
            printf("%3d    ", i);
        }
        printf("\n");
        for (i = 0; i < S; i++) {
            printf("%3d    ", A[i]);
        }
        printf("\n");
        scanf(" %c", &c);
        if (c == 's') {
            scanf("%d", &x);
            if (srch(x) == -1) {
                printf("%d Not Found!\n", x);
            }
            else {
                printf("%d Found at Index %d\n", x, loc);
            }
        }
        else if (c == 'i') {
            scanf("%d", &x);
            if (srch(x) == -1) {
                insert(x);
            }
            else {
                printf("%d already exist", x);
            }
        }
        else if (c == 'd') {
            scanf("%d", &x);
            if (srch(x) == -1) {
                printf("%d doesn't exist", x);
            }
            else {
                del(x);
            }
        }
    }
}

2. Packed, Sorted

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int A[100];
int S, left_dir, right_dir;

int srch(int x) {
    int s, e, m;
    s = 0;
    e = S - 1;
    while (s <= e) {
        m = (s + e) / 2;
        if (A[m] == x) {
            left_dir = right_dir = m;
            return 1;
        }
        else if (A[m] < x) {
            s = m + 1;
        }
        else {
            e = m - 1;
        }
    }
    left_dir = e;
    right_dir = s;
    return -1;
}

void insert(int x) {
    int i;
    for (i = S-1; i >= right_dir; i--) {
        A[i+1] = A[i];
    }
    A[right_dir] = x;
    S++;
}
void del(int x){
    int i, j;
    for (i = right_dir; i < S; i++) { //left_dir든 right_dir든 이미 search 성공했다면, 
        // 두 값이 같으므로 뭐를 쓰던 상관없음
        A[i] = A[i + 1];
    }
    S--;
}
int main() {
    char c;
    int x, i;
    while (1) {
        printf("S = %d\n", S);
        for (i = 0; i < S; i++) {
            printf("%3d    ", i);
        }
        printf("\n");
        for (i = 0; i < S; i++) {
            printf("%3d    ", A[i]);
        }
        printf("\n");
        scanf(" %c", &c);
        if (c == 's') {
            scanf("%d", &x);
            if (srch(x) == -1) {
                printf("%d Not Found!\n", x);
            }
            else {
                printf("%d Found at Index , and it exist between %d and %d\n", x, left_dir, right_dir);
            }
        }
        else if (c == 'i') {
            scanf("%d", &x);
            if (srch(x) == -1) {
                insert(x);
            }
            else {
                printf("%d already exist", x);
            }
        }
        else if (c == 'd') {
            scanf("%d", &x);
            if (srch(x) == -1) {
                printf("%d doesn't exist", x);
            }
            else {
                del(x);
            }
        }
    }
}

---

3. Unpacked, Sorted

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int A[100];
int B[100]; // Mark 배열 생성
int S, left_dir, right_dir;

int search(int x) {
    int s, e, m;
    s = 0;
    e = S - 1;
    while (s<=e) {
        m = (s + e) / 2;
        if (A[m] == x) {
            left_dir = right_dir = m;
            if (B[m] == 0) {
                return -1;
            }
            else {
                return 1;
            }
        }
        else if (A[m] > x) {
            e = m - 1;
        }
        else {
            s = m + 1;
        }
    } // 다 통과 시 e = s-1;
    left_dir = e;
    right_dir = s;
    return -1;
}

void insert(int x) {
    int i, j;
    if (left_dir == right_dir) {
        B[left_dir] = 1;
    }
    else if (left_dir ==-1) { // 왼쪽 맨 끝부터 입력해야함
        i = right_dir; // i=0 
        while (B[i] != 0 && i < S) { // 0부터 하나씩 올라가면서 빈칸 찾기
            i++;
        }
        if (i == S) { // 빈칸이 아무 것도 없으면?
            for (j = S-1; j >=right_dir; j--) { // right_dir==0
                A[j + 1] = A[j]; // 싸그리 다 올려버리기
                B[j + 1] = B[j];
            }
            A[right_dir] = x;
            B[right_dir] = 1;
            S++;
        }
        else {
            for (j = i - 1; j >= right_dir; j--) {
                A[j + 1] = A[j]; // 중간에 빈칸이 발견돼서 i가 S가 아니라면!
                B[j + 1] = B[j];
            }
            A[right_dir] = x;
            B[right_dir] = 1;
        }
    }
    else if (right_dir == S) { //오른쪽 방향으로 들어갈 때
        i = left_dir; // i 가 배열 끝 값을 가리키는 인덱스를 의미하도록 함
        while (B[i] != 0 && i >= 0) // 인덱스--하면서 탐색
            i--;
        if (i == -1) { // 빈칸 제로면
            A[S] = x;
            B[S] = 1;
            S++;
        }
        else { // 빈칸이 중간에 있으면
            for (j = i; j < right_dir; j++) {
                A[j] = A[j + 1];
                B[j] = B[j + 1];
            }
            A[S - 1] = x;
            B[S - 1] = 1;
        }
    }
    else { // 들어가야 할 위치가 중간 어디쯤이라면
        i = left_dir; // 왼쪽부터 탐색
        while (B[i] == 1 && i >= 0) {
            i--;
        }
        // 왼쪽에 빈자리 O
        if (i != -1) {
            for (j = i; j < left_dir; j++) {
                A[j] = A[j+1];
                B[j] = B[j + 1];
            }
            A[left_dir] = x;
            B[left_dir] = 1;
        }
        else { // 왼쪽에 빈 자리 x, 자연스럽게 오른쪽에 빈 자리가 있다고 생각
            i = right_dir;
            while (B[i] == 1 && i < S)
                i++;
            if (i != S) {
                for (j = i - 1; j >= right_dir; j--) {
                    A[j + 1] = A[j];
                    B[j + 1] = B[j];
                }
                A[right_dir] = x;
                B[right_dir] = 1;
            }
            else {
                for (j = S - 1; j >= right_dir; j--) {
                    A[j + 1] = A[j];
                    B[j + 1] = B[j];
                }
                A[right_dir] = x;
                B[right_dir] = 1;
                S++;
            }
        }
    }
}
void del(int x) {
    B[left_dir] = 0;
}
int main() {
    char c;
    int x, i;
    while (true) {
        printf("S = %d\n", S);
        for (i = 0; i < S; i++) {
            printf("%3d    ", i);
        }
        printf("\n");
        for (i = 0; i < S; i++) {
            printf("%3d    ", A[i]);
        }
        printf("\n");
        for (i = 0; i < S; i++) {
            printf("%3d    ", B[i]);
        }
        printf("\n");
        scanf(" %c", &c);
        if (c == 's') {
            scanf("%d", &x);
            if (search(x) == -1 && left_dir == right_dir) { // 값은 찾았지만 죽은 값
                printf("%d Not Found. Stored as deleted value at %d\n", x, left_dir);
                B[left_dir] = 1;
            }
            else if (search(x) == -1 && left_dir != right_dir) { // ㄹㅇ 걍 없음
                printf("%d Not Found! Should be between %d and %d\n", x, left_dir, right_dir);
            }
            else { // 찾고 생존한 값
                printf("%d Found at Index %d\n", x, left_dir);
            }
        }
        else if (c == 'i') {
            scanf("%d", &x);
            if (search(x) == -1) {
                insert(x);
            }
        }
        else if (c == 'd') {
            scanf("%d", &x);
            if (search(x) == 1) {
                del(x);
            }
        }
        else if (c == 'q') {
            break;
        }
        else {
            printf("???\n");
            break;
        }
    }
}