[7~8/14 Sprint] 데이터의 구조 - 알고리즘

Data Structure

■ Array & LinkedList

Static-Array: 고정된 데이터 공간에, 순차적으로 데이터 저장<사이즈 예측 가능시> (메모리 낭비/오버헤드 발생 가능)

접근/추가/마지막 원소 삭제: O(1), 검색/삽입/삭제: O(n)

예시) 주식차트

 

*Array Size가 부족할 경우?

큰 사이즈의 새로운 Array에 옮김(Dynamic Array > Vector)

=> Doubling(Resize 방법): amortized O(n) - 계속 O(1)로 Append 되다가, 옮길 때 한번 O(n)

 

LinkedList: 구조체[데이터/다음노드주소-포인터] (물리적X/논리적 메모리-연속성) & 데이터 추가 시점에 메모리 효율적 할당

접근/검색: O(n), 삽입/삭제: O(1)

 

1) LinkedList vs DynamicArray?

- 데이터[Index] 접근/할당 빠름 O(1)? 배열 첫 주소값+Offset(산술적 연산 가능=Random Access) & 맨 뒤 삽입/삭제 O(1)

- Resize시, 낮은 performance(시간) & 불필요한 메모리 공간 & 삽입/삭제 시 O(n)

2) Array vs LinkedList?

시간 복잡도/메모리 효율적 사용(&구조상 저장방식 차이)

- Array(Stack): 조회/반복문 빈번 & 데이터량 예측+메모리 절약

- LinkedList(Heap): 조회보다 삽입/삭제 빈번+데이터량 예측 불가

 

■ Queue(FIFO): 자원 공유 프린터, CPU task scheduling, Cache구현, 너비우선탐색(BFS)

Enqueue & Dequeue O(1)

Array-Based(Circular Queue-Dynamic Array 방식): 전반적 Performance 좋은 편(단, Resize시 Worst)

List-Based(Singly-Linked List): 메모리 Allocation 필요

 

■ Stack(LIFO): call stack, 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS)

Top에 Push & Pop O(1) / 재귀적 특성

 

- Stack 2개로 Queue 구현

#. Instack / Outstack

• Enqueue, O(n): Instack에 push()
• Dequeue: Outstack이 비어있을 때마다 Instack에서 전체 pop() - 순서 거꾸로(FIFO)로 만들어짐 => Dequeue

Worst case(Outstack 비어있을 때) -> Instack.pop() + Outstack.push() 일때는 O(n), 평균적으로 pop()만 수행시

=> amortized O(1)

- Queue 2개로 Stack 구현

#. Queue 1, Queue 2

• Push: Queue1에 enqueue 동일
• Pop: Queue1의 앞쪽에서 데이터를 한 개 남겨놓고 모두 빼서, Queue2에 삽입 & 남은 데이터 하나 추출(Stack의 LIFO 구현) * 같은 함수 동작을 위해, Queue1과 Queue2 Swap

■ Heap & Priority Queue

Heap(우선순위 큐를 위한 트리의 종류): 일반적인 Tree의 경우 LinkedList로 구현, But Heap의 경우 Array로 구현(Append 수월)

-구현 편의를 위해 Array[0]은 제외하고, n번째 노드는 

Push O(logN) & Pop O(logN): 아래에 삽입/위에서 삭제(맨 아래 노드를 루트로 옮기면서 교차: Swap) 후 아래/위로 비교하면서 자리 찾기

Min Heap(Root Node = 최솟값): 자식 노드는 같거나 큼

Max Heap(Root Node = 최댓값): 자식 노드는 같거나 작음

 

■ 그래프: 정점, 간선, 가중치(정점과 간선 사이에 드는 비용)

 

■ 트리: 깊이(레벨), 높이, 서브트리

• BST: 자식 노드의 개수가 2개 이하, 본인 노드보다 작으면 왼쪽/크면 오른쪽 서브트리 - 모든 서브트리에 재귀적으로 해당⇒ 한 쪽으로(선형적으로) 치우쳤을 때 O(n) → 자가균형 이진탐색트리 이용 O(logN): 2^h - 1 = n
• AVL Tree: 트리 일부를 왼쪽/오른쪽으로 회전하며 균형
• 레드-블랙 Tree: 추가 비트(레드/블랙) 저장

- 정 이진트리: 자식노드 = 0/2

- 완전 이진트리: 왼쪽부터 채움/마지막 노드 제외, 모두 채워진 구조

- 변질 이진트리: 자식노드 1개

- 포화 이진트리: 모든 노드 채워진 구조

- 균형 이진트리: 왼쪽/오른쪽 높이 차이 1 이하(레드-블랙 트리~map/set)

 

■ Hash-Table: 효율적인(빠른) 탐색을 위한 자료구조 [Swift에서는, Dictionary/Set]

Collison 발생 전, 시간복잡도는 효율적 But 공간복잡도 비효율적(미리 공간확보 필요)

key-value 쌍 데이터 입력, [해시함수 h (키값 k)] 위치(버킷)에 key-value 데이터 쌍 저장

 

*좋은 해시함수: 해시값 고르게 분포됨(겹치지 X), 연산 속도 ↑

