자료구조

---

☑️ ArrayList vs LinkedList

✔️Array 는 어떤 자료구조 인가요?

data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기 저장(Stack)

• 고정된 저장 공간
• 순차적인 데이터 저장

↔ LinkedList 메모리에 저장되는 방식, 이에 따른 operation의 연산 속도(time complexity)

✔️Dynamic Array란 무엇인가요?

Array의 저장공간이 가득차면 resize하여 저장공간을 재조정한다.(Heap)

• resize 하는 방식 Doubling(2배 사이즈 resize)

데이터를 추가할 때 시간 복잡도

• resize할 때의 시간 복잡도 O(n) ➡️ 그렇담 결과적으로 append의 시간 복잡도는? amortized O(1) 추가 시, resize가 계속해서 일어나지 않는다.

Linked List와 비교했을 때, 장단점

• 데이터 접근과 할당이 O(1)로 굉장히 빠르다.
• Dynamic Array의 맨 뒤에 데이터를 추가하거나 삭제하는 것이 상대적으로 빠르다.
• Dynamic Array의 맨 끝이 아닌 곳에 data를 insert/remove 할 때, 느린 편이다. 연속적으로 데이터가 저장되어있어서 모두 한칸 씩 shift 해야함
• 필요한 것 이상의 memory 공간을 할당 받는다.

✔️Linked List란 무엇인가요?

Node는 데이터 값과 next Node의 address를 저장

논리적인 연속성을 가진 자료구조

• 메모리 에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유롭습니다.
• Next address를 추가적으로 저장해야 하기 때문에, 데이터 하나당 차지하는 메모리가 더 커지게 됩니다.

데이터가 추가되는 시점에 메모리를 할당

---

☑️ Queue vs Stack

✔️Queue는 무슨 자료구조 인가요?

Queue는 선입선출 FIFO의 자료구조 시간 복잡도는 O(1)

ex) Cache, 프로세스, BFS

✔️Stack 무슨 자료구조 인가요?

LIFO

✔️Stack 2개로 Queue 구현하기

➡️ enqueue를 구현하는 stack1에 모든 data를 push(), 모든 data를 비어있는 stack2에 pop() → dequeue를 구현하는 stack2에 다시 push(), 그 후 pop()

✔️Queue 2개로 Stack 구현하기

✔️Queue vs Priority Queue

Queue는 O(1), PriorityQueue는 O(logN) → 완전이진트리

Heap은 완전이진트리 구조입니다.

• max heap인 경우 각 node 값 ≥ child node 값
• min heap인 경우 각 node 값 ≤ child node 값

☑️ Hash table vs BST

✔️BST는 어떤 자료구조 인가요?

이진탐색트리는 정렬된 트리, 모든 child nodes의 개수가 2개 이하

저장과 동시에 정렬을 하는 자료 구조

• 이진탐색트리의 조건

1. 왼쪽서브트리 ≤ 현재 노드 ≤ 오른쪽 서브트리
2. 모든 서브트리들도 1번 조건을 만족한다.

• 삽입/삭제 시간복잡도 O(logN) / O(N)
• worst case → O(N) 균형이 많이 깨져서 한 쪽으로 치우친 BST의 경우 (≒Linked List)
• worst case가 발생하지 않게 하기 위한 방법 자가 균형 이진 탐색 트리(Self-Balancing BST) ➡️ 최대한 이진 트리의 균형이 잘 맞도록 유지하여 높이를 가능한 낮게 유지 ex) AVL tree, Red-black tree, Java의 hashmap의 seperate chaining

✔️Hash table는 어떤 자료구조 인가요?

직접 주소화 방법은 불필요한 공간이 낭비되고, key가 다양한 자료형을 담을 수 없게 됩니다.

hash function h를 이용해서 (key, value)를 index:h(k)에 저장합니다. 이 때, 키 k값을 갖는 원소가 위치 h(k)에 hash된다. 또는 h(k)는 키 K의 해시값이다. 중복되는 key가 있어서는 안된다.

문제점 → Collision: 서로 다른 key의 해시 값이 똑같을 때

해결 방법 → separate chaining, open addressing

✔️좋은 hash function의 조건은 무엇인가요?

상황마다 좋은 hash function은 달라질 수 있으나 대략적인 기준은 연산 속도가 빨라야 하고, 해시값이 최대한 겹치지 않아야 합니다.

✔️⭐️⭐️⭐️Hashtable에서 collision 발생 시, 해결방안

• separate chaining (worst case 시간 복잡도 설명)

Linked list를 이용하여 collision을 해결합니다. 충돌이 발생하면 해당 주소를 가진 linked list에 노드를 추가해줍니다.

worst case의 경우 n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 linked list가 생성되게 됩니다. 이 때, 검색의 시간복잡도가 O(n)이 됩니다.

• open addressing(선형 조사법, 중복해시)

collision 발생 시, 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾습니다. 추가적인 메모리를 사용하지 않으므로 메모리를 적게 사용합니다. 중복 해시 - 클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용, 하나는 최초의 해시값을 얻을 때 사용하고 또 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용

---

☑️ ArrayList vs LinkedList

✔️Array 는 어떤 자료구조 인가요?

