자료구조

개요

• 자료구조
• List
• LinkedList
• Stack
• Queue
• Dequeue
• Dictionary

자료구조

• 어떤 자료를 어떤 방식을 담고 어떤 방식으로 꺼낼지를 정하는 방법이며, 이 구조에 따라 장점과 단점이 명확하기 때문에, 활용하는 방식과 적용해야하는 지점에도 차이가 생깁니다.
• 간단하게 예로 들면 Queue는 선입선출 방식이며, Stack은 후입선출 방식입니다. 즉 2개가 상반된 구조를 갖고 있기 때문에 어떤 방식을 사용하냐에 따라서 설계해야하는 구조와 실용성이 달라집니다.
• 자료 구조에서는 읽기, 검색, 삭제, 삽입의 속도차이와 공간 복잡도, 시간 복잡도의 개념이 중요합니다.
  - 읽기 : 구조 내에 특정 위치에 접근을 말합니다.
  • 검색 : 구조 내에서 특정 데이터를 찾는 것을 말합니다.
  • 삭제 : 구조 내에서 특정 데이터를 제거하는 것을 말합니다.
  • 삽입 : 구조 내에서 자료를 넣는 것을 말합니다.
    - 공간 복잡도 : 프로그램이 점유하는 메모리의 용량을 말합니다. (다행이 현시 대에서의 대부분의 컴퓨터는 비교적 공간 복잡도에서 자유로운 편입니다.)
  • 시간 복잡도 : 프로그램이 특정 메소드나 함수를 완료하는 데까지의 걸리는 시간을 말합니다. 시간 복잡도는 Big-O 표기법을 기반으로 효율성을 판단합니다.
  • Big-O : 크기에 상관 없이 한번에 접근이 가능한 경우 $O(1)$과 같이 표기하며, 크기에 따라 여러번을 접근이 필요한 경우 $O(n)$을, 2차원 배열 같이 2배로 필요하 경우 $O(n^2)$, 3차원은 $O(n^3)$으로 표시하며, 정렬된 데이터를 찾을 때 절반 단위로 나누어서 접근하는 방식은 $O(logn)$으로 표시합니다.
• 자료 구조에서 위 사항이 중요한 이유는 언급하였듯 Queue와 Stack에서의 차이입니다. 예를 들어 카드를 게임을 하게되었을 때 카드 더미(덱)에서 카드를 갖여오는 방식에 따라 위 방식에서 차이가 날것입니다.
  뒤집어진 더미 위에서 갖고 온다는 상황이 발생 했을때 먼저 놓여진 카드는 맨 아래에 있고 가장 나중에 들어온 카드가 맨 밑에 있을 예정이니, 후입 선출의 개념이 됩니다. 즉 Queeue의 관점에서 봤을 때 삭제(해당 카드를 더미에서 갖고 왔기 때문에 더미 입장에서는 삭제됌)가 바로 일어났지만, 선입 선출 방식에서는 가장 뒤에 있는 카드에까지 접근 후 삭제해야 하기 때문에 카드 수가 늘어날 수록 오래걸리게됩니다.

List

• 배열 기반으로 초기화된 배열의 길이가 부족한 경우 현재 크기의 2배만큼 재할당됩니다.
• Generic을 사용하고 있습니다. (Generic Collection이라고 하며, .Net에서 미리 제공하는 System.Collections.Generic에 포함된 기능입니다.)
• 배열과 유사한 형태를 지니고 있으며, 사용자(프로그래머)의 편의에 맞춰진 형태입니다.
• 검색은 $O(n)$만큼 걸리며, 읽기는 $O(1)$만큼 걸립니다.
  - 검색은 모든 배열을 검색(52개의 배열 중에 52번째일지 5번째일지 모르는 상황이니 전체를 돌아야합니다.)하기 때문이며, 읽기는 Index를 사용하여 바로 접근이 가능하기 때문입니다.
• 삭제와 삽입의 경우에는 가장 뒤에 있는 값을 제거 할때는 $O(1)$이 걸리지만, 중간 부분이나 앞부분을 삭제 또는 삽입의 경우에는 뒤에 있는 모든 값들을 앞으로 밀어줘야하기 때문에 $O(n)$만큼 걸리게 됩니다.

