Category Archives: NOTE

자료구조

알고리즘 복잡도

속도 –  시간 복잡도Time Complexity
메모리 – 공간 복잡도Space Complexity

복잡도의 기준은 비교연산의 횟수 or 반복문 횟수

worst case 기준으로 복잡도 측정

빅-오 표기법( Big-Oh notation)

좋은 알고리즘

O(1) 상수형 빅-오

y=1

O(log n) 로그형 빅-오

O(n) 선형 빅-오

O(nlong n)

보통

O(n^2)

거의사용불가

O(n^3)

O(2^n)

 

재귀 알고리즘 예제

  1. 입력값 n을 넣으면 n~0까지 출력
  2. Fibonacci – 입력값 n을 넣으면 n번째 값 출력 0 1 1 2 3 5 8 …
  3. Factorial – 입력값 n을 넣으면 n! 값 출력 5! = 5*4*3*2*1
  4. BinarySearch
  5. 하노이 타워

 

종류

선형구조Linear

List
Stack
Queue

비선형구조

Tree
Graph

파일구조

순차파일
색인파일
직접파일

단순구조

정수
실수
문자
문자열

 

Stack – LIFO(Last In, First Out)

 

Queue – FIFO(First In, First Out)

뱀그림 대가리 입력 꼬리 출력

Deque

아무리봐도 디큔데 덱이라고 읽음
양방향 입출력 큐

Tree

계층적 관계, Hierarchical Relationship을 표현하는 자료구조

Decision Tree, 조직도

 

Full Binary Tree 왕세모
Complete Binary Tree 작은세모집합

Traversal

1

2       3

전위 순회Preorder Traversal (2 1 3)
중위 순회Inorder Traversal (2 3 1)
후위 순회Postorder traversal (1 2 3)

 

예제) 계산기

전위 표기법prefix notation
중위 표기법infix notation
후위 표기법postfix notation

 

BubbleSort

Selection Sort

Insertion Sort

Heap Sort

Merge Sort

Quick Sort