[CS스터디 #01] 자료구조(Array, LinkedList, Tree, Hash)

 

💻 자료구조: Data Structure

 

 

 

◻️ Array

   가장 기본적인 자료구조로, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 그렇기 때문에 인덱스(index)로 빠르게 접근할 수 있어 search의 경우 O(1)의 빠른 속도를 보여준다. 

   다만 삽입/삭제의 경우 배열의 연속적인 특징이 깨지기 때문에 나머지 원소들을 shift 해주는 O(n)의 비용이 발생하게 된다. 

 

 

◻️ Linked List

   논리적 저장 순서와 물리적 저장 순서가 일치하지 않는 자료구조이다. 각각의 원소는 다음 원소가 무엇인지만을 알고 있기 때문에 삽입/삭제의 비용은 O(1)로 매우 간단하다.

   다만, 연속적이지 않은 특성 때문에 특정 원소에 접근할 경우 해당 원소를 찾기 위해 모든 원소를 들여다 봐야하는 비용이 O(n)으로 발생한다. 따라서 삽입/삭제의 경우에도 작업할 원소를 찾기 위해 비용이 발생하므로 서치/삽입/삭제 모두 worst case로 O(n)의 시간이 소요된다고 볼 수 있다.

   Linked List는 Tree의 근간이 되는 자료구조로 유용하게 쓰인다.

 

 

 

 

 

💙 💙 💙

 

 

◻️ Stack

 가장 기본적인 자료구조 중 하나로, 후입선출(LIFO) 구조로 데이터를 저장한다. 보통 Array로 구현하는데, 이는 데이터를 제거할 필요없이 말단 index만 줄여가며 초기화가 가능하기 때문이다.

 

 

◻️ Queue

 가장 기본적인 자료구조 중 하나로, 선입선출(FIFO)구조로 데이터를 저장한다. 보통 앞단의 삽입/삭제가 용이하도록 연결리스트로 구현된다.

 * Priority Queue (우선순위 큐): 가장 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조로, 일반적으로 힙을 사용하여 구현된다.

 

 

◻️ Heap

 완전 이진트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조이다.

 최대힙, 최소힙이 있어 여러 개의 값들 중에서 최대값이나 최소값을 빠르게 찾아내도록 만들어졌다.

 힙을 저장하는 표준적인 자료구조는 배열이다. 삽입의 경우 가장 말단에 넣어서 바로 위 부모노드랑 비교해가며 힙을 정렬하고, 삭제의 경우 루트노드를 제거한 자리에 말단 노드를 가져온 다음 자식노드와 비교해가며 힙을 정렬한다.

 

 

 

 

 

💙 💙 💙

 

 

◻️ Tree

 트리는 배열, 스택, 큐와 같은 선형구조가 아닌 비선형 구조이다. 자료의 계층적 관계를 표현한다.

• Node(노드): 트리를 구성하고 있는 각각의 요소들을 의미한다.
• Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
• Root Node(루트 노드): 트리에서 최상위에 있는 노드를 의미한다.
• Terminal Node(=Leaf Node, 단말 노드): 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
• Internal Node(내부 노드, 비단말 노드): 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

 

◻️ Binary Tree 이진트리

   한 노드의 차수가 2를 넘지않는 트리를 의미한다. 

   노드의 개수가 n개이고 root가 0이 아닌 1에서 시작할 때, i번째 노드에 대해 다음과 같은 식이 만족된다.

   -parent(i) = i/2

   -left_child(i) = i*2

   -right_child(i) = i*2+1

• Perfect Binary Tree(포화 이진 트리): 모든 레벨이 꽉 찬 이진트리를 의미한다. 
• Complete Binary Tree(완전 이진 트리): 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진트리를 가르킨다.
• Full Binary Tree(정 이진 트리): 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진트리를 의미한다.

 

◻️ BST (Binary Search Tree, 이진탐색트리)

  이진트리에서 더 효율적인 탐색을 위해 생긴 구조이다. 데이터 저장에 규칙이 따른다.

• 이진 탐색 트리의 노드에 저장된 키는 유일하다.
• 부모의 키가 왼쪽 자식 노드의 키보다 크다.
• 부모의 키가 오른쪽 자식 노드의 키보다 작다.
• 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

   이진탐색트리는 탐색에 있어 O(logN) 정확히 말하자면 O(h)라고 표현할 수 있다. 

   주의할 점은 Skewed Tree(편향 트리)가 만들어질 수 있다는 점이다. 저장 순서에 따라 한 쪽으로만 계속해서 저장된다면 탐색의 Worst Case는 O(n)이 되어 이진탐색트리의 장점을 살리지 못하게 된다.

   이러한 비효율을 개선하기 위해 트리를 Rebalancing하는 기법들이 있는데, 그 중에서 대표적인 것이 바로 Red-Black Tree이다.

 

 

◻️ Binary Heap

   Tree 중에서도 배열에 기반한 Complete Binary Tree의 자료구조이다.

   최대힙(Max Heap)과 최소힙(Min Heap)이 있다. 최대힙의 경우 각 노드의 값이 childeren의 값보다 크거나 같은 완전 이진 트리를 뜻하며, 최소힙은 그 반대를 의미한다. 

   각자 최대값, 최소값을 찾는데에는 O(1)의 빠른 속도를 보이지만, 값을 삽입/삭제를 할 때에는 트리 구조를 재구성 해야하기 때문에 O(logN)의 시간복잡도를 보인다.

 

 

◻️ Red Black Tree

 BST를 기반으로 하는 트리 형식의 자료구조이다. 특정 노드의 개수에 대하여 depth를 최소화하여 시간복잡도를 줄이는 것이 핵심으로, Complete binary tree인 경우를 의미한다. 따라서 Search, Insert, Delete의 경우에 O(logN)의 일관적인 시간복잡도를 보인다.

 정의는 아래와 같다.

• 각 노드는 Red/Black의 색깔을 갖는다.
• Root node의 색깔은 Black이다.
• 각 Leaf node의 색깔은 Black이다.
• 어떤 노드의 색깔이 red라면, 두 개의 children의 색깔은 모두 Black이다.
• 각 노드에 대해서 노드로부터 descendant leaves까지의 단순 경로는 모두 같은 수의 black nodes들을 포함하고 있어야 한다. 이를 해당 노드의 Black-Height라고 한다.

삽입/삭제의 원리를 알아두는 것도 좋을 듯 하다.

 

 

 

 

 

💙 💙 💙

 

 

◻️ Hash Table

 Hashing은 특정한 계산을 통하여 나온 값을 키로 하여 값에 접근하는 과정이다. Hash Table과 Hash Function으로 구성된다.

 Hash Table은 Key와 Value를 갖는 자료구조이다. 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 즉, 특정 값을 검색하는데 있어 데이터 고유의 인덱스를 쓰므로 Time Complexity가 O(1)이 되는 것이다. 다만 인덱스로 사용되는 key값이 불규칙하므로 이를 다루는데 있어 특별한 알고리즘으로 이뤄진 Hash Function을 사용하게 된다.

   Hash Function이 리턴하는 값을 Hashcode라고 하는데, 이 키 값이 동일한 데이터가 존재하는 경우 Collision이 발생한다. Collision을 최소화하는 방향으로 설게된 것을 좋은 Hash Function이라고 한다.  이를 위한 방법으로는 아래와 같은 것들이 있다.

• Open Address 방식 (개방주소법)
  • 선형 탐색 (Linear Probing): 해시충돌 시 다음 버켓이나 몇 개의 위치를 건너뛰어 빈 곳에 데이터를 삽입하는 탐색법이다.
  • 제곱 탐색 (Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입하는 탐색법이다.
  • 이중 해시 (Double hashing probing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용한다. 해시연산을 두번 해야하기 때문에 성능적으로 좋지 않다. 
  • 개방주소법은 삭제의 경우 충돌에 의해 저장된 데이터가 검색되지 않을 수 있기 때문에 삭제위치에 다음위치까지 연결해주는 더미노드를 삽입해야한다. 더미노드가 많아지면 버킷을 연속적으로 검색해야하므로 일정 개수 이상이 되었을 경우 재해시를 해줘야 성능 유지가 가능하다.
  • 포인터가 필요없고 지정한 메모리 외 추가적인 저장공간이 필요하지 않다. 삽입/삭제시 오버헤드가 더 적어 데이터가 적을 때 더 유리하다.
• Chaining 방식 (체이닝)
  • 버켓에 연결리스트를 할당하여, 버켓에서 해시충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식이다.
  • 버켓이 꽉 차더라도 연결리스트로 늘려가기 때문에 데이터의 주소값이 변하지 않는다.
  • 개방주소법에 비해 복잡한 계산식이 필요하지 않으나, 해시테이블이 채워질수록 성능저하가 발생한다.
• 리사이징
  • 새로운 배열에 기존 배열의 키를 새롭게 재해싱하는 방법이다.
  • 개방주소법에서 고정크기의 배열이 꽉 차거나, 체이닝에서 연결리스트의 길이가 길어지게 되면 검색 효율이 떨어지기 때문에 버킷의 개수를 늘려주는 방법이다.

 

 

 

💙 💙 💙

 

 

◻️ Graph

 트리와 마찬가지로 비선형 자료구조이다. 트리는 사이클이 존재하지 않는 그래프이다.

 방향 그래프(Directed Graph)/ 방향이 없는 그래프(Undireted Graph)/ 가중치 그래프(Weight Graph)/ 비가중치 그래프/ 부분 그래프(Sub Graph)와 같은 종류가 있다.

 

 그래프를 구현하는 방법으로는 인접 행렬(Adjacent Matrix) 또는 인접 리스트(Adjacent List)를 사용하는 것이 있다.

• 인접 행렬(Adjacent Matrix): vertex 간의 연결관계를 O(1)로 파악할 수 있다. 단, Space Complexity가 O(V^2)이 발생하므로 Dense graph 표현에 적합하다.
• 인접 리스트(Adjacent List): vertex간의 연결관계를 확인하는데 오래 걸린다. Space Complexity는 O(V+E)로 Sparse Graph를 표현하는데 좋다.

 그래프를 탐색하는 방법으로는 다음과 같은 것들이 있다.

• 깊이 우선 탐색 (Depth First Search: DFS): Stack
• 너비 우선 탐색 (Breadth First Search: BFS): Queue

 

◻️ 최소신장트리 MST(Minimum Spanning Tree)

그래프 G에서 edge weight의 합이 최소인 Spanning Tree(그래프 G의 모든 vertex가 cycle없이 연결된 형태)를 의미한다. 

• Kruskal Algorithm
  • 모든 간선들을 오름차순으로 정렬한 다음, 최소 가중치를 보이는 간선부터 선택하며 스패닝 트리를 만들어가는 알고리즘이다. 간선 선택을 기반으로 한다.
• Prim Algorithm
  • 시작 정점을 기준으로 가장 가중치가 적은 간선으로 연결된 정점을 선택하며 신장 트리를 확장시키는 알고리즘이다. 정점 선택을 기반으로 한다.

 

 

 

 

 

💙 💙 💙

 

 

📝 CS 질문 정리

 

   1. 해시 테이블이란 무엇인가? 해시 테이블의 시간 복잡도는 어떻게 되는가?

   >> 해시 테이블은 (Key, Value)쌍으로 데이터를 저장하는 자료구조 중 하나이다. 내부적으로 배열을 사용하여 저장되기 때문에 데이터의 접근이 O(1)로 무척이나 빠르다. 그러나 index에 충돌이 발생하는 경우, 추가적인 조회를 위해 Time Complexity가 O(N)까지 증가할 수 있다. 

 

   2. ArrayList와 Linked List의 차이는 무엇인가.

   >> ArrayList는 데이터들이 순서대로 늘어선 배열의 형태를, Linked List는 자료의 주소값으로 서로 연결된 형식을 가지고 있다. 

• ArrayList: 원하는 데이터에 무작위로 접근할 수 있다. 리스트의 크기가 제한되어 있으며 이를 재조정하는 데에는 많은 연산이 필요하다. 또한 삽입/삭제의 경우 임시배열을 생성하여 복제하고 있기 때문에 시간이 오래 걸린다.
• LinkedList: 리스트의 크기에 영향없이 데이터를 추가할 수 있다. 삽입/삭제의 경우 인접 데이터의 링크만 변경하면 되므로 시간이 매우 빠르다. 단, 무작위 접근이 불가능하므로 데이터 조회시 순차접근을 해야하므로 여기에 시간이 걸린다.

 

   3. 큐와 스택의 구현에 좋은 자료구조는?

   >> 큐는 List, 스택은 Array

• 큐(Queue): Array 구현시 poll 연산 이후 객체를 앞당기는 작업이 필요하다. 하지만 List로 구현하면 객체 1개만 제거하면 되므로 삽입/삭제가 용이한 Linked List로 구현하는 것이 좋다.
• 스택(Stack): List로 구현하면 객체를 제거하는 작업이 필요하다. 하지만 Array로 구현하면 index만 줄이고 초기화하면 되므로 삭제 작업을 할 필요가 없어진다. 따라서 Array로 구현하는 것이 좋다. 

 

   4. 포화 이진트리, 완전 이진트리, 정 이진트리의 차이점에 대해 설명하시오.

 

   5. 힙의 자료구조에 대해 설명하시오.

 

   6. 그래프와 트리의 차이점은 무엇인가?

 

   7. 최소신장트리에 대해 설명하시오.

 

    8. 그래프를 탐색하는 방법으로 무엇이 있는지, 그리고 각각의 특성에 대해 설명하시오.

 

 

 

 

 

 

 

 

 

 

 

   

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