[Day 5] JavaScript 주요 문법 (5)

---

 

💡 실습 문제 - 가장 먼 노드

[프로그래머스] 가장 먼 노드(JavaScirpt) (tistory.com)

[프로그래머스] 가장 먼 노드(JavaScirpt)

 

자료구조&알고리즘 - 트리

 

1. 트리

- 방향 그래프의 일종으로 정점으로 가르키는 간선이 하나 밖에 없는 구조

 

1) 용어

• Degree(차수) : 한 정점에서 나오는 간선의 개수
• Level : 루트부터 리프노드까지 단계(루트가 0,1로 시작하여 커진다)

2) 특징

• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모를 가진다
• 정점이 n개인 트리는 반드시 n-1개의 간선을 가진다
• 루트에서 특정 정점으로 가는 경로는 유일하다

2. 이진트리

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

 

1) 종류

• 완전이진트리 : 마지막 레벨을 제외하고 각 노드들이 자식 노드가 2개씩 가지고 있는 트리
• 포화 이진트리 : 리프노드를 제외한 모든 노드가 자식 노드가 2개
• 편향 이진트리 : 편향된 트리

2) 특징

• 정점이 n개일 때 최악의 경우 높이가 n(편향이진트리)
• 정점이 n개인 포화/이진 트리의 높이는 logN
• 높이가 h인 포화 이진트리는 2^h-1개의 정점을 가진다

 

 

3. 트리 구현 방법

1) 인접 행렬

// left = index * 2
// right = index * 2 + 1;
// parent = index / 2

const tree = [ undefined, 1 , 2, 3, 4, 5, 6, 7 8, 9 ];

각 배열의 인덱스가 노드의 인덱스가 되어 값을 넣어주면 된다. 

 

2) 인접 리스트

class Node {
  constructor(value){
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class Tree {
  constructor(node){
    this.root = node;
  }

  display() {
    const queue = new Queue();
    queue.enqueue(this.root);
    while(queue.size){
      const currentNode = queue.dequeue();
      console.log(currentNode.value);
      if(currentNode.left) queue.enqueue(currentNode.left);
      if(currentNode.right) queue.enqueue(currentNode.right);
    }
  }
}

 

💡 과제 - 전위, 중위, 후위 순회 구현

 

 

 

 

자료구조&알고리즘 - 힙

 

1. 우선순위 큐

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

* 우선순위는 자료구조가 아닌 개념

 

1) 힙

- 이진 트리 형태를 가지고 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬됨

• 이 때 부모와 자식 노드의 대소관계만 중요하며 형제 노드들간에는 관계가 없다

✅ 우선순위 큐 != 힙

출처 : TWpower's Tech Blog

 

ⓐ 특징

• 우선순위가 높은 요소가 먼저 나감
• 루트가 가장 큰 값이 되는 최대 힙, 루트가 가장 작은 값이 되는 최소 힙 존재
• 자바스크립트에 내장되어 있지 않음

ⓑ 요소 추가

• 요소가 추가 될 때 트리의 가장 마지막 정점에 위치
• 추가 후 부모보다 우선순위가 높다면 부모와 순서를 바꾼다
• 이진 트리의 높이가 log n 이기에 추가 알고리즘은 log n이 된다

ⓒ 요소 제거

• 요소 제거는 루트 정점만 가능
• 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치
• 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 교환
• 두 자식 정점이 우선순위가 낮을 때 까지 반복
• 시간복잡도는 log N

 

 

2. 자바스크립트에서 구현

* 강의에선 최대 힙을 구현하였으므로 최소 힙을 구현하였음

class MinHeap {
  constructor(){
    this.heap = [null];
  }

  push(value){
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex/2);

    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 returnValue = this.heap[1]; // 루트
    this.heap[1] = this.heap.pop();

    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    
    // 현재 노드보다 자식노드의 우선순위가 더 높을 때 종료
    while (this.heap[currentIndex] > this.heap[leftIndex] || this.heap[currentIndex] > this.heap[rightIndex]){
      if(this.heap[leftIndex] < this.heap[rightIndex]){
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex *2 + 1;
    }

    return returnValue;
  }
}

 

자료구조&알고리즘 - 트라이

 

1. 트라이

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

 

1) 특징