void Main()
{
	// 초기화시 괄호 안에 숫자는 기본 크기입니다.
	List<int> mylist = new List<int>(6);
    
    List<int> mylist = new List<int>(6);
    mylist.Add(10);
    mylist.Add(9);
    mylist.Add(8);
    mylist.Add(7);
    mylist.Add(6);
    mylist.Add(5);
    foreach (int i in mylist)
    {
        Console.WriteLine(i);
    }

    Console.WriteLine("\n-----------\n");
    mylist.Add(4);
    mylist.Add(3);
    foreach (int i in mylist)
    {
        Console.WriteLine(i);
    }
}

10
9
8
7
6
5

-----------

10
9
8
7
6
5
4
3

• 위 사진들과 같이 공간이 부족할 시 재할당(기존 배열은 따로 참조가 없을 시 GC에서 처리될 예정)이 이루어졌습니다.

LinkedList

• linked는 여러가지의 방식을 갖고 있지만 그중 대표적인 방식으로는 단일 연결 리스트(Single Linked List), 이중 연결 리스트 (Doubly Linked List), 원형 연결 리스트 (Circle Linked List) 방식입니다.
  • 단일은 자신의 값과 자신 다음 값의 주소(마지막 값은 오직 자신만)만 알고 있는 방식입니다.
  • 이중은 자신의 값과 자신 다음 및 자신 전의 주소(첫번째는 자신과 다음, 마지막은 자신과 전)를 알고 있는 방식입니다.
  • 원형은 첫번째와 마지막이 위의 방식(단일, 이중)에 따라 연결되는 방식입니다.
    • 단일을 기준으로 마지막 값은 첫번째 값의 주소를 알고 있는 방식입니다.
• C#은 위 3개중 이중 연결 리스트로 구현되어 있습니다.
  • 검색 : $O(n)$
  • 읽기 : $O(n)$(Index로 접근할 수 없어 모든 배열을 순회해야 하기 때문입니다.)
  • 삭제 : $O(1)$(삭제된 부분은 전과 다음의 주소값만을 바꿔주면 되기 때문에 모든 배열을 순회하지 않습니다.)
  • 삽입 : $O(1)$(삭제와 같은 이유로 다음과 전 주소 값만 바꿔주면 됩니다.)
• LinkedList는 Node를 이용하여 삽입 삭제를 할 수 있습니다.

void Main()
{
    LinkedList<int> mylist = new LinkedList<int>();
    // 노드의 위치를 지정합니다.
    LinkedListNode<int> mynode;
    // 첫번째 지점, 배열 기준 0번째에 삽입합니다. 
    mylist.AddFirst(1);
    // 가장 마지막 지점, 배열의 끝(5의 길이의 배열에 경우 4)에 삽입합니다.
    mylist.AddLast(2);
    mynode = mylist.AddLast(3);
    mylist.AddLast(4);
    mylist.AddLast(5);
    // node가 마지막으로 지정된 위치를 기준으로 뒤로 99를 입력
    mylist.AddAfter(mynode, 99);
    // node가 마지막으로 지정된 위치를 기준으로 앞으로 77을 입력
    mylist.AddBefore(mynode, 77);

    foreach (int i in mylist)
    {
        Console.Write($"{i} ");
    }
}

1 2 77 3 99 4 5

Stack

• stack 또한 배열 기반에 공간 부족시 재할당 됩니다.
• LinkedList와 같이 index로 접근할 수 없지만 다른 메서드를 사용합니다.
  • 검색 : $O(n)$
  • 읽기 : $O(n)$(Index로 접근할 수 없어 모든 배열을 순회해야 하기 때문입니다.)
  • 삭제 : $O(1)$(후입선출 개념을 갖고 있고, 값을 꺼내는 동시에 삭제됩니다.)
  • 삽입 : $O(1)$(가장 뒤부분에서만 삽입합니다.)

