수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초

<aside> 📌 <자료구조>

0. Time Complexity

1. Stack

   1. Stack 구현 코드

2. Queue

   1. Circular_Queue 구현 코드

3. List

   1. liked list

      linked list 구현 코드

   2. double liked list

      Double Linkedlist 구현 코드

4. Tree

   1. tree

   2. binary Tree

   3. Binary Search Tree

   4. Tree Traversal

      Traversal 구현 코드

5. Graph

   1. graph
   2. spanning tree
   3. Search

6. Sorting

   1. Insertion sort

      Insertion sorting 구현 코드

   2. Heap sort

      Heap sorting 구현 코드

   3. Quick sort

      Quick sorting 구현 코드

   4. Merge sort

      Merge sorting 구현 코드

7. Hashing

   1. Symbol Table Abstract Data Type
   2. Static Hashing
   3. Dynamic Hashing

</aside>

<aside> 📌 <알고리즘>

</aside>

Time Complexity (시간 복잡도)

: 입력 값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리나?

시간 복잡도의 세 가지 표기법

• Big-Ω (빅-오메가) : 최상의 경우를 고려하는 표기법이다.

• Big-ɵ (빅-세타) : 평균적인 경우를 고려하는 표기법이다.

• Big-O (빅-오) : 최악의 경우를 고려하는 표기법이다. (주로 사용)

  • O(1) - Constant Complexity
  • O(logn) - Constant Complexity
  • O(n) - Linear Complexity
  • O(n^2) - Quadratic Complexity
  • O(2^n) - Exponential Complexity

  

Stack

: 가장 최근에 들어온 데이터가 가장 먼저 나가는 자료구조 → “후입선출 (LIFO: Last-In First-Out)”

• 출력 순서가 입력 순서의 역순으로 이루어질 때 유용
• 스택의 연산
  • top() : 맨 위에 있는 데이터 반환
  • push() : 데이터 삽입
  • pop() : 데이터 반환 후 삭제
  • isEmpty() : 원소가 없으면 'True', 있으면 'False' 반환
  • isFull() : 원소가 없으면 'True', 있으면 'False' 반환
• top: 가장 최근에 입력된 요소를 가리키는 변수로 자주 쓰인다
  • 데이터의 위치를 기록해놔야 하기 때문
  • 스택이 비어있으면 top = -1

https://roi-data.com/entry/자료구조-4-스택Stack이란-연산-구현방법

Stack 구현 코드

Queue

: 가장 먼저 들어온 데이터가 가장 먼저 나가는 자료구조 → “선입선출 (FIFO: First-In First-Out)”

• 큐의 연산
  • peek() : 맨 앞에 있는 데이터 반환
  • enQueue() : 데이터 삽입
  • deQueue() : 데이터 반환 후 삭제
  • isEmpty() : 원소가 없으면 'True', 있으면 'False' 반환
  • isFull() : 원소가 없으면 'True', 있으면 'False' 반환