[클라우딩 어플리케이션 엔지니어링 TIL] TIL(Today I Learned) - Day12
들어가기전에
비선형 자료구조를 배우면서 실전문제와 함께 익숙해지는 강의를 배웠다.
강의를 보며 나의 주관적인 생각이 들어가 정리한것임으로 반드시 '내가 적은것이 맞다' 라는 것이 아니므로 읽어보시고 이상한부분이 있다면 저에게 알려주시거나 꼭 다른곳도 검색해서 찾아보기를 바랍니다.
목차
1. 학습 주제 | 자료 구조 中
- 해시 테이블
- 비선형 자료구조 - 그래프
- 비선형 자료구조 - 트리
- 비선형 자료구조 - 힙
2. 주요 메모 사항 소개
3. 공부하며 어려웠던 내용
학습 주제.1
해시 테이블
키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
삽입은 O(1)이며, 키를 알고 있다면 삭제, 탐색도 O(1)로 수행한다.
해시 함수
입력받은 값을 특정 범위 내 숫자로 변경하는 함수
해시 테이블의 문제점
해시 함수의 결과가 동일한 결과가 발생할 수 있다.
해시 충돌의 방지법
선형 탐사법 : 충돌이 발생하면 옆으로 한 칸 이동
제곱 탐사법 : 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
이중 해싱 : 충돌이 발생하면 다른 해시 함수를 이용
분리 연결법 : 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가 * 하나의 버킷이 무한정 늘어날 수 있는 단점이 있음
학습 주제.2
비선형 자료구조 - 그래프
정점(Vertex) 간선(Edge)으로 이루어진 비선형 자료구조
그래프의 특징
- 정점은 여러 개의 간선을 가질 수 있다.
- 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
- 간선은 가중치를 가질 수 있다.
- 사이클이 발생할 수 있다.
무방향 그래프
간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다
표현하기에 (A, B)와 (B, A)는 같은 간선으로 취급 ex) 양방향 통행 도로
방향 그래프
간선에 방향성이 존재하는 그래프
양방향으로 갈 수 있더라도 <A, B>와 <B, A>는 다른 간선으로 취급 ex) 일방 통행
연결 그래프
모든 정점이 서로 이동 가능한 상태인 그래프
비연결 그래프
특정 정점쌍 사이에 간선이 존재하지 않는 그래프 ex) 친한 친구 설문 그래프
완전 그래프
모든 정점끼리 연결된 상태인 그래프
사이클 그래프
그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분
그래프의 구현 방법
인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List) 두 가지 방식으로 그래프를 표현할 수 있다.
인접 행렬 (Adjacency Matrix)
인접 리스트 (Adjacency List)
학습 주제.3
비선형 자료구조 - 트리 (Tree)
방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조
특징
- 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다
- 정점이 n개인 트리는 반드시 n-1개의 간선을 가진다.
- 루트에서 특정 점정으로 가는 경로는 유일하다.
이진 트리 (Binary Tree)
이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미
이진 트리 특징
- 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있다.
- 정점이 N개인 포화 또는 완전 이진 트리의 높이는 log n이다.
- 높이가 h인 포화 이진 트리는 2ᵸ - 1개의 정점을 가진다.
- 일반적인 이진 트리를 사용하는 경우는 많지 않다. 다음 자료구조에 응용된다.
1. 이진 탐색 트리
2. 힙
3. AVL 트리
4. 레드 트리 트리
트리(tree) 구현 방법
그래프와 마찬가지로 인접 행렬, 인접 리스트 두 가지 방식으로 구현할 수 있다.
이진 트리(Binary Tree)의 구현 방법
배열 혹은 요소에 링크가 2개 존재하는 연결 리스트로 구현할 수 있다.
이진 트리 구현 방법 | JavaScript
1. 배열(Array)을 이용한 방법
// 0번 인덱스는 편의를 위해 비워둔다.
// Left = Index * 2
// Right = Index * 2 + 1
// Parent = floor(Index / 2)
const tree = [
undefined,
// 1
9,
// 1*2, 1*2+1
3, 8,
// 2*2, 2*2+1, 3*2, 3*2+1
2, 5, undefined, 7,
// 4*2, 4*2+1, 5*2, 5*2+1
undefined, undefined, undefined, 4
];
1. 이진 트리(Linked List)를 이용한 방법
학습 주제.3
비선형 자료구조 - 힙
이진 트리 형태를 가지며, 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징
⚠️우선순위 큐 != 힙
FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐 개념을 가짐
우선순위 큐는 자료구조가 아닌 개념이다.
힙의 특징
- 우선순위가 높은 요소가 먼저 나가는 특징을 가진다
- 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.
- 자바스크립트에서는 힙을 직접 구현해서 사용해야 한다.
힙 요소 추가 알고리즘
- 요소가 추가될 때 트리의 가장 마지막에 정점에 위치한다.
- 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다
- 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
- 완전 이진 트리의 높이는 log N이기에 힙의 요소 추가 알고리즘은 O(log N) 시간복잡도를 가진다.
// 힙 요소 추가 로직
class MaxHeap {
constructor() {
this.heap = [null];
}
push(value) {
this.heap.push(value);
let currentIndex = this.heap.length - 1;
let parentIndex = math.floor(currentIndex / 2);
while (parentIndex !== 0 && this.heap[parentIndex] < value) {
const temp = this.heap[parentIndex];
this.heap[parentIndex] = value;
this.heap[currentIndex] = temp;
currentIndex = parentIndex;
parentIndex = math.floor(currentIndex / 2);
}
}
}
힙 요소 제거 알고리즘
- 요소 제거는 루트 정점만 가능
- 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치
- 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
- 두 자식 정점이 우선순위가 더 낮을 때까지 반복
- 완전 이진 트리의 높이는 log N이기에 힙의 요소 제거 알고리즘은 O(log N) 시간복잡도를 가진다.
// 힙 요소 제거 로직
class MaxHeap {
constructor() {
this.heap = [null];
}
pop() {
const returnValue = this.heap[1];
this.heap[1] = this.heap.pop();
let currentIndex = 1;
let leftIndex = 2;
let rightIndex = 3;
while ( this.heap[currentIndex] < this.heap[leftIndex] || this.heap[currentIndex] < this.heap[rightIndex] ){
if (this.heap[leftIndex] < this.heap[rightIndex]) {
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[rightIndex];
this.heap[rightIndex] = temp;
currentIndex = rightIndex;
} else {
const temp = this.heap[currentIndex];
this.heap[currentIndex] = this.heap[leftIndex];
this.heap[leftIndex] = temp;
currentIndex = leftIndex;
}
leftIndex = currentIndex * 2;
rightIndex = currentIndex * 2 + 1;
}
return returnValue;
}
}
주요 메모 사항 소개
해시 테이블(Hash Table)
키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
그래프(Graph)
방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조
이진 트리 (Binary Tree)
이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미
힙(Heap)
이진 트리 형태를 가지며, 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징
공부하면서 어려웠던 내용
비선형 자료구조 실습
처음 비선형 자료구조를 처음 접하면서 "열심히 공부해야지!" 하고 이번에 배운 비선형 자료구조를 가지고 실습 문제를 풀었을 때, 그 막막함과 멍해지는 감각... 배운건데 문제로 풀어 나오니까 마치 내가 배운것들을 숨겨놓은 기분이였다. 코드로 풀이하니 문제해결능력이 길러야 자료구조도 생각이 나고 활용이 된다 그랬는데, 보이지 않으니 풀지를 못하는... 이론은 공부한다고 되는것이 아니라 실전도 해보고 자꾸 샘플코드도 만들어보고 해야겠구나 싶었다..