void Main()
{
	Stack<int> mystack = new Stack<int>();
    mystack.Push(1);
    mystack.Push(2);
    mystack.Push(3);
    mystack.Push(4);
    Console.WriteLine(mystack.Pop());
    Console.WriteLine(mystack.Pop());
    // Peek를 통해 삭제하지 않고 보기만 할 수 있습니다.
    Console.WriteLine(mystack.Peek());
    Console.WriteLine(mystack.Pop());
    Console.WriteLine(mystack.Pop());
}

4
3
2
2
1

Queue

• 배열기반으로 공간 부족시 재할당 됩니다.
• Stack과 반대로 선입선출입니다.
  • 검색 : $O(n)$
  • 읽기 : $O(n)$(Index로 접근할 수 없어 모든 배열을 순회해야 하기 때문입니다.)
  • 삭제 : $O(1)$(선입선출 개념을 갖고 있고, 값을 꺼내는 동시에 삭제됩니다.)
  • 삽입 : $O(1)$(가장 뒤부분에서만 삽입합니다.)
• stack과 비슷하지만 선출 방식의 차입니다.

void Main()
{
    Queue<int> myqueue = new Queue<int>();
    myqueue.Enqueue(1);
    myqueue.Enqueue(2);
    myqueue.Enqueue(3);
    Console.WriteLine(myqueue.Dequeue());
    Console.WriteLine(myqueue.Dequeue());
    //같은 방식으로 peek을 이용해 보기만할 수 있습니다.
    Console.WriteLine(myqueue.Peek());
    Console.WriteLine(myqueue.Dequeue());
}

1
2
3

Dequeue

• C#에서는 구현되어 있지 않는 방식이기 때문에 이론만 설명합니다.
• Stack와 Queue의 장점을 합친 방식입니다.
• 구현 방식에 따라 입력 방향 제한, 출력 방향 제한할 수 있습니다.
• 필요에 따라 선입선출, 선입후출, 후입선출, 후입후출을 선택할 수 있습니다.

Dictionary

• Key와 Value 값으로 이루어져 있습니다.
• 위 방식들과는 다르게 Hash Funtion을 통해 Key값을 특정 값으로 치환하여, 검색 속도가 매우 높습니다.
  • Hash는 여러 곳에서 사용(특히 보안과 관련된 곳)되며, Dicionary와 같은 곳에서는 검색 속도등을 빠르게 진행 할 수 있습니다.
  • Hashing된 값은 매우 낮은 양의 값을 갖습니다.
• Dictionary는 사전이라는 의미를 갖으며, 실제 사전과 비슷한 방식으로 작동합니다.
  • 검색 : $O(1)$(1에 가까운 속도로 접근하기 때문에 1로 표기하겠습니다.)
  • 읽기 : $O(n)$(찾는 속도가 빠르지만 모든 배열을 돌아야하기 때문에 n의 속도를 갖습니다.)
  • 삭제 : $O(1)$
  • 삽입 : $O(1)$
• Dictionary의 방식은
• Hash 값으로 전환되다보면 매우 낮은 확률로 Hash 값이 겹쳐지는 상황 등이 발생하게 된다면(방식에 차이가 있지만 .Net C#을 기준으로), Dictionary 내부에 같은 Hash 값을 갖는 Key 바로 아래를 검사 후 빈공간이면 새로 생성되면서, 해당 공간에 할당 됩니다.

Dictionary<string, string> spell = new Dictionary<string, string>();

spell.Add("점화", "지정한 대상을 불태웁니다.");
spell.Add("회복", "가장 가까운 아군 또는 지정한 아군을 회복하면서 이동속도를 증가 시킵니다.");
spell.Add("강타", "지정한 대상을  고정피해로 피해 입힙니다.");

Console.WriteLine(spell["점화"]);
Console.WriteLine(spell["회복"]);
Console.WriteLine(spell["강타"]);
spell["강타"] = "지정한 대상을 고정피해로 피해 입히고, 느려지게 만듭니다.";
Console.WriteLine(spell["강타"]);

지정한 대상을 불태웁니다.
가장 가까운 아군 또는 지정한 아군을 회복하면서 이동속도를 증가 시킵니다.
지정한 대상을 고정피해로 피해 입힙니다.
지정한 대상을 고정피해로 피해 입히고, 느려지게 만듭니다.