자료 구조

Array vs Linked List

Array 배열

• 가장 기본적인 자료구조
• 논리적 저장 순서와 물리적 저장 순서가 일치
• 찾고자 하는 원소의 인덱스를 알고 있으면 O(1) 접근 가능
• 중간 삽입 혹은 삭제의 경우 shift 를 해줘야 하기 때문에 in worst case O(N)의 time complexity가 나온다

Linked List 연결 리스트

• 각 노드가 다음 노드의 링크 주소를 가진다
• 삽입, 삭제의 경우 다음 노드의 주소를 바꿔주기만 하면 되기 때문에 O(1)으로 해결 가능 하다
• 하지만 삽입/삭제할 노드의 위치를 찾아야 되기 때문에 첫번째 원소부터 순차적으로 확인하여 결국 O(N)의 time complexity가 나온다
• tree 구조에서 사용된다

Stack vs Queue

Stack

• 선형 자료구조의 일종으로 Last In First Out (LIFO)
• 늦게 들어간 녀석들은 그 위에 쌓이게 되고 호출 시 가장 위에 있는 녀석이 호출되는 구조

Queue

• 선형 자료구조의 일종으로 First In First Out (FIFO)
• Stack 과는 반대로 먼저 들어간 놈이 맨 앞에서 대기하고 있다가 먼저 나오게 되는 구조
• Java Collection 에서 Queue 는 인터페이스

Tree

Binary tree 이진 트리

• 모든 노드가 두개의 서브 트리로 나뉘어 진다
• Perfect Binary Tree (포화 이진 트리), Complete Binary Tree (완전 이진 트리), Full Binary Tree (정 이진 트리)가 있다

Binary Search Tree 이진 탐색 트리

• 데이터를 저장하는 규칙이 있다

  규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
  규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
  규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
  규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

• 탐색 연산은 O(log n)의 시간 복잡도를 갖는다
• 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우를 Skewed Tree (편향 트리)라고 한다

switch(삭제) {
	case (자식이 없는 leaf 노드): 그냥 지운다
        case (자식이 1개인 노드): 지워진 노드에 자식을 올린다
        case (자식이 2개인 노드): 
        	자식 노드 중에서 삭제할 노드 보다 크면서 가장 작은 값 OR 
		자식 노드 중에서 삭제할 노드보다 작으면서 가장 큰 값을 올린다
}

Red Black Tree 적흑 트리

• BST 기반의 트리
• Search, Insert, Delete --> O(log n)
• 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심

정의:
1. Red or Black
2. Root node는 Black
3. Leaf node는 Black
4. Red 인 노드의 자식은 Black
5. root에서 leaf node 까지 모든 경로가 같은 수의 black nodes를 포함하고 있다 (Black height)

Insertion

1. 노드를 삽입
2. 삽입된 노드를 Red로 지정 (Black Height 변경을 최소화 하기 위해!)
3. 노드 색 조정 및 rotation을 통한 height 조정

Rotation

Case 1: 삽입된 노드의 uncle 노드가 Black -> Restructuring
Case 2: 삽입된 노드의 uncle 노드가 Red -> Recoloring

Restructuring

1. 나, 나의 부모, 조부모를 오름차순으로 정렬
2. 가운데에 위치한 값을 부모로 만들고, 나머비들을 자식으로 둔다
3. 부모는 Black, 자식은 Red로 지정한다
   Time Complexity: Restructuring (순서결정, 트리 구현, 노드 재구조) 자체는 O(1) 이지만, Insertion + Restructuring 은 O(log n)이다

Recoloring

1. 현재 삽입된 노드의 부모와 그 형제를 Black 으로 하고 조부모를 Red로 지정한다 *조부모가 root가 아니었을시 Double Red 가 다시 발생할 수 있다
   Time Complexity: O(log n)

Hash Table

• 데이터 고유의 인덱스로 접근하여 average time complexity 가 O(1)이다
• Hash function 을 사용하여 저장할 데이터와 연관된 고유의 숫자를 만들어 인덱스로 사용

Hash Function

• Hashcode 를 반환
• 저장되는 값들의 key 값을 Hash function 을 통해서 작은 범위의 값으로 변환
• Collision: 서도 다른 두 개의 key 가 같은 인덱스로 hashing 되는 경우

Collision 해결 방법

1. Open Address 방식: Collision 이 발생하면 다른 Hash bucket 을 찾아 삽입

   1.1 Linear Probing: 순차적으로 탐색하여 비어 있는 bucket 을 찾을 때 까지 탐색
   1.2 Quadratic Probing: 2차 함수를 이용해 탐색
   1.3 Double Hashing Probing: Collision 발생 시, 다른 해시 함수를 한번 더 적용

2. Separate Chaining 방식: 보조 해시 함수를 통해 Collision 방지

   2.1 linked list: 각각의 bucket 을 linked list 로 만들어 Collision 발생 시 해당 bucket 의 list 에 추가
   2.2 Tree: linked list 대신 tree 를 사용

   • 데이터가 적다면 tree 는 메모리 사용량이 많기 때문에 linked list를 사용

Graph

정점과 간선의 집합, Graph

트리 또한 그래프이며, 그 중 사이클이 허용되지 않는 그래프를 말한다.

그래프 구현

• 인접 행렬 (adjacent matrix) : 정방 행렬을 사용하는 방법

  • 해당하는 위치의 value 값을 통해서 vertex 간의 연결 관계를 O(1) 으로 파악할 수 있다
  • Edge 개수와는 무관하게 V^2 의 Space Complexity 를 갖는다
  • Dense graph 를 표현할 때 적절할 방법

• 인접 리스트 (adjacent list) : 연결 리스트를 사용하는 방법

  • vertex 의 adjacent list 를 확인해봐야 하므로 vertex 간 연결되어있는지 확인하는데 오래 걸린다
  • Space Complexity 는 O(E + V)이다
  • Sparse graph 를 표현하는데 적당한 방법