Map() 자료구조로 저장 - key는 간선으로 문자열(char), value는 해당 Node
트라이를 이용한 자동완성 코드 구현 (과제)
hint: 트리파트의 레벨 순회 응용
trie에 있는 String: "str", "string", "star"
자동완성("st") 하면
출력: ["str", "string", "star"]
13. 정렬
정렬의 특징
정렬 기준은 사용자가 정한다. (오름차순, 내림차순)
비교식 정렬, 분산식 정렬로 나뉜다
삽입, 선택, 버블, 머지 ,힙, 퀵 정렬등 다양한 정렬 방식 존재
가장빠른 정렬
각각의 상황에 따라 다르다.
정렬알고리즘 종류
비교식정렬
1.버블정렬 (O(n^2))
서로 인접한 두 요소를 검사하는 정렬 알고리즘
n번 순회를 n-1번 수행
2.선택정렬(O(n^2)
선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘
3.삽입정렬(O(n^2))
선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 정렬 알고리즘
어느정도 정렬이 되어 있다는 것이 보장 되면 퀵정렬 보다 빠르게 작동
분산식정렬
핵심 아이디어
분할 정복
4.합병정렬(O(n * logn))
분할 정복 알고리즘을 이용한 정석적인 정렬 알고리즘
최선과 최악이 같은 안정적인 정렬 알고리즘
Divide & Conquer 방식
5.퀵 정렬(O(n * logn))
분할 정복알고리즘을 이용하여 빠르지만, 최악의 경우가 존재하는 불안정 정렬
pivot을 이용한 정렬
14. 이진 탐색 (Binary Search)
↔ 선형탐색 :순차적으로 찾는 방법
이진탐색은 요소들이 정렬되어 있을 때,
이진탐색 특징
반드시 정렬이 사전에 되어있어야한다.
O(log n) 으로 상당히 빠른 시간복잡도를 가진다.
배열과 이진트리를 이용하여 구현
배열을 이용한 구현
mid (left + right)/2 값을 통해 찾기
중간 요소 탐색 시 선형시간(O(n))이 걸리는 단점 → 이진탐색트리로 구현
이진탐색트리를 통한 구현
이진트리에서 하나의 규칙(정점을 기준으로 왼쪽 서브트리는 작은 값, 오른쪽 서브트리는 큰 값을 가진다)을 추가한 자료구조
하나의 서브 트리를 가지는 경우
두개의 서브 트리를 가지는 경우
문제점
최악의 경우 한쪽으로 편향된 트리가 될 수 있다.
js에서의 구현 (by 배열)
js에서의 구현 (by BST)
실습(입국심사)
O(n^2) 으로 효율성 실패
대주제
자료구조
작성완료
작성완료
전날 정리 노트 이동
다음 정리 노트 이동
주제
트리와 힙
트라이 자료구조
정렬
이진탐색
날짜
Mar 25, 2022
class MaxHeap(){
constructor(){
this.heap = [null] // 0번 idx 관리 쉽게 비어준다.
}
// 제일 뒤에 들어오고, 부모랑 비교&교체 반복
push(value){
this.heap.push(value);
let currentIndex = this.heap.length - 1; // 추가된 요소의 idx
let parentIndex = Math.floor(currentIndex / 2);
// 부모값이 작으면 교체, 정점(parentIndex = 0)까지 반복
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) // 부모위치도 바뀐 현재위치에 따라 변경
}
}
// 부모요소 제거 후, 마지막 정점 부모로 이동
// 정점이 각 자식과 비교하여, 현재노드가 자식노드 보다 작을 경우 교체 반복
pop(){
const currentIndex = this.heap.length -1;
const temp = this.heap
this.heap.[1] = this.heap
const
}
// 부모요소 제거 후, 마지막 정점 부모로 이동
// 정점이 각 자식과 비교하여, 현재노드가 자식노드 보다 작을 경우 교체 반복
pop() {
const returnValue = this.heap[1];
this.heap[1] = this.heap.pop();
console.log(returnValue, this.heap);
let currentIdx = 1;
let leftIdx = 2; //Math.floor(currentIndex / 2);
let rightIdx = 3; // leftIdx + 1;
while (
this.heap[currentIdx] < this.heap[leftIdx] ||
this.heap[currentIdx] < this.heap[rightIdx]
) {
// 왼쪽자식 오른쪽 자식과의 비교 (현재요소는 둘 중 하나보다 무조건 작음이 판정)
if (this.heap[leftIdx] < this.heap[rightIdx]) {
const temp = this.heap[currentIdx];
this.heap[currentIdx] = this.heap[rightIdx];
this.heap[rightIdx] = temp;
currentIdx = rightIdx;
} else {
const temp = this.heap[currentIdx];
this.heap[currentIdx] = this.heap[leftIdx];
this.heap[leftIdx] = temp;
currentIdx = leftIdx;
}
leftIdx = currentIdx * 2;
rightIdx = currentIdx * 2 + 1;
}
console.log(this.heap);
return returnValue;
}
// 각 노드는 모든 자식 요소를 연결리스트 키-값으로 가지고 있는다. (Map)
class Node {
constructor(value = "") {
this.value = value;
this.children = new Map(); // key-value (char-node)
}
}
class Trie {
constructor() {
this.root = new Node();
}
// 해당 string이 분해되어 노드형식으로 저장이 된다.
// 루트부터 시작하여, 타고 내려간다.
insert(string) {
let currentNode = this.root;
for (const char of string) {
if (currentNode.children.has(char)) {
currentNode = currentNode.children.get(char);
} else {
currentNode.children.set(char, new Node(currentNode.value + char));
currentNode = currentNode.children.get(char);
}
}
}
// 현재 트라이가 해당 string을 가지고 있는지 판별한다.
has(string) {
let currentNode = this.root;
for (const char of string) {
if (!currentNode.children.has(char)) {
return false;
}
currentNode = currentNode.children.get(char);
}
return true;
}
}
const array = [];
find
function solution(n, times) {
var answer = 0;
// [0,0,7,10, 14, 20, 21 ,28, 30]
let t = [];
for(let i = 1; i <= n; i++){
times.forEach(time => t.push(time * i))
}
return t.sort((a,b)=> a-b)[n-1]
}
