🤔들어가며
데브코스 교육이 벌써 2주차가 끝났다. 뭐 이번주는 추석 연휴가 있어 3일이였지만 그렇다고 쉽다고 생각했던 3일은 아니였다.
2주차에는 문법보단 개발자에 있어 기본적인 자료구조와 알고리즘에 대해 배운 주차였다.
대학교에서 대부분 선행학습을 한 내용들이였지만 내가 제일 어려워했던 파트였기도 했다. 그래서 다시 정리하며 더 탄탄하게 지식을 가져가는 느낌이였다.
✅ JavaScript 주요 문법(4) 9.25
큐(Queue)
현재까지 자바스크립트에서 큐를 사용할때 나는 그냥 배열에 지원해주는 push(), shift()로 큐를 사용했었다.
하지만 shift()함수가 시간이 오래걸린다만 알았지 선형시간 O(n) 정도인지는 몰랐던 사실이다.
알고리즘 문제를 풀면서 데이터 조건이 커지면 shift()사용이 꺼져렸는데 이제부터는 큐를 따로 구현하여 더 효율적할 수 있을거 같다.
해시 테이블(Hash Table)
해시 테이블을 구현할때 Object로만 구현했는데 이번에 Map, Set 객체에 대해 알게 되었다.
사실 Set 객체는 중복을 제거하여 리스트를 만들때 사용해봤지만 Map은 처음 알게 되었다.
일반 Object로 구현하는 것 보다 Map을 활용하면 더 좋은 메서드를 통해 편리하게 객체를 관리할 수 있다.
그래프(Graph)
그래프는 관련된 문제를 많이 풀어봐서 쉽게 이해했다.
그래프를 이해하는것도 중요하지만 그래프를 활용한 알고리즘을 이해하는게 더 중요하다고 생각한다. 많이 어렵기도하고 종류도 다양해서..
✅ JavaScript 주요 문법(4) 9.25
트리
정말 오랜만에 마주하는 트리다. 대학교 2학년 때 처음 배웠던 내용인데 당시 지식으로는 완전 새로운 개념을 배우는듯한 느낌이여서 정말 어렵던 경험이 있었다.
그래도 트리 순회를 구현하면서 트리에 대해 탄탄하게 알고가는 것 같다.
힙(heap)
알고리즘 문제를 풀면서 Heap에 대해 공부한 경험이 있다. 큐의 우선순위를 통해 enqueue해야하거나 다익스트라 알고리즘을 사용하거나
이때마다 생각한것이 아! 힙과 우선순위 큐가 같구나라고 생각하고 있었는데 강사님께서 신기하게도 힙과 우선순위 큐를 같다고 생각하시는 분이 많은데 이건 다르다! 라고 말해주셨다.
우선순위 큐는 그냥 개념일 뿐이며 힙을 통해 구현하는 것 뿐이라고.. 정말 신기하게 쪽 집어서 알려주시는 것 같다..
트라이
트라이는 처음 접해본 자료구조 방식이였다. 그래도 그렇게 이해하기 어려운 개념은 아니여서 금방 이해했다.
또한 인터넷 서비스에서 자동완성 기능이 어떻게 이루어지는지 구조에 대해 이해를 하게 되었으며 그 자동
완성 기능을 작게나마 구현할 수 있는 기회가 되어 정말 좋았다.
정렬(Sort)
정렬은 요소들을 일정한 순서대로 열거하는 알고리즘이다.
정렬의 특징
- 정렬의 기준은 사용자가 정할 수 있다.
- 크게 비교식과 분산식 정렬로 나눌 수 있다.
- 대부분의 언어가 빌트인으로 제공해준다.
- 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬이 방식이 존재한다.
비교식 정렬 : 다른 요소와 비교를 통해 정렬을 함
- 버블 정렬 : 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘 O(n2) 시간 복잡도를 가진다.
- 선택 정렬 : 선택한 요소와 가장 우선순위가 높은 요소를 교호나하는 정렬 알고리즘 O(n2) 시간 복잡도를 가진다.
- 삽입 정렬 : 선택한 요소를 삽입 할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘 O(n2) 시간 복잡도를 가진다.
분산식 정렬 : 요소를 분삭하여 정렬하는 방식
- 분할 정복 : 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략, 다양한 알고리즘에 응용된다.
- 합병 정렬 : 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘 O(nlogn) 시간 복잡도를 가진다.
- 퀵 정렬 : 분할 정복 알고리즘을 이욯나 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬 O(nlogn) 시간 복잡도를 가진다.
이진 탐색
✅ JavaScript 주요 문법(4) 9.25
BFS, DFS
너비 우선 탐색(BFS) : 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘
BFS 특징
- Queue를 이용하여 구현
- 시작 지점에서 가까운 정점부터 탐색한다.
- V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V + E)다.
깊이 우선 탐색(DFS) : 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘
DFS의 특징
- Stack을 이용하여 구현
- 시작 정점에서 깊은 것 부터 찾는다.
- V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V + E)다.
그리디
그리디 : 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘, 최적해를 보장해주지 않는다.
그리디 알고리즘 특징
- 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.
- 크루스칼, 다익스트라 알고리즘 등에 사용된다.
- 직관적인 문제 풀이에 적합하다.
🥱마치며
두 번째 주는 정말 자료구조와 알고리즘이 주가 되었다.
정말 몇 개월 전만 해도 제일 자신 없고 막막했던 부분이였는데 알고리즘 문제를 꾸준히 풀면서 개념을 이해하고 응용했던 경험때문인지 이제는 새롭지 않고 몰랐던 부분을 더 자세히 알게되는 경험을 얻는것 같다.
그래도 아직 부족하니 피하지말고 꾸준히 마주하여 더 좋은 경험을 얻도록 노력해야겠다.