• 검색어 자동완성, 사전 찾기 등에 활용 가능
• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적
• 문자열의 길이만큼 탐색/삽입 시간복잡도가 걸린다
• 하지만 저장공간을 좀 더 많이 차지함

2) 구조

• 루트는 비어있음
• 각 간선은 추가될 문자를 키로 가짐
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다
• 해시 테이블과 연결 리스트를 통해 구현 가능

class Node {
  constructor(value = ""){
    this.value = value;
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(string){
    let currentNode = this.root;

    for(const char of string){
      if(!currentNode.children.has(char)){
        // 없는 문자라면
        currentNode.children.set(char, new Node(currentNode.value + char));
      }
      currentNode = currentNode.children.get(char);
    }
  }

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

 

💡 과제 - 자동완성 코드 구현

 

 

 

자료구조&알고리즘 - 정렬

 

1. 정렬

- 요소를 일정한 순서대로 열거하는 방법

 

1) 비교식 정렬

- 다른 요소와 비교하는 방식으로 정렬하는 방법

 

ⓐ 버블 정렬

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

- 시간복잡도 : O(N^2)

 

ⓑ 선택 정렬

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

- 시간복잡도 : O(N^2)

 

ⓒ 삽입 정렬

- 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 알고리즘

- 시간복잡도 : O(N^2)

 

2) 분산식 정렬

- 요소를 분산하여 정렬하는 방식

- 분할 정복 : 문제를 작은 2개의 문제를 분리하고 더 이상 분리가 불가능 할 때 처리하고 합치는 전략

 

ⓐ 합병 정렬

- 분할 정복 알고리즘을 이용한 최선과 최악이 같은 알고리즘 

- 시간 복잡도 : O(nlogn)

 

ⓑ 퀵 정렬

- 분할 정복 알고리즘을 이용한 최악이 존재하는 불안정 정렬

- 시간복잡도 : O(nlogn) ~ O(n^2)

 

 

2. 자바스크립트 정렬

const array = [ 1 ,4, 5, 6, 2, 5, 3 ];

array.sort(); // 자바스크립트 sort()는 아스키 코드값 기준으로 정렬

array.sort((a,b) => a - b); // 오름차순 정렬 
array.sort((a,b) => b - a); // 내림차순 정렬

+ MDN 

 arr.sort([compareFunction])

• compareFunction(a, b)이 음수일 경우 a를 b보다 낮은 색인으로 정렬합니다. (A, B)
• compareFunction(a, b)이 0일 경우 a와 b를 서로에 대해 변경하지 않고 모든 다른 요소에 대해 정렬합니다. 
• compareFunction(a, b)이 양수일 경우, b를 a보다 낮은 인덱스로 소트합니다.
• compareFunction(a, b)은 요소 a와 b의 특정 쌍이 두 개의 인수로 주어질 때 항상 동일한 값을 반환해야합니다. 일치하지 않는 결과가 반환되면 정렬 순서는 정의되지 않습니다.

 

💡 실습 문제 - 가장 큰 수

[프로그래머스] 가장 큰 수 (JavaScript) (tistory.com)

[프로그래머스] 가장 큰 수 (JavaScript)

 

 

 

자료구조&알고리즘 - 이진 탐색

 

1. 선형 탐색

: 순서대로 하나씩 찾는 탐색 알고리즘 - O(n)

 

2. 이진 탐색

: 정렬되어 있는 요소들을 반씩 제외하며 찾는 알고리즘 - O(log n)

 

1) 특징

• 반드시 정렬
• 배열/이진트리로 구현 가능

2) 구현

ⓐ 배열

- 중앙값을 피벗으로 정한다

- 피벗과 찾으려는 값과 비교한다.

- 만약 찾으려는 값이 피벗보다 작으면 피벗보다 왼쪽배열에서, 크면 오른쪽배열에서 재탐색한다.

