데이터 엔지니어링 3일차 TIL

학습 내용

큐(Queue)

자료를 보관할 수 있는 선형구조
선입선출(FIFO : First-In-Fisrt-Out)의 특징을 가진다.

큐의 연산의 정의
size() - 큐에 들어있는 데이터 원소의 수를 구한다. O(1)
isEmpty() - 현재 큐가 비어 있는지를 판단 O(1)
enqueue(x) - 원소x를 큐에 추가 O(1)
dequeue() - 큐의 맨 앞에 저장된 원소를 제거 O(n)
peek() - 큐의 맨 앞에 저장된 원소를 반환 O(1)

큐의 활용
자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
자료의 생성이 여러곳에서 일어나는 경우
자료의 생성과 그 자료를 이용하는 작업이 양쪽 다 여러곳에서 일어나는경우(컴퓨터 시스템내부) 등

환형 큐(Circular Queue)
정해진 개수의 저장공간을 빙 돌려가며 이용하는 것
front와 rear를 적절히 계산하여 배열을 환형으로 재활용한다.

isFull() - 큐에 원소가 꽉 차 있는지를 판단

우선순위 큐(Priority Queues)
큐가 FIFO방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
ex)운영체제의 CPU스케줄러

트리(Trees)
노드와 간선을 이용하여 데이터의 배치 형태를 추상화한 자료 구조

뿌리노드(root) : 뿌리노드
노드의 차수(degree) : 자식으로 연결되는 간선의 갯수
부모노드(parent) : 간선으로 연결된 관계에서 뿌리노드에 더 가까운 노드
자식노드(child) : 간선으로 연결된 관계에서 뿌리노드에 더 먼 노드
트리의 높이(depth) : 최대수준(level) +1

이진트리(Binary Tree)
모든노드의 차수가 2이하인 트리

이진트리의 연산
size() - 현재 트리에 포함되어 있는 노드의 수를 구함
depth() - 현재 트리의 깊이를 구함

포화 이진트리(Full Binary Tree)
모든 레벨에서 노드들이 모두 채워져 있는 이진트리
노드의 갯수 : 2^k-1

완전 이진 트리(Complete Binary Tree)
레벨k-2까지는 모든 노드가 2개의 자식을 가진 포화이진트리이며
레벨k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 트리

깊이 우선 순회 (depth first traversal)
중위순회(in-order traversal)
자기 자신을 중간에 방문 (L-나-R 순서)

전위순회(pre-order traversal)
자기 자신을 먼저 방문 (나-L-R 순서)

후위순회 (post-order traversal)
자기 자신을 마지막에 방문(L-R-나 순서)


넓이 우선 순회(breadth first traversal)
level이 낮은 노드를 우선적으로 방문
같은 수준의 노드들 사이에는, 부모 노드의 방문순서에 따라 방문한다.
왼쪽 자식 노드를 오른쪽 자식노드보다 먼저 방문.

이진 탐색 트리(Binary Search Trees)
모든 노드에 대해서, 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리이다.

장점 : 데이터 원소의 추가, 삭제가 용이하다.
단점 : 공간 소요가 크다.

이진탐색 트리의 연산
insert(key, data) - 트리에 주어진 데이터 원소를 추가
remove(key) - 특정 원소를 트리로부터 삭제
lookup(key) - 특정 원소를 검색
inorder() - 키의 순서대로 데이터 원소를 나열
min(), max() - 최소 키, 최대 키를 가지는 원소를 각각 탐색

이진 탐색트리는 트리의 왼쪽, 오른쪽이 비슷할 때에 효율적이지만 한쪽으로 치우쳐져 있으면 효율적이지 못하다. 
=>높이의 균형을 유지해야 한다. - AVL tree, Red-Black tree 등

힙(heap)
루트노트가 언제나 최대값 또는 최솟값을 가지는 완전 이진트리이다.

최대/최소 힙의 응용
1. 우선 순위큐 구현
2. 힙 정렬(heap sort) 구현

 

느낀점

 

여러자료 구조들의  종류와 응용 및 적합한 활용처에 대해 알 수 있었다.

아직까지 클래스 사용이 익숙하지 않아 구현 실습이 쉽지 않았다.

이번시간의 강의는 내용이 너무 많아서 좀 힘들었다.

아직 선택실습도 많이 남아있기에 코어타임 시간이 끝나고도 더 해야할 것 같다.

좋은 강의를 들을 수 있어 좋았다.