data를 메모리상에 연속적이며 순차적으로 미리 할당된 크기 저장(Stack)

• 고정된 저장 공간
• 순차적인 데이터 저장

↔ LinkedList 메모리에 저장되는 방식, 이에 따른 operation의 연산 속도(time complexity)

✔️Dynamic Array란 무엇인가요?

Array의 저장공간이 가득차면 resize하여 저장공간을 재조정한다.(Heap)

• resize 하는 방식 Doubling(2배 사이즈 resize)

데이터를 추가할 때 시간 복잡도

• resize할 때의 시간 복잡도 O(n) ➡️ 그렇담 결과적으로 append의 시간 복잡도는? amortized O(1) 추가 시, resize가 계속해서 일어나지 않는다.

Linked List와 비교했을 때, 장단점

• 데이터 접근과 할당이 O(1)로 굉장히 빠르다.
• Dynamic Array의 맨 뒤에 데이터를 추가하거나 삭제하는 것이 상대적으로 빠르다.
• Dynamic Array의 맨 끝이 아닌 곳에 data를 insert/remove 할 때, 느린 편이다. 연속적으로 데이터가 저장되어있어서 모두 한칸 씩 shift 해야함
• 필요한 것 이상의 memory 공간을 할당 받는다.

✔️Linked List란 무엇인가요?

Node는 데이터 값과 next Node의 address를 저장

논리적인 연속성을 가진 자료구조

• 메모리 에서 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 좀 더 자유롭습니다.
• Next address를 추가적으로 저장해야 하기 때문에, 데이터 하나당 차지하는 메모리가 더 커지게 됩니다.

데이터가 추가되는 시점에 메모리를 할당

---

☑️ Queue vs Stack

✔️Queue는 무슨 자료구조 인가요?

Queue는 선입선출 FIFO의 자료구조 시간 복잡도는 O(1)

ex) Cache, 프로세스, BFS

✔️Stack 무슨 자료구조 인가요?

LIFO

✔️Stack 2개로 Queue 구현하기

➡️ enqueue를 구현하는 stack1에 모든 data를 push(), 모든 data를 비어있는 stack2에 pop() → dequeue를 구현하는 stack2에 다시 push(), 그 후 pop()

✔️Queue 2개로 Stack 구현하기

✔️Queue vs Priority Queue

Queue는 O(1), PriorityQueue는 O(logN) → 완전이진트리

Heap은 완전이진트리 구조입니다.

• max heap인 경우 각 node 값 ≥ child node 값
• min heap인 경우 각 node 값 ≤ child node 값

☑️ Hash table vs BST

✔️BST는 어떤 자료구조 인가요?

이진탐색트리는 정렬된 트리, 모든 child nodes의 개수가 2개 이하

저장과 동시에 정렬을 하는 자료 구조

• 이진탐색트리의 조건

1. 왼쪽서브트리 ≤ 현재 노드 ≤ 오른쪽 서브트리
2. 모든 서브트리들도 1번 조건을 만족한다.

• 삽입/삭제 시간복잡도 O(logN) / O(N)
• worst case → O(N) 균형이 많이 깨져서 한 쪽으로 치우친 BST의 경우 (≒Linked List)
• worst case가 발생하지 않게 하기 위한 방법 자가 균형 이진 탐색 트리(Self-Balancing BST) ➡️ 최대한 이진 트리의 균형이 잘 맞도록 유지하여 높이를 가능한 낮게 유지 ex) AVL tree, Red-black tree, Java의 hashmap의 seperate chaining

✔️Hash table는 어떤 자료구조 인가요?

직접 주소화 방법은 불필요한 공간이 낭비되고, key가 다양한 자료형을 담을 수 없게 됩니다.

hash function h를 이용해서 (key, value)를 index:h(k)에 저장합니다. 이 때, 키 k값을 갖는 원소가 위치 h(k)에 hash된다. 또는 h(k)는 키 K의 해시값이다. 중복되는 key가 있어서는 안된다.

문제점 → Collision: 서로 다른 key의 해시 값이 똑같을 때

해결 방법 → separate chaining, open addressing

✔️좋은 hash function의 조건은 무엇인가요?

상황마다 좋은 hash function은 달라질 수 있으나 대략적인 기준은 연산 속도가 빨라야 하고, 해시값이 최대한 겹치지 않아야 합니다.

✔️⭐️⭐️⭐️Hashtable에서 collision 발생 시, 해결방안

• separate chaining (worst case 시간 복잡도 설명)

Linked list를 이용하여 collision을 해결합니다. 충돌이 발생하면 해당 주소를 가진 linked list에 노드를 추가해줍니다.

worst case의 경우 n개의 모든 key가 동일한 해시값을 갖게 되면 길이 n의 linked list가 생성되게 됩니다. 이 때, 검색의 시간복잡도가 O(n)이 됩니다.

• open addressing(선형 조사법, 중복해시)

collision 발생 시, 미리 정한 규칙에 따라 hash table의 비어있는 slot을 찾습니다. 추가적인 메모리를 사용하지 않으므로 메모리를 적게 사용합니다. 중복 해시 - 클러스터링 문제가 발생하지 않도록 2개의 해시함수를 사용, 하나는 최초의 해시값을 얻을 때 사용하고 또 다른 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용