[기술면접준비] 자료구조

Array vs Linked List

Array

• 논리적 저장 순서와 물리적 저장 순서가 일치
• 인덱스로 해당 원소에 접근할 수 있다.
• random access가 가능하다
• 추가/삭제시, shift 연산이 필요

Linked List

• Array의 문제점을 해결하기 위한 자료구조
• 삽입/삭제 과정에서의 shitf 연산이 필요없다
• 탐색 과정에서 첫번째 원소부터 확인해야된다 = 탐색시간이 오래걸린다.
• 탐색 과정 때문에 삽입/삭제 과정에서 O(n)의 시간이 추가 발생하게 된다.

stack

• Last In First Out : LIFO

Queue

• First In First Out : FIFO

Tree

• 비선형자료구조
• 계층적 구조

Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

Binary Tree :이진트리

두 개의 서브 트리 모두 이진트리여야한다.
level : 각 층별 숫자 [ root level : 0 ]
height : 최고 레벨
parent : i/2 [ root index : 1 ]
left_child : i*1 [ root index : 1 ]

Perfect Binary Tree : 포화 이진 트리

Complete Binary Tree : 완전 이진 트리

Full Binary Tree : 정 이진 트리

Binary Search Tree : BST

• 효율적인 탐색을 위한 저장 방법
• 탐색 연산 : O(log n) => 최악의 경우[편향이진트리 ], O(n)

규칙

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

Rebalencing 기법

• O(n)의 탐색기간이 걸리는 경우를 해결
• 균형을 잡기 위해 트리 구조의 재조정을 하는 기법
• ex. Red-Black Tree

Binary Heap

• 자료구조의 일종, Tree 의 형식
• Complete Binary Tree
• Max Heap / Min Heap

Red Black Tree

• BST를 기반으로 하는 트리형식의 자료구조
• 탐색, 입력, 삭제 => O(log n)
• BST의 삽입,삭제 연산과정에서 발생할 수 잇는 문제점을 해결하기 위해 만드렁진 자료구조

정의

1. 각 노드의 red or black이라는 색깔을 가진다
2. root node의 색깔은 Black이다
3. 각 leaf node는 black이다
4. 어떤 노드의 색깔이 red라면 두 개의 children의 색깔은 모두 blackc이다
5. 각 노드에 대해서 노드로부터 descendant leaves까지의 단순 경로는 모두 같은 수의 black node들을 포함하고 있다. 이를 해당 노드의 black-height라고 한다.

특징

1. Binary Search Tree이므로 BST의 특징을 모두 갖는다
2. Root nodeㅂ터 leaf node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. : balanced 상태
3. 노드의 child가 없을 경우, child를 가리키는 포인터는 NULL값을 저장한다. 이러한 NULL들은 leaf node로 간주된다.

삽입
1.BST의 특성을 유지하면서 노드를 삽입
2. 삽입된 노드를 red로 지정 : black-height를 최소화하기 위해서
3. RBT의 특성 위배시, 노드의 색깔을 조정한다
4. Black-Height가 위배되었을 경우, rotation을 통해 height 조정한다

삭제

1. BST의 특성을 유지하면서 노드를 삭제
2. 삭제될 노도의 child의 개수에 따라 rotation방법이 다라진다.
   2-1. 지워진 노드의 색깔이 black이라면 black-height가 1 감소한 경로에 black node가 1개 추가될도록 rotation하고 색깔을 조정한다.
   2-2. 지워진 노드의 색깔일 red라면 violation이 발생하지 않으므로 RBT가 그대로 유지한다.

Hash Function

• Hash Function의 결과값 : hashcode
• collision : 서로 다른 두개의 키가 같은 인덱스로 hashing되면 같은 곳에 저장할 수 없게 된다.
• 무조건 1:1로 만드는 것보다는 collision을 최소화하는 방향으로 설계 & collision 발생시, 대응 방법을 선택하는 것이 중요
• 1:1로 만드는 경우는 거의 불가능하고 만들어도 array와 다를바가 없어 메모리가 너무 커진다.
• Collision이 많아질 수록 O(1) -> O(n)으로 변경
• hash function이 매우 중요함.

Resolve Conflict

1. Open Address : 개방 주소법

• 충돌이 발생하면, 다른 해시버킷에 해당 자료에 삽입하는 방식

2. Separate Chaining : 분리연결법
   2-1. 연결리스트를 사용하는 방식
   2-2. tree[RBT]를 사용하는 방식

해시버킷 동적확장
일정 개수 이상이 되면[임계점 : 75%], 해시버킷의 개수를 2배 늘린다.

Graph

• 정점과 간선의 집합
• Undirected Graph / Directed Graph
• Degree : 각 정점에 연결되 edge의 개수
• Weight Graph : 가중치 있음
• Sub Graph : 본래의 그래프이 일부 정점 및 간선으로 이루어진 그래프

구현방식

인접행렬 : 정방행렬 사용
인접리스트 : 연결리스트 사용

그래프 탐색

DFS 깊이 우선탐색 O(V+E)
BFS 너비 우선탐색 O(V+E)

MST Minimum Spanning Tree

Kruskal O(E log E)
Prim O(E log V)