250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- STUDYENGLISH
- readingbook
- BFS
- nightroutine
- dfs
- englishbook
- 코테
- English
- SQL
- 직무면접
- 원서
- the midnight library
- sw expert
- 프로그래머스
- 삼성
- 원서읽기
- 알고리즘 문제
- 알고리즘
- 코테 준비
- 쉬운 알고리즘 문제
- D4
- MySQL
- 백준
- sw expert academy
- 코테 대비
- swexpertacademy
- 원서읽자
- 완전탐색
- 코딩테스트
- PyQt
Archives
- Today
- Total
시나브로
[기술면접준비] 자료구조 본문
728x90
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)
규칙
- 이진 탐색 트리의 노드에 저장된 키는 유일하다
- 부모의 키가 왼쪽 자식 노드의 키보다 크다
- 부모의 키가 오른쪽 자식노드의 키보다 작다
- 왼쪽 오른쪽 서브트리도 이진 탐색 트리이다.
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의 삽입,삭제 연산과정에서 발생할 수 잇는 문제점을 해결하기 위해 만드렁진 자료구조
정의
- 각 노드의 red or black이라는 색깔을 가진다
- root node의 색깔은 Black이다
- 각 leaf node는 black이다
- 어떤 노드의 색깔이 red라면 두 개의 children의 색깔은 모두 blackc이다
- 각 노드에 대해서 노드로부터 descendant leaves까지의 단순 경로는 모두 같은 수의 black node들을 포함하고 있다. 이를 해당 노드의 black-height라고 한다.
특징
- Binary Search Tree이므로 BST의 특징을 모두 갖는다
- Root nodeㅂ터 leaf node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다. : balanced 상태
- 노드의 child가 없을 경우, child를 가리키는 포인터는 NULL값을 저장한다. 이러한 NULL들은 leaf node로 간주된다.
삽입
1.BST의 특성을 유지하면서 노드를 삽입
2. 삽입된 노드를 red로 지정 : black-height를 최소화하기 위해서
3. RBT의 특성 위배시, 노드의 색깔을 조정한다
4. Black-Height가 위배되었을 경우, rotation을 통해 height 조정한다삭제
- BST의 특성을 유지하면서 노드를 삭제
- 삭제될 노도의 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
- Open Address : 개방 주소법
- 충돌이 발생하면, 다른 해시버킷에 해당 자료에 삽입하는 방식
- 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)
728x90
'취업' 카테고리의 다른 글
[기술면접준비] 운영체제 (0) | 2020.11.15 |
---|---|
[기술면접준비] 알고리즘 (0) | 2020.11.14 |
[기술면접준비] 네트워크 (0) | 2020.11.14 |
[기술면접 준비] 개발 지식 (0) | 2020.11.13 |
싸피(ssafy_서울) 4기 합격 후기 (16) | 2020.06.30 |
Comments