오늘 공부한 내용 💻
- [실습] 가장 먼 노드
- 자료구조 & 알고리즘 - 트리
- 자료구조 & 알고리즘 - 힙
- 자료구조 & 알고리즘 - 트라이
- 자료구조 & 알고리즘 - 정렬
- [실습] 가장 큰 수
- 자료구조 & 알고리즘 - 이진 탐색
- [실습] 입국심사
어려웠던 내용 🤢
우선순위 큐(Priority Queue)
- 우선순위 큐란?
일반적인 큐와는 다르게 우선순위가 높은 요소가 먼저 나가는 큐. - ※ 주의 ※
우선순위 큐는 자료구조가 아닌 개념으로 자료구조를 통해 구현할 수 있다.
힙(Heap)
-
이진 트리 형태를 가지며, 우선순위 큐를 구현하기 좋음.
-
우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입/삭제 될때 바로 정렬되는 특징이 있다.
-
힙(Heap)의 특징
- 우선순위가 높은 요소가 먼저 나가는 특징을 가진다.
- 루트가 가장 큰 값을 가지는 힙 : 최대 힙(Max Heap)
- 루트가 가장 작은 값을 가지는 힙 : 최소 힙(Min Heap)
트라이(Trie)
-
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태 자료구조.
-
트라이(Trie)의 특징
- 검색어 자동완성, 사전찾기 등에 응용될 수 있다.
- 문자열을 탐색할 때 단순하게 비교하는 것 보다 효율적으로 찾을 수 있다.
- L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
- 각 정점이 자식에 대한 링크를 전부 가지고 있기 때문에 저장 공간을 더 많이 사용한다.
-
트라이(Trie)의 구조
- 루트(root)는 비어있다.
- 각 간선은 추가될 문자를 키로 가진다.
- 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.
더 공부할 내용 📃
- [실습] 입국심사 다시 풀어보기
- 트리 - 전위 순회, 중위 순회, 후위 순회 구현
- 트라이- 검색어 자동 완성 기능 구현
느낀점 👀
> '🤪'
계속해서 자료구조&알고리즘 수업 !
과제에 필요한 개념을 배우는 날인 만큼 강의를 몇 번이나 돌려봤다 !
그래서 그런지 살짝 과부하가 왔다 ㅎㅎ
트라이나 힙에 대해서는 이번에 새롭게 알게 되어서 몇 번 더 보면서 직접 구현을 해봐야 익숙해질듯.
정렬은 항상 지원해주는 기능을 쓰기만 해서 구체적인 내용은 잘 몰랐는데, 종류나 특징에 대해서 알게 되어서 의미 있었던 수업!
참고 사이트 🙄
Studying FrontEnd Development