Direct Access Array & Sorted Array & Tree

Tree

n개의 노드가 존재할 때 가장 작은 tree의 높이가 Ω(log2 n) = log2(n+1) - 1임을 증명해보자.

높이가 가장 작은 트리를 만들기 위해서 완전 이진 트리이면 된다. 완전 이진 트리의 경우 자식이 생길때마다 노드가 2개씩 증가하게 되며, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다. 

 

Inductive Proof

트리의 시간 복잡도를 T(n) = clog2 n이라고 가정했을 때, clog2 n = clog2 (n+1) - O(1)이 된다. O(1) = clog2 (1+1/n)이 되며, n의 값이 커질수록 O(1)의 값은 0에 수렴하기 때문에 tree의 높이는 Ω(log2 n) = log2(n+1) - 1 식을 만족한다.

 

Direct Access Array

배열의 인덱스와 키를 1:1 로 매칭시켜서 바로 접근하면 각 아이템에게 유일한 키 k∈{0,...,u−1}를 부여하고, 각 아이템을 배열 인덱스 k 에 저장할 수 있다. 키는 유일하기 때문에 배열 A[k] 에 접근하면 원하는 키를 O(1)으로 바로 찾을 수 있다.

 

이렇게 인덱스와 키를 1:1 로 매칭시키고 해당하는 인덱스에 그 키에 해당하는 아이템을 저장하는 자료 구조를 Direct Access Array라고 한다.

 

하지만, 여기에는 큰 문제점이 있는데 키 공간의 크기 u가 크면 u의 크기를 갖는 배열을 만들 때 사용하는 공간이 매우 낭비된다.

ex)

10개의 알파벳을 키로 갖는다고 한다면 모든 키를 인덱스로 가지는 배열을 만들어야 하는데, 이러면 하나의 비트를 저장하려고 해도 26^10 → 17.6TB의 공간이 필요하다.

 

그렇다면 위의 direct access array로 인한 배열의 공간 낭비를 해결하기 위해 linked list를 이용하면 어떨까? 이 방식으로 진행하더라도 문제가 발생한다. linked list로 진행하게 되면, 원하는 아이템까지 도달하기 위해서 처음부터 해당 아이템이 포함된 인덱스까지 돌아야하기 때문에 O(n)이라는 비효율적인 시간 복잡도가 발생하게 된다.

 

Birthday dataset

Approach 1.  unordered array using set

시간 복잡도: O(n)

// unordered array using set
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <int> v;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            v.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    for (int i = 0; i < v.size(); i++) { // ---> O(n)
        auto it = std::find(v.begin() + (i+1), v.end(), v[i]);
        if (it != v.end()) {
            contain.push_back(v[i]);
            cnt += 1;
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }

    }

    fp.close();

}

 

build: n

find: n

insert & delete: n

find_min & find_max: n 

find_next & find_prev: n

Approach 2.  sorted array set

1. Selection Sort를 이용한 경우

시간 복잡도: O(n^2)

// selection sort
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <int> v;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            v.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    // selection sort 구현
    for (int i = 0; i < n; i++) { // ---> O(n^2)

        min = i;

        for (int j = i+1; j < n; j++) { // ---> O(i)
            if (v[min] > v[j]) {
                min = j;
            }
        }

        if (v[min] < v[i]) {  // ---> O(1)
            int tmp = v[i];
            v[i] = v[min];
            v[min] = tmp;
        }
    }

    for (int i = 1; i < n; i++) {

        if (v[i - 1] == v[i]) {
            cnt += 1;
            contain.push_back(v[i - 1]);
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }
    }

    fp.close();

}

 

2. Insertion Sort를 이용한 경우

시간 복잡도: O(n^2)

// insertion sort
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <int> v;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            v.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    // insertion sort 구현
    for (int i = 1; i < n; i++) { // ----> O(n^2)
        int insert_index = i;
        int insert_index_value = v[i];

        // 현재 범위에서 데이터 삽입 위치 찾기
        for (int j = i - 1; j >= 0; j--) { // ----> O(i) 
            if (v[j] < v[i]) { // 해당 데이터를 삽입할 위치 찾기
                insert_index = j + 1;
                break;
            }
			
            // 맨 앞에 데이터 삽입하는 경우 
            if (j == 0) { 
                insert_index = 0;
            }
        }

        // 해당 데이터 삽입을 위해 데이터들 한 칸씩 뒤로 밀기
        for (int k = i; k > insert_index; k--) { // ----> O(i)
            v[k] = v[k - 1];
        }

        v[insert_index] = insert_index_value; // ----> O(1) 
    }

    for (int i = 1; i < n; i++) {

        if (v[i - 1] == v[i]) {
            cnt += 1;
            contain.push_back(v[i - 1]);
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }
    }

    fp.close();

}

 

3. Merge Sort를 이용한 경우

시간 복잡도: O(nlogn)

// merge sort
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

vector <int> v(97, 0);
vector <int> tmp(97, 0); // 임시 저장 벡터

void merge_sort(int s, int e);
int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 1; i <= n; i++) {
            int birthday;
            fp >> birthday;
            v[i] = birthday;
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    // merge sort 구현
    merge_sort(1, n);

    for (int i = 1; i < n; i++) {

        if (v[i] == v[i+1]) {
            cnt += 1;
            contain.push_back(v[i+1]);
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }
    }

    fp.close();

}

void merge_sort(int s, int e) {
    if (e - s < 1) {
        return;
    }

    int m = s + (e - s) / 2; // 분할

    merge_sort(s, m); // ----> O(n/2) 
    merge_sort(m + 1, e); // ----> O(n/2) 

    for (int i = s; i <= e; i++) {
        tmp[i] = v[i];
    }

    int k = s;
    int index1 = s; // 앞쪽 그룹 시작점
    int index2 = m+1; // 뒤쪽 그룹 시작점

    // 두 그룹 병합 ----> O(n) 
    while (index1 <= m && index2 <= e) {
        // 뒤쪽 그룹의 데이터가 작은 경우
        if (tmp[index1] > tmp[index2]) {
            v[k] = tmp[index2];
            k += 1;
            index2 += 1;
        }
        // 앞쪽 그룹의 데이터가 작은 경우
        else {
            v[k] = tmp[index1];
            k += 1;
            index1 += 1;

        }
    }

    // 한쪽 그룹이 모두 선택되고 남아있는 그룹의 데이터 정렬하기
    while (index1 <= m) { // 앞쪽 그룹의 데이터가 작은 경우
        v[k] = tmp[index1];
        index1 += 1;
        k += 1;
    }
    while (index2 <= e) { // 뒤쪽 그룹의 데이터가 작은 경우
        v[k] = tmp[index2];
        index2 += 1;
        k += 1;
    }
}

 

build: nlog2 n

find: log2 n

insert & delete: n

find_min & find_max: 1

find_next & find_prev: log2 n

Approach 3.  direct access array set

// direct access array set
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <vector<int>> v;

    v.resize(1232);

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            v[birthday].push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    for (int i = 0; i < v.size(); i++) { // ---> O(n)
        if (v[i].size() >= 2) {
            cnt += 1;
            contain.push_back(v[i][0]);
        }
    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }
        
    }

    fp.close();

}

 

build: u

find: 1

insert & delete: 1

find_min & find_max: u

find_next & find_prev: u

 

참고 자료:

https://klioop.tistory.com/43 

Universal Hashing 이해하기