- 목표값을 찾을 때까지 위 과정을 반복한다.

* 요소 추가/삭제에 선형 시간이 걸리는 단점이 있음

 

const array = [1,1,4,124,300,580,980,2000,4999];

function binarySerach(array, findValue){
  let left = 0;
  let right = array.length -1;
  
  while(left<=right){
    let mid = Math.floor((left+right)/2);
    if(array[mid] <findValue){
      left = mid +1;
    }else if(array[mid] > findValue){
      right = mid -1;
    }else {
      return mid;
    }
  }

  return -1;
}

console.log(binarySerach(array, 4999));
console.log(binarySerach(array, 125));

 

 

ⓑ 이진 탐색 트리

- 왼쪽 서브트리 < 루트 노드 < 오른쪽 서브트리

 

1) 이원 탐색 트리에서의 검색(키 값 K)

- 트리가 공백 : 검색은 노드를 찾지 못하고 실패

- K = Ki : 노드 Ni가 원하는 노드

- K < Ki : 루트의 왼쪽 서브트리를 검색

- K > Ki : 루트의 오른쪽 서브트리를 검색

 

2) 이원 탐색 트리에서의 삽입

- 트리가 공백 : K를 루트 노드로 삽입

- K = Ki : 트리에 같은 키 값이 존재하므로 삽입 거부

- K < Ki : 루트의 왼쪽 서브트리로 이동하여 계속 탐색

- K > Ki : 루트의 오른쪽 서브트리로 이동하여 계속 탐색

 

3) 이원 탐색 트리에서의 삭제

- 삭제 노드가 가진 자식 수에 따른 삭제 연산

① 자식이 없으면 단순히 그 노드 삭제

② 자식이 1개면 삭제되는 노드에 자식 노드 위치

③ 자식이 2개면 왼쪽 서브트리에서 가장 큰 키 값/ 오른쪽 서브트리에서 가장 작은 값으로 대체 선택하여 삭제

 

4) 이원 탐색트리의 성능

ⓐ 편향 이원 탐색트리 : 리프 노드의 탐색 시간은 최악

* n개의 노드인 이원 탐색 트리에서의 최악의 탐색 시간은 n의 노드 탐색

ⓑ 우수한 성능이 되기 위한 조건

- 가장 자주 접근되는 노드는 루트에 가장 가까이 유지함

- 트리가 균형 트리가 되도록 함

ⓒ 이원 탐색 트리의 단점

- 삽입, 삭제 후 효율적 접근을 위한 균형 유지 부담

- 작은 분기율에 따른 긴 탐색 경로와 검색 시간

class Node {
  constructor(value){
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class Tree {
  constructor(node){
    this.root = node;
  }

  // 삽입
  insert(value) {
    const newNode = new Node(value);
    
    // 루트가 비어있다면
    if(this.root === null) {
      this.root = newNode;
      return;
    }

    let currentNode = this.root;
    while(currentNode !== null){
      // 삽입 노드가 현재 노드보다 크면 
      if(currentNode.value < value){
        // 현재 노드의 오른쪽 자식노드가 비어 있다면
        if(currentNode.right === null) {
          currentNode.right = newNode;
          break;
        }
        // 비어있지않다면 오른쪽 서브트리 탐색
        currentNode = currentNode.right;
      }
      // 삽입 노드가 현재 노드보다 작다면 
      else {
        if(currentNode.left === null) {
          currentNode.left = newNode;
          break;
        }
        currentNode = currentNode.left;
      }
    }
  }

  // 탐색
  has(value){
    let currentNode = this.root;
    while(currentNode !== null){
      if(currentNode.value === value){
        return true;
      }
      if(currentNode.value < value) {
        // 탐색 노드가 더 크면 오른쪽 서브트리 탐색
        currentNode = currentNode.right;
      }else {
        // 왼쪽 서브트리 탐색
        currentNode = currentNode.left;
      }
    }
    return false;
  }
}

 

💡 실습 - 입국심사

[프로그래머스] 입국심사 (Javascript) (tistory.com)

[프로그래머스] 입국심사 (Javascript)