자료구조 & 알고리즘
이진 트리(Array)
const tree = [
undefined,
9, // 1
3, 8, // 1*2, 1*2+1
2, 5, undefined, 7 // 2*2, 2*2+1, 3*2, 3*2+1
undefined, undefined, undefined, 4 // 4*2, 4*2+1, 5*2, 5*2+1
]0번 인덱스는 편의를 위해 비워둠
Left = Idex 2
Right = Index 2 + 1
Parent = floor(Index / 2)
이진 트리 순회 알고리즘
트리에 저장된 모든 값을 중복이나 빠짐없이 탐색할 때 사용
우선순위 큐
FIFO인 큐과 달리 우선 순위가 높은 요소가 먼저 나가는 큐
주의
우선순위 큐는 자료구조가 아닌 개념이다!!
우선순위 큐 != 힙
힙
우선순위 큐를 구현하기 위한 가장 적합한 방법
이진 트리 형태
우선순위가 높은 요소를 루트에 두기 위해 요소가 삽입, 삭제 될 때 바로 정렬
-
힙 요소 추가 알고리즘
순서대로 요소를 추가할 때 이진트리의 가장 마지막에 추가
요소가 추가되었다면 부모 노드보다 우선순위가 높은지 확인
추가된 요소의 우선순위가 더 높다면 부모와 순서를 바꿈
순서를 바꿀 수 없을 때까지 반복하면 결국 우선순위가 가장 높은 정점이 루트
요소는 항상 이진트리의 마지막에 추가되기 때문에 힙은 항상 완전이진트리
완전 이진 트리의 높이는 log N이기 때문에 최악의 경우에도 짧은 시간에 가능 -
힙 요소 제거 알고리즘
요소를 제거하는 것은 루트만 가능
루트가 제거되면 그 공백을 가장 마지막 정점이 대체
추가하는 것과는 반대로 루트로 부터 정점을 아래로 내림
루트 정점의 두 자식 중 우선순위가 높은 정점과 순서 바꿈
두 자식의 우선순위가 낮을 때까지 반복하면 결국 우선순위가 가장 높은 정점이 루트
완전 이진 트리의 높이는 log N이기 때문에 최악의 경우에도 짧은 시간에 가능
트라이
트리를 이용한 자료구조
검색서비스에서 자동완성, 사전 찾기 기능에 사용
문자열을 저장하고 효율적으로 탐색
구조
- 루트는 비어있다
- 각 간선은 추가될 문자를 키로 가짐
- 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가짐
- 해시테이블과 연결 리스트를 이용하여 구현
정렬
-
비교식 정렬 (다른 요소와 비교를 통해 정렬하는 방식)
- 버블 정렬 : 서로 인접한 두 요소를 검사하여 정렬
- 선택 정렬 : 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬
- 삽입 정렬 : 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬
-
분산식 정렬 (분할 정복 : 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할때 처리한 후 합치는 전략)
- 합병 정렬 : 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬
- 퀵 정렬 : 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬
이진 탐색
선형 탐색 : 순서대로 하나씩 찾는 탐색
이진 탐색 : 정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘 (Up&Down 게임)
- 특징
반드시 정렬
배열 혹은 이진트리로 구현
시간복잡도가 O(log n)으로 매우 빠름
이진 탐색 트리를 이용한 구현 방법
이진 트리에서 한가지 규칙을 추가
왼쪽 서브 트리는 루트보다 작은 값 오른쪽 서브 트리는 루트보다 큰 값
문제점
편향된 트리가 될 수 있다.
너비 우선 탐색 BFS
그래프 탐색 알고리즘, 같은 깊이에 해당하는 정점부터 탐색
-
큐 사용하여 구현
-
시작 지점에서 가까운 정점부터 탐색
레벨 순회 (ROOT-L-R)
깊이 우선 탐색 DFS
그래프 탐색 알고리즘, 최대한 깊은 정점부터 탐색
- 재귀적, 반복적(스택 사용) 방법으로 구현
- 시작 정점에서 깊은 것 부터 탐색
전위 순회 (ROOT-L-R)
중위 순회 (L-ROOT-R)
후위 순회 (L-R-ROOT)
오늘의 마무리
🖤 TIL에 핵심없이 배운 내용을 나열만 하는 것 같아 앞으로 중요한 내용 위주로 요약해서 포스팅하기로 마음먹었다!
🖤 하지만 아직 포스팅하지 못한 임시 글은 주저리주저리일 예정이다🤣
🖤 자료구조에 관한 내용들은 두고두고 복습하며 꾸준히 사용해봐야 내 것이 될 것 같다( 아직까진 거리 두기 중..! )
