230926 [Day6] JavaScript 주요 문법 (5)

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

 

 

• 방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조를 가지고 있다.
• 레벨 : 루트로부터 몇 번째 깊이인지 표현
• degree(차수) : 한 정점에서 뻗어나가는 간선의 수
• 특징
  • root 정점을 제외한 모든 정점은 하나의 부모 정점을 가지고 있다
  • 정점이 n개인 트리는 간선이 n-1개 → 하나의 부모 정점을 가지기 때문에
  • 루트에서 특정 정점으로 가는 경로는 유일하다 → 하나의 부모 정점을 가지기 때문에

 

이진트리

각 정점이 최대 2개의 자식을 가지는 트리이다. 주로 탐색할때 많이 쓰인다.

• 정점이 N개 →(최악의 경우) 높이(n개) ⇒ 편향트리
• 정점이 N개 →(포화 or 완전이진트리) 높이(logn) ⇒ 레벨이 올라갈수록 2배씩 정점이 생성
• 높이가 h인 포화 이진 트리 : (2^h)-1개의 정점
• 일반적인 이진트리를 사용하는 경우는 많지 않다. → 이진 탐색트리, 힙, AVL트리, 레드블랙트리 구현

 

트리의 구현 방법

• 인접 행렬
• 인접 리스트

=> 그래프와 구현방법이 같다.

 

이진트리의 구현 방법 

1차원 배열

index*2 -> 왼쪽 정점

index*2+1 -> 오른쪽 정점

부모 정점만 알고싶다면 index/2에 소수점 버리기

// 0번 인덱스는 편의를 위해 비워둔다.
// Left = Index * 2
// Right = Index * 2 + 1
// Parent = floor(Index / 2)
const tree = [
  undefined,
  9,
  3, 8,
  2, 5, undefined, 7
  undefined, undefined, undefined, 4

 

요소에 링크가 존재하는 연결 리스트로 구현

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();
      if (currentNode.left) queue.enqueue(currentNode.left);
      if (currentNode.right) queue.enqueue(currentNode.right);
    }
  }
}

 

전위, 중위, 후위, 레벨 순회

• 전위순회
  • 루트->왼쪽자식->오른쪽자식 순서
    ex) 1->2->4->5->3
• 중위순회
  • 왼쪽자식->루트->오른쪽자식 순서
    ex) 4->2->5->1->3
• 후위순회
  • 왼쪽자식->오른쪽자식->루트 순서
    ex) 4->5->2->3->1
• 레벨순회
  • 맨위의 레벨부터 왼쪽에서 오른쪽으로 탐색
    ex) 1->2->3->4->5

 

 

자료구조&알고리즘 - 힙

우선순위 큐

• FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐
• 자료구조가 아닌 개념이여서 다양하게 구현할수 있는데 이걸 활용해서 heap 자료구조를 구현한 것이다.

 

힙

• 이진트리 형태이고 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될때 바로 정렬되는 자료구조
• 특징
  • 우선순위가 높은 요소부터 먼저 나가는 특징
  • root가 가장 큰 값 or 작은 값 : 최대 힙 / 최소 힙
  • js는 직접 구현

 

 동작원리

• 힙 요소 추가 알고리즘
  • 요소가 추가될 때는 트리의 가장 마지막에 정점에 위치한다.
  • 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
  • 이 과정을 반복하면 결국 가장 우선순위가 높은 정점이 루트가 된다.
  • 완전 이진 트리의 높이는 log N이기에 힙의 요소 추가 알고리즘은 O(log N) 시간복잡도를 가진다.

 

• 힙 요소 제거 알고리즘
  • 요소 제거는 루트 정점만 가능하다.
  • 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
  • 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
  • 두 자식 정점이 우선순위가 더 낮을 때까지 반복한다.
  • 완전 이진 트리의 높이는 log N이기에 힙의 요소 제거 알고리즘은 O(log N) 시간 복잡도를 가진다.

 

//내부적으로 관리할 배열, 0번 인덱스는 null
class MaxHeap {
  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];
    const.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.haep[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      //바꾼 정점에서 왼쪽 정점의 위치와 오른쪽 정점의 위치를 구한다.
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
    
    return returnValue;
  }
}

const heap = new MaxHeap();
heap.push(45);
heap.push(36);
heap.push(54);
heap.push(27);
heap.push(63);
console.log(heap.heap);
// [null, 63, 54, 45, 27, 36]


const array=[];
array.push(heap.pop()); //63
array.push(heap.pop()); //54
array.push(heap.pop()); //45
array.push(heap.pop()); //36
array.push(heap.pop()); //27
console.log(array);
// [63, 54, 45, 36, 27]

 

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

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

