[C#] Data Structure

자료구조

---

프로그래밍을 공부하면서 간단한 콘솔 프로젝트를 경험해봤다면 데이터 집단을 어떻게 관리해야할지 고민을 해봤을 것이다. 상황에 따라 더 빠르고 효율적인 자료구조를 선택하는 것 또한 프로그래머의 필수 기초 역량이기에, 자주 사용되는 자료구조를 배우고 적절하게 사용해보자.

데이터 저장 기법

컴퓨터의 메모리에 존재하는 데이터를 어떻게 배치,사용하느냐에 따라 큰 성능차이가 나게 되는데, 이렇게 데이터를 배치하는 것을 자료구조라고 하며 형태에 따라서 2가지로 나눌 수 있다.

• 선형 구조 : 자료 간의 관계가 1대1 구조 / 배열, 스택, 큐, 스택 ...

• 비선형 구조 : 자료 간의 관계가 1대n n대n인 구조 / 트리, 그래프 ...

알고리즘 성능

효율적으로 코드를 구성하기 위해서는 성능을 측정하는, 판단하는 기준이 존재하여 비교가 가능해야하며, 이 경우 2가지로 성능을 판단하게 된다.

• 공간 복잡도 : 알고리즘의 공간적 자원 소모량

• 시간 복잡도 : 알고리즘의 시간적 자원 소모량

• Big-O 표기법 : 알고리즘의 시간 복잡도를 나타내는 점근표기법

  데이터 증가량에 따른 시간 증가량을 계산하고, 가장 높은 차수를 표기한다.

static void Main(string[] args)
{
    int Case1(int n)
    {
        int sum = 0;
        sum = n * n;
        return sum;
    }

    int Case2(int n)
    {
        int sum = 0;
        for(int i = 0; i<n; i++)
        {
            sum += n;
        }
        return sum;
    }

    int Case3(int n)
    {
        int sum = 0;
        for(int i = 0; i<n; i++)
        {
            for(int j =0; j<n; j++)
            {
                sum++;
            }
        }
        return sum;
    }

    /* 입력값  Case1   Case2   Case3
     * 1        1       1       1
     * 10       1       10      100
     * 100      1       100     10,000
     * 1,000    1       1,000   10,000,000
     * n        1       n       n^2
     * Big-O    O(1)    O(n)    O(n^2)  */

알고리즘의 성능을 만약 수행 시간으로 분석한다면, 개개인의 컴퓨터 성능에 따라 다른 결과가 나올 것이다. 따라서 수행 시간을 분석하는 경우 Big-O 표기법과 함께 수행시간을 평균 상황, 최악의 상황을 기준으로 평가한다.

List

---

매번 자료를 저장하기 위해 자료구조를 만드는 것은 굉장히 피곤한 작업이 될 것이다. 따라서 이를 지원하기 위해 C#에서는 Generic Collection으로써 효율적이고 다양한 자료구조들을 지원하고 있으며, 그 중 대표적인 예시인 List에 대해 알아보자.

List의 크기

List는 배열 기반의 자료구조로 배열은 크기를 바꿀 수 없지만, List는 크기 변동이 가능하다는 점에서 큰 차이를 갖는다.

List<int> list = new(10);  

for(int i =0; i<20; i++)
{
    list.Add(i);
    Console.WriteLine($"Count : {list.Count}, Capacity : {list.Capacity}");
}

위 코드를 실행하면 List의 크기가 바뀌는 원리에 대해 알 수 있다. List는 가지고 있는 크기보다 더 많은 데이터를 저장하고자 하면, 기존 크기의 2배에 해당하는 배열을 새롭게 생성하고, 기존 배열의 데이터를 생성한 배열로 복사한 뒤 데이터를 추가하는 알고리즘을 가지고 있다. 따라서 데이터를 추가하는

List의 사용

List<int> list = new List<int>() : 인스턴스 생성
list.Add() : 맨 뒤에 추가하기. O(1)
list.Insert(,) : 원하는 index에 추가하기, 이후 인덱스 뒤로 밀림. O(n)
list.Remove() : 해당 요소 제거(중복될 경우 맨 앞), 이후 인덱스 앞으로 당겨
list.RemoveAt() : 해당 index 제거, 이후 인덱스 앞으로 당겨짐 O(n)
list[1] = 1000 : 리스트는 인덱스를 통한 접근이 가능. O(n)
int value = list[1]

int index = list.IndexOf() : 해당 요소의 인덱스 값을 반환. 없는 경우 -1 반환. O(n)
bool contain = list.Contains() : 해당 요소가 있으면 true, 없으면 false.

int count = list.Count : 리스트가 소유중인 요소의 수
int capacity = list.Capacity : 리스트의 용량

List 성능

리스트의 시간 복잡도는 다음과 같다. 접근 : O(1) / 탐색,삽입,삭제 : O(n)
즉 접근에 굉장히 좋은 자료구조이지만 탐색, 삽입, 삭제에서 좋은 평가를 받을 수는 없다. 하지만 List는 배열 기반으로 만들어져있어 cache memory 적중률이 좋다는 장점이 있고 정말 많이 사용되는 자료구조이므로 쓰임을 잘 알아두어야 한다.

Linked List (연결 리스트)

---

List가 탐색, 삽입, 삭제에서 비교적 시간 복잡도가 높기 때문에 데이터의 추가 및 제거가 빈번한 상황에서는 장점을 발휘하기 힘들다. 따라서 이러한 상황에서 장점을 갖는 Linked list를 알아둘 필요가 있다.

Linked list

데이터와 다른 데이터 지점의 참조 변수를 가진 노드를 기본 단위로 사용하며 이러한 노드들을 연결식으로 만든 자료구조이다. Linked list는 데이터를 노드로 연결식으로 구성하고 있기에 데이터의 추가와 삭제에 장점을 가진다.

연결리스트의 종류

• 단방향 연결리스트 : 노드가 다음 노드를 참조
• 양방향 연결리스트 : 노드가 이전/다음 노드를 참조
• 원형 연결리스트 : 시작 노드와 마지막 노드가 서로를 참조

연결리스트의 특징

데이터를 연속적으로 배치하는 배열과 달리 연결식으로 구성되며, 데이터 추가/삭제 과정이 다른 데이터의 위치와 무관하게 진행되기 때문에 빠르다는 장점이 있다. 하지만 데이터 접근 과정에서 연속적인 데이터 배치가 아니기에 인덱스 사용이 불가능하여 처음부터 탐색해야하기 때문에 시간이 걸린다는 단점을 가진다.

연결리스트의 사용

static void Main(string[] args)
{
    // 생성
    LinkedList<int> linkedList = new();

    // 추가
    LinkedListNode<int> node0 = linkedList.AddFirst(0);
    LinkedListNode<int> node1 = linkedList.AddLast(1);
    LinkedListNode<int> node2 = linkedList.AddBefore(node1,2);
    LinkedListNode<int> node3 = linkedList.AddAfter(node1,3);

    // 제거
    linkedList.Remove(node1);   // O(1)
    linkedList.RemoveFirst();   // O(1)
    linkedList.RemoveLast();    // O(1)
    linkedList.Remove(3);       // O(n) : 탐색 후 제거

    // 접근
    LinkedListNode<int> prevNode = node1.Previous;
    LinkedListNode<int> nextNode = node1.Next;
    LinkedListNode<int> firstNode = linkedList.First;
    LinkedListNode<int> LastNode = linkedList.Last;

    // 탐색
    LinkedListNode<int> findNode = linkedList.Find(2);
    bool contain = linkedList.Contains(3);  // 못찾으면 null 반환
}

Stack

---

후입선출(LIFO) 방식의 자료구조로 가장 최근에 입력된 순서로 데이터를 처리해야하는 상황에 활용되며, 대표적인 예시로 UI, DFS, Undo 등이 있다. 구현 자체는 List를 통해 쉽게 가능하며, 성능때문보다 맞는 상황에 사용함으로써 갖는 이점이 크기 때문에 많이 활용한다.

Stack의 사용

static void Main(string[] args)
{
    Stack<int> stack = new();
                                  

    stack.Push(1);   // 추가 : O(1) / 최악 : O(n)
    stack.Push(2);
    stack.Push(3);
    stack.Push(4);

    stack.Pop();     // 최근에 추가한 데이터 확인 및 제거
    stack.Peek();	 // 최근에 추가한 데이터 확인
    
    stack.TryPop(out int pop);     // Pop이 가능하면 수행
	stack.TryPeek(out int peek);   // Peek이 가능하면 수행 
}

Queue

---

서비스를 제공 받고자 할 때 줄을 서서 순차적으로 기다렸을 것이다. 이렇게 가장 먼저 추가된 데이터를 반환하는 FIFO 형태의 선형 자료구조를 Queue라고 한다. Queue의 경우 linked list로 쉽게 구현이 가능하지만, 배열이 더 빠르기 때문에 배열로 head, tail 시스템으로 구현한다.

Queue의 원리

• head : Dequeue 될 인덱스 / tail : Enqueue 될 인덱스
• head와 tail이 같으면 비어있는 것으로 간주
• Enqueue가 될때마다 tail이 다음 인덱스로 이동
• tail이 배열의 범위를 벗어나는 경우 배열의 맨 처음으로 이동
• head 바로 왼쪽에 tail이 있는 경우 크기를 2배 늘리고 복사

Queue의 사용

static void Main(string[] args)
{
    Queue<int> queue = new();

    // 추가 : O(1) 최악 : O(n)
    queue.Enqueue(1);
    queue.Enqueue(2);
    queue.Enqueue(3);
    queue.Enqueue(4);

    // 꺼내기 : O(1)
    Console.WriteLine(queue.Dequeue());
    Console.WriteLine(queue.Dequeue());
    Console.WriteLine(queue.Dequeue());
    Console.WriteLine(queue.Dequeue());
}