자료구조

배열(Array)

---

정적으로 필요한만큼만 원소를 저장할 수 있는 공간이 할당

이때 각 원소의 주소는 연속적으로 할당됨

index를 통해 O(1)에 접근이 가능함

삽입 및 삭제는 O(N)

지정된 개수가 초과되면? → 배열 크기를 재할당한 후 복사해야함

리스트(List)

---

노드(Node)들의 연결로 이루어짐

크기 제한이 없음 ( heap 용량만 충분하면! )

다음 노드에 대한 참조를 통해 접근 ( O(N) )

삽입과 삭제가 편함 O(1)

ArrayList

---

동적으로 크기가 조정되는 배열

배열이 가득 차면? → 알아서 그 크기를 2배로 할당하고 복사 수행

재할당에 걸리는 시간은 O(N)이지만, 자주 일어나는 일이 아니므로 접근시간은 O(1)

스택(Stack)

---

LIFO 방식 (나중에 들어온게 먼저 나감)

원소의 삽입 및 삭제가 한쪽 끝에서만 이루어짐 (이 부분을 top이라고 칭함)

함수 호출 시 지역변수, 매개변수 정보를 저장하기 위한 공간을 스택으로 사용함

큐(Queue)

---

FIFO 방식 (먼저 들어온게 먼저 나감)

원소의 삽입 및 삭제가 양쪽 끝에서 일어남 (front, rear)

FIFO 운영체제, 은행 대기열 등에 해당

우선순위 큐(Priority Queue)

---

FIFO 방식이 아닌 데이터를 근거로 한 우선순위를 판단하고, 우선순위가 높은 것부터 나감

구현 방법 3가지 (배열, 연결리스트, 힙)

1.배열

간단하게 구현이 가능

데이터 삽입 및 삭제 과정을 진행 시, O(N)으로 비효율 발생 (한 칸씩 당기거나 밀어야하기 때문)

삽입 위치를 찾기 위해 배열의 모든 데이터를 탐색해야 함 (우선순위가 가장 낮을 경우)

2.연결리스트

삽입 및 삭제 O(1)

하지만 삽입 위치를 찾을 때는 배열과 마찬가지로 비효율 발생

3.힙

힙은 위 2가지를 모두 효율적으로 처리가 가능함 (따라서 우선순위 큐는 대부분 힙으로 구현)

힙은 완전이진트리의 성질을 만족하므로, 1차원 배열로 표현이 가능함 ( O(1)에 접근이 가능 )

root index에 따라 child index를 계산할 수 있음

root index = 0

left index = index * 2 + 1
right index = index * 2 + 2

데이터의 삽입은 트리의 leaf node(자식이 없는 노드)부터 시작

삽입 후, heapify 과정을 통해 힙의 모든 부모-자식 노드의 우선순위에 맞게 설정됨 (이때, 부모의 우선순위는 자식의 우선순위보다 커야 함)

데이터의 삭제는 root node를 삭제함 (우선순위가 가장 큰 것)

삭제 후, 마지막 leaf node를 root node로 옮긴 뒤 heapify 과정 수행

트리(Tree)

---

사이클이 없는 무방향 그래프

완전이진트리 기준 높이는 logN

트리를 순회하는 방법은 여러가지가 있음

1.중위 순회 : left-root-right

2.전위 순회 : root-left-right

3.후위 순회 : left-right-root

4.레벨 순서 순회 : 노드를 레벨 순서로 방문 (BFS와 동일해 큐로 구현 가능)

이진탐색트리(BST)

---

노드의 왼쪽은 노드의 값보다 작은 값들, 오른쪽은 노드의 값보다 큰 값으로 구성

삽입 및 삭제, 탐색까지 이상적일 때는 모두 O(logN) 가능

만약 편향된 트리면 O(N)으로 최악의 경우가 발생

해시 테이블(Hash Table)

---

효율적 탐색을 위한 자료구조

key - value 쌍으로 이루어짐

해시 함수를 통해 입력받은 key를 정수값(index)로 대응시킴

충돌(collision)에 대한 고려 필요

충돌(collision) 해결방안

해시 테이블에서 중복된 값에 대한 충돌 가능성이 있기 때문에 해결방안을 세워야 함

1.선형 조사법(linear probing)

충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장

예시)
ht[k], ht[k+1], ht[k+2] ...

※ 삽입 상황
충돌이 ht[k]에서 일어났다면, ht[k+1]이 비어있는지 조사함. 차있으면 ht[k+2] 조사 ...
테이블 끝까지 도달하면 다시 처음으로 돌아옴. 시작 위치로 돌아온 경우는 테이블이 모두 가득 찬 경우임

※ 검색 상황
ht[k]에 있는 키가 다른 값이면, ht[k+1]에 같은 키가 있는지 조사함. 
비어있는 공간이 나오거나, 검색을 시작한 위치로 돌아오면 찾는 키가 없는 경우

2.이차 조사법

선형 조사법에서 발생하는 집적화 문제를 완화시켜 줌

h(k), h(k)+1, h(k)+4, h(k)+9 ...

3.이중 해시법

재해싱(rehasing)이라고도 함

충돌로 인해 비어있는 버킷을 찾을 때 추가적인 해시 함수 h'()를 사용하는 방식

h'(k) = C - (k mod C)

조사 위치
h(k), h(k)+h'(k), h(k) + 2h'(k) ...

4.체이닝

각 버킷을 고정된 개수의 슬롯 대신, 유동적 크기를 갖는 연결리스트로 구성하는 방식

충돌 뿐만 아니라 오버플로우 문제도 해결 가능

버킷 내에서 항목을 찾을 때는 연결리스트 순차 탐색 활용

5.해싱 성능 분석

a = n / M

a = 적재 비율
n = 저장되는 항목 개수
M = 해시테이블 크기

맵(map)과 해시맵(hashMap)의 차이는?

map 컨테이너는 이진탐색트리(BST)를 사용하다가 최근에 레드블랙트리를 사용하는 중

key 값을 이용해 트리를 탐색하는 방식임 → 따라서 데이터 접근, 삽입, 삭제는 O( logN )

반면 해시맵은 해시함수를 활용해 O(1)에 접근 가능

하지만 C++에서는 해시맵을 STL로 지원해주지 않는데, 충돌 해결에 있어서 안정적인 방법이 아니기 때문 (해시 함수는 collision 정책에 따라 성능차이가 큼)