*Direct-address Table(직접 주소화 테이블): key 값으로 k를 갖음 - index k(숫자로만)에 저장 = 불필요한 공간낭비

 

★ Hash-Table Collison 이란? 해시 값의 입력값 무한 (해시함수)→ 출력 값 한정적, 비둘기집 원리

1) Open Addressing - 미리 정한 규칙에 따라, 비어있는 해시 슬롯 검색 *메모리 낭비 X

• 선형/이차 조사법(규칙적 건너뛰기) - 특정 영역에 클러스터링 됨
• 중복(이중)해시(해시 함수 2개) - 해시값 계산용 1개, 탐사 이동폭용 1개

2) Seperate Chaining - 데이터 초과 시, LinkedList 노드 증가

기본 해시테이블 - 삽입/검색/삭제 평균 O(1) ⇒ 충돌 발생시, Append 제외하고 n개 만큼 오른쪽으로 검색/삭제 - O(n)

* worst case: LinkedList O(n) → BST(or Red-Black Tree/AVL) O(logN) 시간복잡도를 낮출 수 있음

 

# 빅-오 표기법

O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)

 

* 공간 복잡도: ex, 재귀적 함수 사용시, 자료형*크기 공간 계속적 사용

자료구조 시간복잡도 [평균/최악]

	접근/탐색	삽입/삭제
배열 [접근시, O(n)]	O(n)	O(n)
스택/큐	O(n)	O(1)
이중 연결 리스트	O(n)	O(1)
해시 테이블	[O(1) / O(n)]	[O(1) / O(n)]
이진 탐색 트리(BST)	[O(logn) / O(n)]	[O(logn) / O(n)]
AVL/레드-블랙 트리	O(logn)	O(logn)

---

Algorithm

정렬 시간복잡도

예시: 5 1 8 3 2	Best/Avg	Worst	Run-time/속도
버블 정렬: 5부터 2까지 인접 원소비교/교체 -> 처음 원소부터 반복	n^2	n^2	6
선택 정렬: 가장 작은 데이터 찾아 맨 앞으로 옮기고 -> 다음부터 동일	n^2	n^2	5
삽입 정렬: 첫 원소부터 새롭게 삽입, 위치(크기)에 맞게 하나씩 삽입	n/n^2	n^2	4
힙 정렬: 힙(트리)구조 생성 - 큰 데이터(루트)삭제 - 구조 재생성 반복	nlog2(N)	nlog2(N)	3
합병 정렬: 데이터 분할(5 1 / 8 3 2) - 정렬 - 합병 반복	nlog2(N)	nlog2(N)	2
퀵 정렬: 피봇 선택 - 데이터 분할 - 정렬 - 합병 반복	nlog2(N)	n^2	1

 

■ 허프만 코딩(허프만 트리-이진코드)

문자 빈도수 확률/통계 기반 압축

- 접두부 코드(겹치지 않는) / 최적 코드(인코딩 메시지 길이 짧은 코드)

 

■ 반복문 → 재귀 알고리즘(피보나치, 팩토리얼)

https://www.pngegg.com/ko/png-psaev

 

// Recursive
private static fibonacci(idx: Int) -> Int {
    if (idx <= 2){ // 1, 2
    	return 1
    }
	return fibonacci(idx - 1) + fibonacci(idx - 2)
}

// For-Loop
private static fibonacci(idx: Int) -> Int {
    var result: Int = 1
    var before: Int = 1
    var tmp: Int = 0
    
    var i:Int = idx - 1
    
    while (i > 1) {
        tmp = result
        result += before
        before = tmp
    	i -= 1
    }
    return result
}

// Recursive
private static factorial(num: Int) -> Int {
	if(num > 1) {
		return recursiveFactorial(num -1) * num
	}
	return 1
}

// For-Loop
private static factorial(num: Int) -> Int {
	var answer: Int = 1
	for i in 2...num {
		answer *= i
	}
	return answer
}

# Dynamic Programming 이란?

중복되는 부분 문제(Overlapping Subproblem) & 부분 문제 최적해 = 전체 문제 최적해, 최적구조(Optimal Substructure)에 사용

• Top-Down: 큰 문제를 작은 문제로 분할 & 해결 → 메모이제이션[계산 결과 저장] 사용(재귀-중복 계산 방지)
• Bottom-Up: 작은 문제부터 → 큰 문제를 해결(테이블에 결과 저장)

var memo = [0, 1, 2]

func fibo (_ num: Int) -> Int {

	if num < memo.count {
        return memo[num]
    }

    let result = fibo(num - 1) + fibo(num - 2)
    memo.append(result)

    return result
}

func fibonacci(n: Int) -> [Int] {
  if(n <= 1) {
  	return n
  }
  
  let table = [0, 1]
  
  for i in stride(from: 2, to: n, by: 1) {
    table[i] = table[i - 2] + table[i - 1];
  }
  
  return table[n];
}

 

Tabulation(메모리절약 & 속도↑) > Memoization(복잡한 문제 직관적 해결 가능)

---

# References

https://dev-coco.tistory.com/160 [슬기로운 개발생활:티스토리]

https://www.nossi.dev/cs