Day 5 - 2022/10/21
💡 새롭게 알게된 점
자료구조와 알고리즘
트리
트리는 정점이 가리키는 간선이 하나 밖에 없는 방향 그래프의 일종이다.
가장 상위의 노드를 root, 각 정점을 node, 자식이 없는 node를 leaf node라 칭함.
루트로부터 몇번째 깊이 인지를 level이라고 한다. (root는 level 1)
한 정점에서 뻗어나가는 간선의 수를 degree 혹은 차수라고 부른다.
트리의 특징을 알아보자!
root를 제외한 모든 정점은 반드시 하나의 부모를 가진다.
정점이 N개인 트리는 반드시 N-1개의 간선을 가진다. 모든 정점이 하나의 부모를 가지기 때문
루트에서 특정 정점으로 가는 경로는 유일하다. 마찬가지로 하나의 부모를 가지기 때문
트리의 종류는 무엇이 있을까?
이진 트리
이진 트리는 각 정점이 최대 2개의 자식을 가지는 트리이다.
탐색을 위한 알고리즘에 많이 쓰인다.
완전 이진 트리
마지막 레벨을 제외하고 모든 정점이 채워져 있는 트리
포화 이진 트리
모든 정점이 채워져있는 트리
편향 트리
한 방향으로만 정점이 이어지는 트리
이진 트리의 특징은 무엇이 있을까?
정점이 N개인 이진 트리는 최악의 경우 높이가 N. 즉, N개의 정점을 가진 편향 트리
정점이 N개인 포화 또는 완전 이진 트리의 경우 높이가 logN. 레벨이 증가함에 따라 두 배씩 정점이 생기기 때문
높이가 h인 포화 이진 트리의 경우 정점이 2^h - 1 개. (ex: 이진법)
자바스크립트에서 트리를 구현해보자!
그래프의 일종인 트리는 그래프와 동일하게 인접 행렬, 인접 리스트로 구현할 수 있음!
- 인접 행렬
Index * 2는 왼쪽 정점, Index * 2 + 1은 오른쪽 정점이 된다.
Math.floor(Index / 2)는 부모 정점
- 연결 리스트
기존 연결 리스트 노드의 next 대신 left와 right
계속해서 left와 right를 연결
힙
우선순위 큐를 구현하기 위한 가장 적합한 방법이다.
우선순위 큐가 뭔데?
우선순위 큐는 FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐이다.
자료구조가 아닌 개념이기 때문에 구현 방법이 다양하다.
힙은 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬된다.
그럼 우선순위 큐와 힙은 같은 건가요?
Nope! 매번 배열을 우선 순위에 따라 정렬한다면 역시 우선 순위 큐가 될 수 있다. 하지만 힙보다 효율이 좋지 않음.
힙의 특징을 알아보자!
힙은 우선 순위가 높은 요소가 먼저 나간다.
루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 가장 작은 값이 되는 최소 힙(Min Heap)이 있다.
JS엔 없기 때문에 직접 구현해야함..
힙에 요소를 추가해보기
완전 이진 트리의 높이는 logN이기 때문에 힙에 요소를 추가하는 과정은 O(logN)의 시간 복잡도를 가진다.
- 추가할 때 이진 트리의 가장 마지막 정점에 추가
- 추가 후 부모보다 우선 순위가 높다면 부모와 교체
- 1-2 과정 반복
힙에서 요소를 삭제해보기
요소 추가와 마찬가지로 완전 이진 트리의 높이는 logN이기 때문에 힙에서 요소를 삭제하는 과정은 O(logN)의 시간 복잡도를 가진다.
- 삭제할 때 이진 트리의 루트에서 삭제
- 마지막 정점을 루트로 이동
- 루트의 자식 중 우선 순위가 높은 정점과 교체
- 반복
트라이
트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
한 정점이 이전 정점으로부터 더해진 문자열 정보를 저장한다.
트라이의 특징을 알아보자!
검색어 자동완성, 사전 찾기 등에 응용 가능
문자열 탐색 시 단순 비교보다 효율적임
탐색, 삽입의 과정이 O(문자열의 길이)만큼 소요됨
대신 각 정점이 자식에 대한 링크를 전부 가지고 있기 때문에 공간 복잡도는 증가한다는 단점
트라이 구조
- 루트는 비어 있는 공백
- 각 간선(링크)는 추가될 문자를 키로 가짐
- 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가짐
자바스크립트에서 트라이를 구현해보자!
트리 구조인 만큼 그래프처럼 (인접 리스트 형태의) 노드가 필요함
- 트라이 생성 시 root로 빈 노드 생성
- 문자열을 추가 시
- root로부터 시작하여 문자열을 앞에서부터 하나씩 자르며 현재 노드에서 자른 문자열을 간선으로 가지고 있지 않다면 새 노드를 추가
- 다음 정점으로 이동
- 반복
정렬
어떤 정렬이 제일 빠를까?
퀵 정렬이나 합병 정렬이 제일 빠르다고 생각하지만, 각 정렬마다 최선의 경우와 최악의 경우가 다르기 때문에 무엇이 더 좋고 나쁜지는 정해져 있지 않다.
정렬의 종류는 무엇이 있을까?
비교식 정렬
버블 정렬
버블 정렬은 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘이다.
O(n^2)의 시간 복잡도를 가진다.
선택 정렬
선택 정렬은 선택한 요소와 나머지 요소 중 우선 순위가 가장 높은 요소를 교환하는 알고리즘이다.
O(n^2)의 시간 복잡도를 가진다.
삽입 정렬
삽입 정렬은 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 알고리즘이다.
O(n^2)의 시간 복잡도를 가진다.
두 번째 요소부터 시작한다.
어느 정도 정렬이 되어 있다면 퀵 정렬보다 빠른 성능을 가진다.
분산식 정렬
분할 정복
분할 정복은 문제를 작은 2개의 문제로 나눠 더 이상 분리가 불가능할 때 처리한 후 합치는 알고리즘이다.
합병 정렬
합병 정렬은 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘이다.
O(NlogN)의 시간 복잡도를 가진다.
퀵 정렬
퀵 정렬은 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정한 정렬 알고리즘이다.
O(NlogN)의 시간 복잡도를 가진다.
이진 탐색
이진 탐색은 사전에 정렬되어 있는 요소들을 반씩 제외하며 찾는 알고리즘이다.
O(logN)의 시간 복잡도를 가진다.
이진 탐색의 특징을 알아보자!
반드시 정렬되어 있어야 사용할 수 있다.
배열 혹은 이진 트리를 이용하여 구현할 수 있다.
정렬되어 있는 경우라면 선형 탐색보다 훨씬 빠르다. → 정렬이 되어 있지 않다면 선형 탐색보다 느릴 수 있다.
이진 탐색 트리
이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값, 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.
이진 탐색 트리의 문제점
최악의 경우 편향 트리가 될 수 있다.
편향 트리가 된 경우 순차 탐색과 동일한 시간 복잡도를 가진다.
이 경우 어떻게 해결할까?
AVL 트리
레드-블랙 트리
Array.prototype.shift()
javascript에 빌트인된 Array.prototype.pop()이 O(1)의 시간 복잡도를 가지는데에 비해 Array.prototype.shift()는 O(n)의 시간 복잡도를 가진다고 한다. 왜일까?
이는 제일 앞 원소를 제거 후 나머지 원소들을 앞으로 재정렬하는 과정이 필요하기 때문이다.
찾아보니 shift()와 pop()은 배열의 원소가 1000개 이하일 때 별 차이가 없다고 한다.
강의 중간에 shift()는 O(n)이지만 요소가 적을 경우에 자바스크립트 엔진에서 최적화를 해준다고 하셨는데, firefox의 경우 shift() 수행 시 요소를 움직이는 대신 포인터를 움직이거나 배열이 시작되는 곳의 새 주소를 컴퓨터에 알려준다고 한다.
그래서 firefox에서 shift() 수행 시 O(n) 대신 O(1)의 시간이 걸린다는데, 그러면 shift()를 남용해도 될까??
Nope! 비슷한 성능으로 모든 JS 런타임에서 실행할 수 있어야 하지만, js 엔진마다 다르다.
Chrome의 경우에도 이와 유사한 알고리즘이 있지만 50k 미만의 요소를 가진 배열에만 적용된다고 하니 큰 배열에서 shift()를 남발하는 일을 자제하도록 하자!
❗️ 느낀점
Array.prototype.shift()를 배열이 작을 때 애용하는 편이었는데, 오늘 강의 시간에 배열의 요소가 적을 경우 js 엔진에서 최적화를 해준다고 했다.
그래서 여러 엔진을 찾아봤는데 firefox의 js 엔진에서의 최적화 기법을 제외하고는 찾아볼 수 없었다..
이것 역시 나중에 다시 조사해보고, 다른 브라우저의 엔진에서의 최적화 기법의 유무와 왜 없는지를 찾아봐야겠다.
또한 v8을 찾아보던 중 v8에서 배열을 최적화 하는 법에 대해서 살짝 알게되었는데, 나중에 깊이 공부하고 블로그에 올려야겠다.
오늘도 고생했다👊