5일차 배운 것 정리 (1)

이전 내용

10.트리

방향그래프의 일종으로 정점이 가르키는 간선이 하나 밖에 없는 구조를 가진 비선형 자료구조

• 루트(Root)
• 트리의 최상단에 있는 노드를 가르킴

• 레벨(Level)
• 루트노드로 부터 해당 노드까지의 깊이

• 차수(degree)
• 한 정점에서 뻗어나가는 간선의 숫자

• 조직도

• 폴더구조

• 루트 노드를 제외한 모든 노드는 하나의 부모 노드를 가진다.

• 루트에서 특정 정점으로 가는 경로는 유일하다.

각 정점이 최대 2개의 자식을 가지는 트리를 의미

• 편향트리(최악의경우) N개의 노드에서 높이가 N이 될 수 있다.

• 정점이 N개일 때, 완전이진트리와 포화이진트리의 높이는 logN이다.

• 주로 이진트리를 활용하여 다른 자료구조로 응용된다.
• 이진탐색트리(BST)
• 힙(Heap)
• AVL트리
• 레드블랙트리

11. 힙(Heap)

FIFO인 큐와 달리 우선순위가 높은 요소가 먼저 나가는 큐

• 1.

• 2.

• 3. js에서는 직접 구현

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;
  }

12.트라이 (Trie)

문자열을 저장하고, 효율적으로 탐색하기 위한 트리형태의 자료구조

검색 서비스에서의 자동완성 기능 어떻게 구현?

→ 트라이

• 자동완성, 사전 찾기

• 문자열 탐색,삽입 시 효율적 (O(L:문자열길이))
• 단점: 정점이 자식에 대한 링크를 모두 가지고 있어야 해서 공간 많이 사용

// 각 노드는 모든 자식 요소를 연결리스트 키-값으로 가지고 있는다. (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;
  }
}

• hint: 트리파트의 레벨 순회 응용
trie에 있는 String: "str", "string", "star" 자동완성("st") 하면
1. 출력: ["str", "string", "star"]

13. 정렬

정렬의 특징

• 정렬 기준은 사용자가 정한다. (오름차순, 내림차순)

• 비교식 정렬, 분산식 정렬로 나뉜다

• 삽입, 선택, 버블, 머지 ,힙, 퀵 정렬등 다양한 정렬 방식 존재

• 각각의 상황에 따라 다르다.

정렬알고리즘 종류

비교식정렬

1.버블정렬 (O(n^2))

서로 인접한 두 요소를 검사하는 정렬 알고리즘

• n번 순회를 n-1번 수행

2.선택정렬(O(n^2)

선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘

 

3.삽입정렬(O(n^2))

선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 정렬 알고리즘

• 어느정도 정렬이 되어 있다는 것이 보장 되면 퀵정렬 보다 빠르게 작동

 

 

• 핵심 아이디어
분할 정복

분할 정복 알고리즘을 이용한 정석적인 정렬 알고리즘

• 최선과 최악이 같은 안정적인 정렬 알고리즘

• Divide & Conquer 방식

분할 정복알고리즘을 이용하여 빠르지만, 최악의 경우가 존재하는 불안정 정렬

• pivot을 이용한 정렬

14. 이진 탐색 (Binary Search)

이진탐색은 요소들이 정렬되어 있을 때,

• 반드시 정렬이 사전에 되어있어야한다.

• O(log n) 으로 상당히 빠른 시간복잡도를 가진다.

• 배열과 이진트리를 이용하여 구현

• mid (left + right)/2 값을 통해 찾기

• 중간 요소 탐색 시 선형시간(O(n))이 걸리는 단점 → 이진탐색트리로 구현

이진트리에서 하나의 규칙(정점을 기준으로 왼쪽 서브트리는 작은 값, 오른쪽 서브트리는 큰 값을 가진다)을 추가한 자료구조

const array = [];

find

실습(입국심사)

• O(n^2) 으로 효율성 실패

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]
}