[CS / 자료구조] 자료구조 정리

Array vs Linked List

1. Array

데이터가 메모리 공간에 연속적으로 저장되어 있는 자료구조

• index를 통해 랜덤 access 가능 ⇒ 탐색 : O(1)
• 컴파일 타임에 배열의 크기가 고정됨 따라서 런타임에 크기를 변경 불가 (⇒ vector, array list)
• 삽입, 삭제 : O(N) 배열의 값들을 모두 이동시켜야 하기 때문에
• 읽기 전용에 유용
• 스택에 저장

2. Linked List

여러개의 노드들이 순차적으로 연결된 자료 구조

• 노드
  • 데이터
  • 다음 노드를 가르키는 포인터
• 메모리 공간에 연속적으로 할당되어 있지 않음
• 탐색 : O(N)
• 삽입, 삭제 : O(1)
• 자료의 삽입 삭제가 빈번하게 일어나는 것에 유용
• 힙에 저장

---

Stack vs Queue

1. Stack

LIFO 후입선출 성질을 가지는 자료구조

• 가장 위의 요소 top, top에만 접근 가능
• 삽입 : push
• 삭제 : pop

2. Queue

FIFO 선입선출 성질을 가지는 자료구조

• 추출되는 부분을 front, 삽입하는 부분을 rare라고 함
• 삽입 : enqueue
• 삭제 : dequeue

---

 

트리

1. 그래프

정점과 간선으로 이루어진 자료구조

2. 트리

비선형 자료구조

• 부모 자식 관계를 가지는 계층구조
• 간선수 = 노드의 수 - 1
• 트리 내의 A노드와 B노드 사이의 경로는 반드시 존재함
• 구성
  • root
  • 내부
  • 리프 : 자식 노드가 없는 노드
• 깊이 : 최단거리의 길이(개별 노드에 대한 높이)
• 높이 : root에서 리프까지 가장 긴거리

3. 이진트리

자식 노드의 수가 2개 이하인 트리

• 종류
  • 정이진트리 : 자식 노드의 수가 0 또는 2
  • 완전이진트리 : 마지막 레벨을 제외하고 모두 채워져있고 왼쪽에서부터 채워지는 트리
  • 변질이진트리
  • 포화이진트리
  • 균형이진트리 : 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1이하인 트리 (레드블렉, AVL)

 

4. 이진탐색트리

루트의 왼쪽은 루트보다 작고, 오른쪽은 루트보다 큰 값을 가지는 트리

탐색에 유리하다 ⇒ O(logN)

최악의 경우 ⇒ O(N) : 선형적 트리일 때

이를 막기 위해 자가 균형 이진 탐색 트리를 사용

 

5. 균형 이진 탐색 트리

 

AVL

 

자식의 높이차를 비교

• 자식 서브트리의 높이차 ≤ 1
• 높이 차가 1보다 커지면 Rotation을 통해 균형 유지
• O(log N) : 높이차를 이용하기 때문에
• Balance Factor = 왼쪽 자식 높이 - 오른쪽 자식 트리 높이
• 재구성
  • LL : 왼쪽 로테이션
  • RR : 오른쪽 로테이션
  • LR : 왼쪽 + 오른쪽
  • RL : 오른쪽 + 왼쪽
  •  

 

 

 RB(레드블랙)

노드에 규칙에 맞게 색을 부여

• 규칙
  1. 노드는 검정 혹은 빨강
  2. 루트 노드는 항상 검정
  3. 빨강이 연속적으로 나올 수 없다
  4. 모든 리프는 검정이다
  5. 한 리프노드에서 루트로 가는 경로에서 만나는 검은 색 노드의 수는 같다
• 재구조화 : 삼촌 노드를 기준(부모의 형제 노드를 기준으로 바꿈)
  • Restructing : 검정일 때
    • 부모, 조부모, 자기자신 오름차순 배열
    • 가운데 값을 루트로 놓음
    • O(1) : 포인터 변경
  • Recoloring : 빨강일 때
    • 부모와 삼촌 노드를 검정으로 변경
    • 조부모를 빨강으로 변경
    • 조부모가 root일 때까지 반복
    • 최악 O(N), 평균O(logN)

 

AVL	RB
높이를 항상 logN으로 유지시키기 때문에 조회 성능이 좋다	삽입, 삭제 시 균형을 맞추는 작업이 적다
BF값을 가지고 있어야 해서 추가적인 메모리 공간 필요	색상 저장시 1bit만 추가로 저정하면 됨

 

---

Heap & Priority Queue

1. 우선순위 큐

pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 **우선 순위가 가장 높은** 원소가 나오는 큐

• 디스크립트 스케줄링 : 운영 체제에서 프로세스나 스레드에 서로 다른 우선순위를 할당하고, 가장 높은 우선순위를 가진 작업부터 처리
• 네트워크 트래픽 제어 :데이터 패킷에 우선순위를 부여하여 중요한 데이터가 먼저 전송되도록 함
• 다익스트라 알고리즘의 최단 경로 찾기

 

2. Heap

• 우선 순위 큐를 구현하기 위해 사용되는 완전 이진트리 기반의 자료구조
• 반정렬 상태 유지 ⇒ 부모노드와 서브트리 간 대소 관계가 성립됨
• 중복 값 허용

• 종류
  • 최대힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 이진트리
  • 최소힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 이진트리
• 최소 힙 삽입 동작 원리
  1. 삽입 시 가장 왼쪽 최하단부 노드에 삽입됨
  2. 부모의 노드와 비교하며 부모보다 작으면 부모와 swap
  3. 계속해서 자신보다 작은 값이 존재할 때까지 swap
• 최소 힙 삭제 동작 원리
  1. 트리 구조 상 가장 마지막 위치와 루트 값 swap
  2. 최소 값인 루트 값 제거
  3. 삽입 동작과 비슷하게 힙의 성질에 위배되지 않게 swap 반복

시간복잡도

• 검색 **O(logN) :** 아무리 많이 비교를 해도 트리의 높이 만큼만 비교
• 최대/최소 값 확인 O(1)

💡 단, 10번째로 작은 원소같은 값은 확인 불가능 ⇒ 이진 검색 트리와 다른점!

 

---

Hash

• 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정 길이의 데이터로 매핑하는 것
• key - value 형태의 자료구조
• 해시 함수를 구현해 데이터 값을 해시 값으로 매핑함 ⇒ 즉, 해시함수를 사용해 키를 해시값으로 매핑하고 hash key - value로 해시 테이블에 저장하는 것
• 하지만, 데이터가 많아지만 다른 데이터가 같은 해시 값으로 충돌나는 collision 현상 발생
• 해시테이블에 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색 모두 평균적으로 시간복잡도 **O(1)**을 가짐

충돌 해결법

• 체이닝 : 같은 인덱스에 여러 개의 요소가 위치할 수 있도록 링크드 리스트나 다른 자료구조를 사용하는 방법
• 개방 주소법 : 충돌이 발생하면 다른 인덱스에 데이터를 저장하는 방식. 선형 탐색, 제곱 탐색, 이중 해싱