• 간선(키):이전 정점으로부터 새롭게 추가되는 문자 정보
• 정점(자식):이전 정점으로부터 더해진 문자 정보

 

트라이의 특징

• 검색어 자동완성, 사전 찾기 등에 응용될 수 있다.
• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
• 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용한다.

 

트라이 구조

• 루트는 비어있다.
• 각 간선(링크)은 추가될 문자를 키로 가진다.
• 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
• 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.

 

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

class Tree {
  constructor() {
    this.root = new Map();
  }
  
  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 chcar of string) {
      if (!currentNode.children.has(char)) {
        return false;
      }
      currentNode = currentNode.children.get(char);
    }
    return true;
  }
}

 

 

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

요소들을 일정한 순서대로 열거하는 알고리즘

 

정렬의 특징

• 정렬 기준은 사용자가 정할 수 있다.
• 크게 비교식과 분산식 정렬로 나눌 수 있다.
• 대부분의 언어가 빌트인으로 제공해준다.
• 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재한다.

 

비교식 정렬

버블 정렬

• 서로 인접한 두 요소를 검사하여 정렬하는 알고리즘
• O(n2) 시간 복잡도를 가진다.
• n-1 번 순회하면 정렬 마무리 됨.

 

선택 정렬

• 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘
• O(n2) 시간 복잡도를 가진다.

 

삽입 정렬

• 선택한 요소를 삽일할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘
• O(n2) 시간 복잡도를 가진다.

 

분산식 정렬

분할 정복 : 문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능 할 때 처리한 후 합치는 전략(다양한 알고리즘에 응용)

 

합병 정렬

• 분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘
• O(nlogn) 시간 복잡도를 가진다.

 

퀵 정렬

• 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬
• O(nlogn) 시간 복잡도를 가진다.

 

const array = [5, 9, 10, 3, 8, 3, 2];
// 다음과 같이 그냥 정렬하면 ASCII 문자 순서로 정렬되어 우리가 원하는 숫자 크기대로 정렬되지 않는다.
array.sort();
console.log(array); // 10, 2, 3, 4, 8, 9

array.sort((a, b) => a - b) // 오름차순 정렬
console.log(array); // 2, 3, 3, 4, 8, 9, 10

array.sort((a, b) => b - a); // 내림차순 정렬
console.log(array); // 10, 9, 8, 4, 3, 3, 2

 

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

• 정리가 안 된 책장에서 원하는 책을 찾는 방법
• 정렬되어 있는 요소들을 반씩 제외하며 찾는 알고리즘
• O(logn)만큼 시간복잡도가 걸린다.

 

이진 탐색의 특징

• 반드시 정렬이 되어있어야 사용할 수 있다.
• 배열 혹은 이진 트리를 이용하여 구현할 수 있다.
• O(logn) 시간복잡도인만큼 상당히 빠르다.

 

이진 탐색 트리

• 이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

 

이진 탐색 트리의 문제점

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.
• 그런 경우 순차 탐색과 동일한 시간복잡도를 가진다.
• 이를 해결하기 위해 AVL트리나 레드-블랙 트리가 이용될 수 있다.

 

구현 방법

Array

const array = [1, 1, 5, 124, 400, 599, 1004, 2876, 8712];

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

 

Binary Search Tree 

이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  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;
  }
}

const tree = new BinarySearchTree();
tree.insert(5);
tree.insert(4);
tree.insert(7);
tree.insert(8);
tree.insert(5);
tree.insert(6);
tree.insert(2);
console.log(tree.has(8)); //true
console.log(tree.has(1)); //false

 

이진 탐색 트리 요소 삭제

• 단말 정점을 삭제하는 경우
  • 별다른 처리 없이 부모 정점과의 연결을 끊으면 된다.
• 하나의 서브트리를 가지는 경우
  • 제거되는 정점의 부모 간선을 자식 정점을 가르키게 바꾸면 된다.
• 두 개의 서브트리를 가지는 경우
  • 왼쪽 서브 트리의 가장 큰 값 혹은 오른쪽 서브 트리의 가장 작은 값과 교체하면 된다.
  • 이 경우 교체된 정점의 좌우 자식이 없다면 제거되는 정점의 링크로 대체된다.

 

이진 탐색 트리의 문제점

• 최악의 경우 한쪽으로 편향된 트리가 될 수 있다.
• 그런 경우 순차 탐색과 동일한 시간복잡도를 가진다.
• 이를 해결하기 위해 다음과 같은 자료구조를 이용할 수 있다.
  • AVL 트리, 레드블랙트리