02_자료구조
본 게시글의 모든 내용은 https://github.com/JaeYeopHan/Interview_Question_for_Beginner를 참고하여 작성되었습니다.
Array vs Linked List
Array
특징
- 논리적 저장순서와 물리적 저장 순서가 일치
- 인덱스로 해당 원소에 접근(O(1))
- random access가 가능
단점
- 삭제 또는 삽입의 과정에서 해당 원소에 접근해(O(1)) + 한가지 작업을 더 해줘야함
-> 시간이 더 걸림(O(n))
예를 들어, 배열의 원소 중 어느 원소를 삭제하면, 배열의 연속적인 특징이 깨지게 되어 빈공간이 생기게 된다. 그래서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift 해주저야 한다.
Linked List
특징
- 각자의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억
- 삽입과 삭제를 O(1)로 해결가능
- 트리 구조의 근간
단점
- 논리적 저장순서와 물리적 저장 순서가 일치하지 않기 떄문에 Search에서 O(N) 시간이 걸림
- 결국 linked list는 search에 O(N)+ 삽입/삭제에도 O(N) [search를 2번하니까..]
Stack vs Queue
Stack : 선형 자료 구조의 일종(LIFO)
`Last in First Out`
Queue : 선형자료구조의 일종(FIFO)
`First in First out`
Java Collection에서 Queue는 인터페이스이다. `priority queue`등을 사용할 수 있다.
TREE
트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 구조.`계층적 관계`를 표현
구성요소
- 노드(Node): 트리를 구성하고 있는 각각의 요소
- 간선(Edge): 트리를 구성하기 위해 노드와 노드를 연결하는 선
- 루트노드(Root Node): 트리 구조에서 최상위에 있는 노드
- Terminal Node(=leaf Node, 단말노드): 하위에 다른 노드가 연결되어 있지 않은 노드
- Internal Node(내부노드, 비단말노드): 단말노드를 제외한 모든 노드, 루트노드를 포함
특징
- 각 층 == 레벨(루트노드(0)부터 시작~루트의 최고 레벨(height(높이)))
Binary Tree(이진트리)
루트노드를 중심으로 두개의 서브 트리로 나뉘어진다. 또한 나뉘어진 두 서브 트리도 모두 이진트리
특징
- 나누어진 서브 트리도 이진트리 예)공집합, 노드가 1개인 트리
- 노드의 개수 :N
- root가 1에서 시작할때, i번째 노드에 대해서
parent(i) = i/2
left_child = 2i
right_child= 2i+1
의 index 값을 갖는다.
종류
- `포화이진트리(Perfect binary tree) `: 모든 레벨이 꽉찬 이진 트리
- `완전 이진트리(Complete binary tree)`: 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진트리
- `정 이진 트리(Full binary tree)`: 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리
BST(Binary Search Tree)
특징
- 시간복잡도 : `O(log n)`, 트리의 높이를 하나씩 더해갈수록 노드의 수가 2배씩 증가 O(h)라 보아도 됨.
- `편향트리(skewed tree)`가 될 경우, 저장 순서에 따라 한쪽 노드만 추가되기 때문에 최악의 경우 시간 복잡도가 O(n), 배열보다 많은 메모리 사용
- 이 문제 해결을 위해, `Rebalancing기법` 등장. 균형을 잡기 위한 트리구조의 재조정
- 종류: Red-Black Tree
- 어떻게 찾을 것인가만을 고민하는 것이 아니라, 효율적인 탐색을 위한 저장방식이 무엇인가를 고민해야한다.
데이터를 저장하는 규칙
규칙1. 이진 탐색 트리의 노드에 저장된 키는 유일
규칙2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다
규칙3. 루트 노드의 키가 오른쪽 서브트리를 구성하는 어떠한 노드의 키보다 작다.
규칙4. 왼쪽과 오른쪽 서브트리도 이진탐색 트리이다.
Binary Heap
특징
- tree의 형식
- 배열에 기반한 Complete Binary tree(완전 이진 트리)
- 루트노드 1부터 시작
- 시간 복잡도: O(1)
- random access 가능
- heapify 과정을 거쳐 heap구조를 유지하면, 시간 복잡도 O(log n)
힙 종류
- 최대 힙: 각 노드의 값이 해당 children의 값보다 크거나 같은 Complete Binary tree
- 최소 힙: 각 노드의 값이 해당 Children의 값보다 작거나 같은
Red Black Tree
특징
- 시간복잡도 : O(log n) -- 탐색, 삽입, 삭제
- 동일한 노드의 개수일 때, depth를 최소화하여 시간복잡도를 줄이는 것
- 동일한 노드의 개수일 떄, depth가 최소가 되는 경우의 tree: complete binary tree
- 루트 노드 부터 leaf 노드까지 모든 경로중 최소경로와 최대 경로의 크기 비율은 2보다 크지 않다. (balanced 상태)
- 노드의 child가 없을 경우, child를 가리키는 포인터는 NIL 값을 저장한다.
정의
각 노드는 red, black 색을 가짐
leaf node는 black
어떤 노드의 색이 red면, children의 색은 모두 black
각 노드에 대해서 노드로 부터 descendant leaves까지의 단순 경로는 모두 같은 수의 black nodes들을 포함하고 있다. 이를 해당 노드의 black-height라고 한다.
삽입
- 삽입된 노드의 색깔은 red -> black-height 변경을 최소화하기 위함.
- 삽입 결과 RBT의 특성 위배(violation)시 노드의 색깔을 조정, Black-Height 가 위배되었다면 rotation을 통해 height를 조정
- RBT의 동이랗ㄴ height에 존재하는 internal node 들의 Black-hieght가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2미만으로 유지된다.
삭제
BST의 특성을 유지하면서 해당 노드를 삭제. 삭제될 노드의 child의 개수에 따라 rotation방법이 달라지게 된다. 지워진 노드의 색이 Black이면 black-hieght가 1감소한 경로에 black node가 1개 추가되도록 rotation 하고 노드의 색깔의 조장한다, 지워진 노드의 색이 red면, violation이 발생하지 않으므로 RBT가 유지된다.
java collection에서 ArrayList/ HashMap에서 seperate chaining에서도 사용
Hash Table
hash는 내부적으로 배열을 사용해 데이터를 저장하기 때문에, 빠른 검색속도
특징
- 배열을 이용해 데이터 저장
- 시간복잡도 : O(N)
- 인덱스로 저장되는 key 값이 불규칙
- 특별한 알고리즘을 이용해 저장할 데이터와 연관된 고유한 숫자를 만들어 낸뒤 이를 인덱스로 사용한다.
Hash Func
hash method또는 해시 함수라고 하며, 이 메소드에 의해 반환된 데이터의 고유 숫자의 값을 hashcode라고 한다. 저장되는 값들의 key값을 hash func를 통해 **작은범위의 값들**로 바꿔준다.
collision: 서로 다른 2개의 키가 같은 인덱스로 hashing되면 같은 곳에 저장할 수 없게 된다.
hash func의 조건
- 키 전체를 참조해 해쉬값을 만들어 내는 것.
- 1:1로 무조건 바꾸는 것보다, collision을 최소화하는 방향으로 설계하는 것이 중요하다. 1:1대응으로 hash func을 만들면 메모리를 너무 차지할 뿐
- Collosion이 많아지면 시간복잡도가 O(1) -> O(n)에 가까워진다.
resolve confilct
open Address(개방 주소법)
해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식.
방법1. Linear probing 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행
방법2. Quadratic probing 2차 함수를 이용해 탐색할 위치를 찾음
방법3. Double hashing probing 하나의 해쉬 함수에서 충돌일 발생하면 2차 해쉬함수를 이용해 새로운 주소를 할당한다. 많은 연산량을 요구
- Separate Chaining 방식(분리연결법)
자바 7은 separate chaining 방식을 이용해 hashmap을 구현하고 있다.
구현 방식
> 연결리스트를 사용하는 방식
>
> - 장점: 시간복잡도 줄어듬
> - 단점 : 연결리스트의 오버레드 증가, 테이블 확장을 늦출 수 있다.
> 트리를 사용하는 방식(RBT)
>
> 데이터가 많을 때 사용 (key-value값이 6/8이하인 경우)
Open Address vs Seperate Chaining
두 방식 모두 Worst Case: O(M)
개방 주소법은 연속된 공간에 데이터를 저장해서 캐시 효율이 좋다.데이터 개수가 적다면 개방주소법을 사용해서
**보조 해시함수**
key의 해시 값을 변형하여 해시 충돌가능성을 줄이는 것. seperate chaining 방식을 사용할 때 함께 사용되며ㅡ 보조 해시 함수로 worst case에 가까워지는 경우를 줄일 수 있다.
해시버킷 동적 확장(Resize)
해시 버킷의 개수가 적다면 메모리 사용을 아낄 수있지만 해시 충돌로 인해 성능상 손실이 발생
hashmap은 key-value 쌍 데이터 개수가 일정 개수 이상이되면 해시 버킷의 개수를 두배로 늘린다. 해시 충돌로 인한 성능 손실 문제를 어느정도 해결할 수 있다.
해시 버킷 크기를 두배로 확장하는 임계점을 데이터의 개수가 해시 버킷 개수의 75%, load factor `0.75`
Graph
구현방식
인접행렬 : 시간복잡도 O(1)
인접리스트: 시간복잡도 O(E+V)
DFS : 깊이 우선 탐색
시간복잡도 : O(V+E), V:vertext, E:edge
BFS : 너비 우선탐색
minimum spanning tree
spanning tree 중 edge weight 합이 최소인 spanning tree를 말한다. 그래프 모든 vertex가 cycle없이 연결된 상태
최소신장트리(MST)
Kruskal Algo
초기화 작업으로 edge 없이 vertex들만으로 그래프를 구성. weight가 제일 작은 edge부터 검토. edge set을 non-decreasing으로 sorting해야한다.
시간복잡도 O(eloge)
순서
- 간선들의 가중치 오름차순 정렬
- 사이클을 형성하는 간선 제외
- N-1개의 간선 생성 종료
https://gmlwjd9405.github.io/images/algorithm-mst/kruskal-example2.png
Prim Algo
시간복잡도 : O(ElogV)
순서
정점 선택을 기반으로 하는 알고리즘
인접 점정점 중 최소 간선으로 연결된 정점 선택
N-1개의 간선이 생성되면 종료
https://gmlwjd9405.github.io/images/algorithm-mst/prim-example.png
사이클을 형성하는지 체크하는 것이 중요
'개발이야기 > 전공 기초' 카테고리의 다른 글
| 1. 개발 상식 정리 (0) | 2020.03.16 |
|---|