다양한 자료구조 (C# or C++)

[ggjae]

자료구조

자료의 집합을 의미하며, 무수히 많은 오브젝트나 데이터들에 대한 처리를 효율적으로 수행할 수 있도록 구분하여 표현한 것이다. 자료구조를 사용하는 목적은 자료를 효율적으로 저장하고, 관리하기 위해 사용하며 잘 선택된 자료구조는 실행시간을 단축시켜주고, 메모리 용량의 절약을 이끌 수 있다.

배열 (어레이)

다수의 데이터를 그룹화하여 효율적으로 관리할 수 있는 자료구조로, 인덱스가 존재하여 데이터의 접근을 O(1)만에 데이터에 접근할 수 있다. 하지만 연속적인 메모리의 사용으로써 중간의 위치에 있는 데이터 삭제나 삽입은 비효율적이다. 배열은 조회에 O(1), 원소탐색은 O(n), 이미 할당된 공간에 삽입 O(1), 삭제는 O(N)만큼의 시간복잡도를 나타낸다.

링크드리스트

데이터필드와 링크필드로 이루어져있고, 항목들을 노드에 분산하여 저장하는 리스트이다. 연결리스트의 장점으로는 삽입과 삭제가 용이하며, 연속된 메모리 공간이 필요하지 않다는 것과 크기에 제한이 없다는 것이 큰 특징이다. 조회에는 O(n)의 시간복잡도, 원소탐색은 O(n), 맨 앞이나 맨 뒤에 삽입하는 경우 O(1)이지만, 중간에 삽입하는 경우 이전 노드를 먼저 조회하여야 하므로 O(n)이 소모된다. 삭제의 경우에도 이전 노드를 조회하여야 하므로 O(n)이 소모된다.

리스트 구현

구현시에는 노드 구조체를 만들어 이 구조체는 데이터와, Node포인터 자료형의 next라는 link로 이루어져 있고, Addrear(int val)과 같이 맨 뒤, 혹 Addfront 맨 앞에 이 구조체를 추가하여 연결시킴으로써 리스트를 구현할 수 있다. 아래는 코드

struct Node {
    int data;
    struct Node* next;
};
struct Node *pStart = null;, struct Node *pEnd = null;
void addrear(int val)
{
    struct Node *Current;
    Current = (struct Node *) malloc (sizeof(struct Node));
    Current->data = val;
    Current->next = NULL;
    pEnd->next = Current;
    pEnd = Current;
}

배열과 리스트의 차이

1. 배열은 인덱스를 사용하여 특정 원소 접근이 가능하다. Random Access가 가능하다.
2. 배열은 Array가 선언될 때 Stack 메모리 영역에 할당하지만, 리스트는 새로운 노드가 추가될 때 Heap 영역에 할당한다.
3. 링크드리스트의 맨 앞이나, 맨 뒤에 추가하거나 맨 앞, 맨 뒤를 삭제하는 경우에는 O(1)밖에 걸리지 않지만, Array의 삽입과 삭제는 O(n)만큼 소요된다.

맵 (내부적으론 RBT) : 해당 키값에 어떤 벨류가 들어있는가?

삽입과 동시에 정렬이 필요할 때, 많은 데이터를 보관해야 하고, 검색이 빨라야할 때 사용하게 된다. 데이터의 삽입과 삭제에는 오랜 시간이 사용되므로 데이터 삽입과 삭제는 적을 때 사용하게 된다. key와 value의 쌍을 원소로 저장하고, key는 중복될 수 없다. 조회시 키값을 인덱스로 이용하여 O(1), 탐색시 O(log N), 삽입과 삭제 또한 O(log n)

셋 : 해당 데이터가 존재하는가?

삽입과 동시에 정렬이 필요하고, 검색이 빨라야 할 때 사용하고 빠른 검색으로 key의 존재 여부를 신속하게 알고 싶을 때 사용한다. 셋은 BST로 구현되어 있어 검색은 O(log n), 삽입과 삭제는 O(log n) 이다.

해시테이블

Key Value로 데이터를 저장하는 자료구조로, 빠르게 데이터 검색에 최적화된 자료구조 탐색, 삽입, 삭제가 모두 O(1)만에 이루어진다! 내부적으로 배열(버킷)을 사용하여 데이터를 저장한다. 해시테이블은 각각의 Key값에 해시함수를 적용하여 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 해시값이 충돌하는 경우 해시 테이블을 확장하지 않고, 저장된 자료를 연결시켜 chaining을 구현할 수 있다. 하지만 데이터의 수가 많아지면 chaining이 많아져 캐시의 효율성이 떨어질 수 있다. unordered_map, unordered_set은 해시테이블로 구현되어 있다.

데이터 양이 많은 경우 map보다 unordered_map이 성능이 더 좋고, 그 이유는 map의 경우 위에서 살펴봤듯이 RBT인데, 키 값의 분포가 고르지 못하고 데이터가 많은 경우 balancing(트리 재배열)에 대한 비용이 계속해서 사용되므로 성능이 저하될 수 있다. 최악의 경우에도 O(log N)은 지켜지지만, unordered_map의 경우 해시테이블의 기반으로서 노드를 정렬할 필요가 없고 탐색의 시간복잡도는 O(1)이 소모되고, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수 있다. RBT는 자가 균형 이진탐색트리로써, 이진탐색트리가 한쪽으로 치우쳤을 때 검색 효율이 떨어지므로 균형을 바로 잡기 위하여 RBT를 주로 사용한다.

C# 딕셔너리

Key와 Value 쌍으로 이루어져 있다. C++의 map + hash table이라고 생각한다. 중복이 불가능하다. 내부 구현된 메소드가 많아 이용하기 편리하다. 인덱스를 이용하여 데이터를 찾을 순 없다. 딕셔너리는 검색과 추가, 삭제가 상수시간의 복잡도를 가지고 있고, 딕셔너리는 자료형을 명확히 설정하는 반면 해시테이블은 자료형에 대한 정의가 없어 속도면에서 딕셔너리가 좋은 성능을 보인다. ex) ContainsKey, OrderBy를 통해 정렬 등...

[ggjae]

집에 와 밥을 먹으면서 다시 생각해보았지만, 배열의 삽입 시 시간복잡도는 O(n)이라고 생각한다. 맨 뒤에 삽입할때나 O(1)이지...

[ggjae]

또한 리스트의 구현 코드 내 pEnd가 첫 시작 시 NULL이므로 첫 시작에는 예외처리가 필요하고, null 비교를 통해서 빼내주고 진행해야 함

[ggjae]

딕셔너리는 해시테이블로 구현되어 있고, 해시테이블은 배열로 구현되어 있다. C#에서는 딕셔너리는 체이닝방법으로 hash collision을 해결하지만, 해시테이블은 double hashing 방법을 사용해서 자리가 없다면 다른 해시함수를 사용해서 hash collision을 해결한다.