[자료구조]목차를 통한 간략 정리

사실 자료구조는 컴퓨터과학의 기초중 기초이기 때문에, 항상 기본적으로 숙지하고 있어야할 사항입니다.

 

따라서 기본적인 내용을 안다는 가정 하에, 머릿속에 '아 이러한 것이 있었지!'라는 느낌을 받을 수 있도록 정리했습니다.

---

Performance Analysis

• Big-O: 최악의 경우
• Big-Θ: 평균적인 경우
• Big-Ω: 최선의 경우

 

Space Complexity

알고리즘 상 차지하는 공간(보통 변수들의 크기)

 

Time Complexity

알고리즘이 돌아가는데 걸리는 시간(대충 loop 횟수)

 

 

Recursion Tree

Recursion을 Tree형태로 보기 쉽게 표현한 것

 

Ex)

= O(n^2)

 

 

 

 

Master Theorem

Recursion Tree 대신 식을 가지고 한 번에 Complexity 구하는 법

 

 

• Big-O가 아니라 Θ임!
• ε은 f(n)과의 비교값임 → f(n)보다 logba값이 작냐, 크냐를 비교하는 척도

 

 

 

Sorting

• Selection: unstable
• Bubble: stable
• Insertion: stable
• Shell: 뭘 쓰냐에 따라 다름
• Merge: stable
• Heap: unstable
• Quick: unstable
• Counting: 판단 불가능
• Radix: stable

 

Queue

• FIFO
• Circular Queue(Full과 Empty 구분을 위해 1자리 남기기)
• Deque(Double Ended)

 

Stack

• LIFO
• Infix - Postfix - Prefix

 

List

• ArrayList
• LinkedList(head 필요)
• Circular LinkedList(꼬리가 다시 첫번째 노드로)
• Head + Tail
• Double Linked List(Bi-directional)
• Dynamic Stack(Linked List로 Stack 만듬)
• Dynamic Queue

 

Heap

Priority Queue

• 큐의 원소들이 우선순위를 갖고 있어 높은것이 front로 오도록

 

Heap

• Complete binary tree
• Insertion: 끝에다가 원소 추가하여 부모랑 계속 비교
• Deletion: root 노드 지우고, 끝 노드와 바꾼 다음 자식들 중 더 큰 놈과 바꿈

 

Huffman Coding

• 데이터 전송 시 bit 길이를 압축하기 위한 기법(가변 길이 코드)
• 접두어 코드이다(한 코드가 다른 코드의 접두어에 해당되지 않음)
• Frequency를 기준으로 min-heap 사용
• 2개 빼면서 합하여 binary tree 만들고, 다시 넣음(root node 값 기준)
• 끝난 뒤, 왼쪽 자식은 1, 우측 자식은 0으로 bit 배정

 

Binary Tree

Tree

• 최소 높이: logN + 1

• 최대 높이: N

• Full Binary Tree: 노드가 높이만큼 다 차있음(2^k - 1개)

• Complete Binary Tree: 노드가 높이만큼 다 차있진 않지만 균형잡혀있음. 또한 왼쪽부터 차 있음.

 

Traversal

• Inorder - LCR
• Preorder - CLR
• Postorder - LRC
  • → 재귀 함수들로 표현

• Level order
  • → Queue로 표현

• Threaded
  • → leaf right child만 다음 inorder successor를 가짐

 

Search Tree

• 왼쪽은 작게, 오른쪽은 크게
• Deletion
  • leaf node의 경우: 그냥 지움
  • child node가 하나 있는 경우: child node로 대체
  • child node가 두개인 경우: Inorder predecessor, Inorder successor로 대체
• 보통 O(logN) 들지만 최악의 경우 O(N) 듬.

 

AVL Tree

• Balanced tree
• 왼쪽 자식 높이 만큼 -, 우측 자식 높이 만큼 +
• -1 ~ +1 사이면 balanced 됐다고 판단
• Insertion
  • RR(Right Right), LL(Left Left), RL, LR 등의 Rotation 기법 사용
• Balancing 돼있기 때문에 O(logN) 보장

 

Red-Black Tree

• Root는 항상 검은색
• 새로 추가되는 Node는 빨간색
• 빈 Node는 검은색으로 침
• 단, 빨간색 node가 연속 높이에 있으면 규칙 위배(조정해야함)
  • Uncle이 Red인 경우: (Parent + Uncle)과 GrandParent 색을 바꿈
  • Uncle이 Black인 경우 - 일직선 위배: Parent와 GrandParent 색 바꾸고 LL or RR
  • Uncle이 Black인 경우 - 꺾인 위배: 자신과 GrandParent 색 바꾸고 LR or RL

 

2-3 Tree(B-Tree의 종류)

• 부모가 2개, 자식이 3개인 Tree
• B-Tree의 일종으로, 2-3 Tree는 order가 3인 경우이다.

 

 

Graph

Graph

• Simple Graph: 싸이클이 있던 말던 상관 없음
• Weighted Graph: 가중치 있는 graph
• Directed Graph: edge에 방향성이 있는 graph
• Complete Graph: 모든 Node끼리 연결 돼있음
• Sub Graph: graph의 sub

• Adjacency Matrix: 인접 행렬. (V^2)
• Adjacency List: 인접 리스트. (V + E)
• Degree: 한 노드에 연결된 edge 수

 

Traversal

• DFS: Recursion으로 구현(또는 stack)
• BFS: Queue로 구현

 

Minimum Spanning Tree

• 간단하게 구현하면 O(V^3)
• Union-Find: Node가 서로 cycle을 이루는지 알아내는 알고리즘
• Prim's Algorithm: Dijkstra 최단거리 알고리즘과 비슷함. O(V^2) 또는 O(ElogV) → Matrix냐 List냐 차이
• Kruskal's Algorithm: Edge들로 정렬해서 사용. O(ElogE)

 

Directed Acyclic Graph(DAG)

• 방향성 있는 graph이며, cycle이 존재하지 않는다.
• Topology Sort: indegree 값을 통해 Node 순서를 정렬하는 방법(답 여러개 존재 가능). O(V + E)

 

Shortest Path

• 간단하게 구현하면 O(V^3)
• Dijkstra's Algorithm: O(V^2) 또는 O(ElogV)
• Floyd-Warshall: O(V^3)
• Bellman-Ford: O(VE) - (V - 1)번만 탐색한다

 

 

Hash

Hashing

• Key: Value 형태
• O(1)
• 최악의 경우 O(N) - Chain 타고 들어가서

 

Hash Function

• Hash key가 겹치는 것을 방지
• Mid-square, Division, Folding etc....
• Probing: 다음 자리를 탐색해서 들어감
• Chaining: Linked List로 계속 Node가 추가