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 |
■ 허프만 코딩(허프만 트리-이진코드)
문자 빈도수 확률/통계 기반 압축
- 접두부 코드(겹치지 않는) / 최적 코드(인코딩 메시지 길이 짧은 코드)
■ 반복문 → 재귀 알고리즘(피보나치, 팩토리얼)
// 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 [슬기로운 개발생활:티스토리]
'☺︎ Daily-Life > Full-time Job Interviews' 카테고리의 다른 글
[3~4/14 Sprint] 운영체제 (1) | 2024.10.23 |
---|---|
[1~2/14 Sprint] 데이터베이스 (3) | 2024.10.21 |
The Hiring Process (1) | 2024.04.27 |