트리 ~ 그리디

트리

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

특징

• 루트 노드를 제외한 모든 노드는 반드시 하나의 부모 노드를 가짐.

• 노드가 N개인 트리는 반드시 N-1개의 간선을 가짐.

• 루트에서 특정 노드로 가는 경로는 유일함.

이진 트리

• 각 노드가 최대 2개의 자식을 가지는 트리를 의미. 탐색 알고리즘에 자주 사용됨.

• 이진트리, 완전이진트리, 포화이진트리, 편향이진트리가 있음.

이진 트리 특징

• 노드가 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있음.

• 노드가 N개인 포화 또는 완전 이진 트리의 높이는 log N임.

• 높이가 h인 포화 이진 트리는 2^h - 1개의 정점을 가짐.

• 이진 탐색 트리, 힙, AVL 트리, 레드 블랙 트리 등의 자료구조에 응용되는 경우가 많음.

이진 트리 구현 방법

const tree = {
    undefined,
    // 1
    9,
    // 1*2. 1*2+1
    3, 8,
    //2*2, 2*2+1, 3*2, 3*2+1
    2, 5, undefined, 7,
    //4*2, 4*2+1, 5*2, 5*2+1
    undefined, undefined, undefined, 4
}

힙 (Heap)

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

• heap은 우선 순위 큐를 구현하기 위한 가장 적합한 방법(우선순위 큐 ≠ 힙).

특징

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

• 우선순위가 높은 요소가 먼저 나감.

• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 가장 작은 값이 되는 최소 힙(Min Heap)이 있음.

• 아쉽게도 JS에서 직접 구현해야 함.

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

    //heap 요소 추가
    push(value) {
        this.heap.push(value);
        let currentIdx = this.heap.length-1;
        let parentIdx = Math.floor(currentIdx/2);

        while(parentIdx !==0 && this.heap[parentIdx] < value) {
            const temp = this.heap[parentIdx];
            this.heap[parentIdx] = value;
            this.heap[currentIdx] = temp;

            currentIdx = parentIdx;
            parentIdx = Math.floor(currentIdx/2);
        }
    }

    //heap 요소 제거
    pop() {
        const returnValue = this.heap[1];
        this.heap[1] = this.heap.pop();

        let currentIdx = 1;
        let leftIdx = 2;
        let rightIdx = 3;

        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[leftIdx] = temp;
                currentIdx = leftIdx;
            }
            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;
        }
        return returnValue;
    }
}

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

const array = [];
array.push(heap.pop())
console.log(array) //[ 54 ]

트라이 (Trie)

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

• 미리 정의한 문자열로 자동완성 구현 가능.

특징

• 검색어 자동완성, 사전 찾기 등에 응용될 수 있음.

• 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있음.

• L이 문자열의 길이일 때, 탐색, 삽입은 O(L)만큼 걸림 (찾는 문자열의 길이만큼 시간 복잡도를 가짐).

• 대신 각 노드가 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용함.

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

const trie = new Trie();
trie.insert('cat');
trie.insert('can');
console.log(trie.has('cat')) //true

정렬 (Sort)

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

특징

• 정렬 기준은 사용자가 정할 수 있음.

• 크게 비교식과 분산식 정렬로 나뉨.

• 삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재함.
• 버블 : 서로 인접한 두 요소를 검사하여 정렬. O(n^2)
• 선택 : 선택한 요소와 가장 우선순위가 높은 요소를 교환하여 정렬. O(n^2)
• 삽입 : 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하여 정렬. O(n^2)
• 합병 : 분할 정복 알고리즘을 이용한 최선, 촤악이 같인 안정적인 정렬 알고리즘. O(n log n)
• 퀵 : 분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 있는 불안정 정렬. O(n log n)

이진 탐색 (Binary Search)

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

• 이진 탐색 : 정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘. O(log n)

특징

• 반드시 정렬이 되어 있어야 함 → 정렬 후 탐색 시 선형 탐색보다 느릴 수 있음.

• 배열, 이진 트리를 이용하여 구현할 수 있음.

• O(log n) 시간 복잡도인만큼 상당히 빠름.

이진 탐색 트리

• 문제점 : 최악의 경우 한쪽으로 편향된 트리가 될 수 있음. 그런 경우 순차 탐색과 동일한 시간복잡도를 가짐. 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;
}
console.log(binarySearch(array, 1004)); //6

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

BFS, DFS

BFS (너비 우선 탐색)

• 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 노드부터 탐색하는 알고리즘.

• Queue를 이용하여 구현 가능.

• 시작 지점에서 가까운 노드부터 탐색.

• V가 노드 수, E가 간선 수일 때 시간복잡도는 O(V+E)임.

DFS (깊이 우선 탐색)

• 그래프 탐색 알고리즘으로 최대한 깊은 노드부터 탐색하는 알고리즘.

• stack을 이용하여 구현 가능.

• 시작 노드에서 깊은 것부터 찾음.

• BFS의 시간 복잡도와 동일함.

그리디 (Greedy)

• 매 선태개에서 지금 가장 최적인 답을 선택하는 알고리즘.

• 최적해를 보장해주진 않음.

특징

• 최적해를 구하는 알고리즘보다 빠른 경우가 많음. O(n)

• 크루스칼, 다익스트라 알고리즘 등에 사용됨.

• 직관적인 문제 풀이에 적합함.

Follow Up Tasks