[TIL] 2022-03-25 / 5일차

 

오늘 배운 내용

 

트리

 

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

• Root : 최상위 정점
• Node : 각 정점
• Reaf Node : 자식이 없는 정점
• Level : Root로부터의 Depth
• Degree or 차수 : 정점에서 뻗어 난 간선의 수

 

일상에서 볼 수 있는 트리 구조는 조직도, SW에서는 디렉터리 구조.

 

트리의 특징

 

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

 

 

이진 트리

• 이진 트리 : 각 정점이 최대 2개인 자식을 가지는 트리를 의미함(2개 이상 X)
• 완전 이진 트리 : 마지막 Level을 제외하고 모든 정점이 채워져 있는(2개) 트리
• 포화 이진 트리 : 완전 이진 트리에서 마지막 정점까지 모두 채워진 상태
• 편향 트리 : 한쪽으로 치우쳐진 트리

 

이진 트리의 특징

 

정점이 N개인 트리는 최악의 경우 높이가 N이 될 수 있다. 즉, N개의 정점을 가진 편향 트리가 될 수 있다.

정점이 N개인 포화 또는 완전 이진 트리의 높이는 log N이다.

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

 

일반적인 이진 트리를 사용하는 경우는 많지 않고,

1. 이진 탐색 트리
2. 힙
3. AVL 트리
4. 레드 블랙 트리

등을 구현하기 위해 사용되는 경우가 많다.

 

트리의 구현 방법

 

트리는 그래프의 일종이다. 따라서 그래프와 마찬가지로 인접 행렬과 인접 리스트 두 가지 방식으로 트리를 표현할 수 있다. 가장 중요한 기본 개념만 있으면 구현이 어렵지 않다.

• left 정점 = index * 2
• right 정점 = idnex * 2 + 1

인접 행렬로 트리를 구현하면 다음과 같다.

 

const tree = [
    undefined,
    // 1번 index
    10,
    // 2번 idnex = 1 * 2, 3번 index = 1 * 2 + 1
    13, 15,
    // 4번 = 2*2, 5번 = 2*2+1, 6번 = 3*2, 7번 = 3*2+1
    7, 11, undefined, 3
]

console.log(tree)

 

인접 리스트의 경우 Node 클래스를 생성하고, left와 right를 다루면 된다. 그리고 Tree 클래스를 생성해 생성자를 통해 root만 생성해주면 된다.

 

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

 

힙(Heap)

 

우선순위 큐

 

FIFO 구조인 큐와 달리 우선순위가 높은 요소가 먼저 나오는 구조를 가진 큐이다. 우선순위 큐는 자료구조가 아니라 개념.

 

자료구조가 아니기 때문에 구현하는 방법이 다양하다. 힙은 우선순위 큐를 구현하기 위한 가장 적절한 방법이다. 힙은 이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬된다.

 

우선순위 큐와 힙은 같은가? 다르다.

매번 우선순위에 따라 배열을 정렬해도 우선순위 큐라고 할 수 있다(자료구조가 아니기 때문). 다만 효율성의 문제가 있다.

 

힙 요소 추가

 

요소가 추가되면 트리의 마지막 정점에 추가가 된다. 추가 후 부모 정점보다 우선순위가 높은지 확인한 후 높다면 교체해 준다. 이 과정을 더 이상 바꿀 것이 없을 때까지 반복하면 된다. 반복 과정을 마치고 나면 우선순위가 가장 높은 것이 Root가 된다. 항상 이진 트리의 마지막 정점에 추가되기 때문에 항상 완전 이진 트리이다.

 

힙 요소 제거

 

우선순위가 가장 높은 Root 정점만 제거할 수 있다. Root 정점이 제거된 후에는 트리의 가장 마지막 정점이 공백을 메운다. 이때부터 정점을 아래로 내려오며 교체한다. Root 정점에서 두 자식 정점 중 더 우선순위가 높은 것과 교체를 하고, 이 과정을 반복한다.

 

힙의 시간 복잡도는 완전 이진 트리의 높이만큼 반복되기 때문에 O(log N)

 

힙 구현

 

최대 힙 클래스를 생성하고, 생성자로 배열을 생성한다.

 

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

 

추가와 삭제 모두 완전 이진 트리이기 때문에 left, right index를 구하는 게 핵심이다.

 

// 요소 추가
class MaxHeap {
    constructor() {
        this.heap = [null];
    }

    push(value) {
        this.heap.push(value)   // 마지막 정점에 값 추가
        let currIndex = this.heap.length - 1;   // 값이 추가된 정점의 현재 index
        let parentIndex = Math.floor(currIndex / 2);    // 추가된 값의 부모 index

        while (parentIndex !== 0 && this.heap[parentIndex] < value) { // 부모 index가 1일 때까지(Root 노드일 때까지) && 부모 노드의 값이 추가된 값보다 작을 때까지
            // 교체 로직
        }
    }
}

// 요소 제거
class MaxHeap {
    constructor() {
        this.heap = [null];
    }
    
    pop() {
        if(this.isEmpty()){
            return console.error("Heap is empty");
        }

        const returnValue = this.heap[1];
        if (this.heap.length === 2) return this.heap.pop();
        this.heap[1] = this.heap.pop();

        let currIndex = 1, leftIndex = 2, rightIndex = 3;

        while (
            this.heap[leftIndex] > this.heap[currIndex] || this.heap[rightIndex] > this.heap[currIndex]
        ) {
            // 교체 로직
        }
        return returnValue
    }

    isEmpty() {
        if (this.heap.length === 1) {
            return true
        }
    }
}

 

트라이(Trie)

 

트라이는 트리를 이용한 자료구조이다. 검색 엔진에서 자동완성 기능에 사용된 자료구조가 트라이이다.

트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 구조이다. 간선은 이전 정점으로부터 새롭게 추가된 정보를 갖고 있고, 정점은 이전 정점으로부터 더해진 문자열 정보(누적된 값)를 갖는다.

 

트라이 특징

 

검색어 자동완성, 사전 찾기 등에 응용된다. 일반적으로 문자열을 탐색하면, 문자열의 개수와 각 문자열의 길이만큼 시간 복잡도가 걸리지만, 트라이는 찾는 문자열의 길이만큼만 소요된다. 각 정점은 자식에 대한 링크를 전부 갖고 있어 저장 공간이 많이 필요하다.

 

트라이 구현

 

Root는 empty. 각 간선(링크)은 추가될 문자를 키로 갖고, 각 정점은 이전 정점의 값 + 간선의 키를 값으로 갖는다. 해시 테이블과 연결 리스트를 이용해 구현할 수 있다.

 

정렬

 

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

 

정렬의 특징

 

정렬 기준은 사용자가 정할 수 있다(오름차순 ? 내림차순). 크게 비교식, 분산식 정렬로 구분할 수 있다. 대부분의 언어가 빌트인으로 제공해준다.

• 삽입 정렬
• 선택 정렬
• 버블 정렬
• 머지 정렬
• 힙 정렬
• 퀵 정렬
• etc

 

어느 정렬이 빠르다고 단정할 수 없다. 각각 유리한 상황이 다르기 때문에 적절히 골라서 사용해야 한다.

 

분산식 정렬 - 요소를 분산해 정렬

 

분산식 정렬에 쓰이는 핵심 전략은 분할 정복이다. 문제를 작은 2개의 문제로 분리 -> 더 이상 분리가 불가능할 때까지 처리한 후 합병하는 전략이다.

1. 머지 정렬 : 분할 정복 알고리즘을 이용한 알고리즘, 요소를 이분해 계산하기에 최악, 최선의 시간 복잡도 모두 O(n log n)
2. 퀵 정렬 : 평균적으로 빠른 성능을 보이지만, 특정 상황에서 2차 시간이 걸리는 최악의 경우가 존재, 시간 복잡도는 O(n log n)

 

비교식 정렬 - 다른 요소와 비교해 정렬

 

1. 버블 정렬 : 서로 인접한 두 요소를 검사해 정렬하는 알고리즘, 시간복잡도는 O(N^2)
2. 선택 정렬 : 선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘, 시간복잡도는 O(N^2)
3. 삽입 정렬 : 선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식, 시간 복잡도는 O(N^2)

 

이진 탐색

 

Up and Down 게임. 이미 요소들이 정렬되어 있어야 사용 가능하다. 절반씩 탐색 범위를 줄여나가 시간복잡도는 O(log n)이다. 반드시 정렬되어 있어야 사용할 수 있다. 정렬 후 탐색하면 선형 탐색보다 오래 걸릴 수 있다.

 

이진 탐색 구현은 배열 또는 이진트리를 이용해 구현할 수 있다. 자료들이 정렬되어 있다면 이진 탐색을 사용하는 것이 유리하다.

 

이진 탐색 트리를 이용한 구현 방법

 

이진 트리에서 하나의 규칙만 추가해 주면 된다. 왼쪽 Sub 트리는 Root보다 작은 값들만, 오른쪽 Sub 트리는 Root보다 큰 값들만 들어가야 하는 규칙만 적용하면 된다.

 

이진 탐색 트리의 문제점

 

최악의 경우 한쪽으로 편향된 트리가 될 수 있고 이러면 순차 탐색과 동일해진다. 이를 해결하기 위해 AVL트리, 레드-블랙 트리를 이용할 수 있다.

 

부족했던 점

• 자동완성 코드 구현
• 이진 탐색 트리 구현

 

느낀 점

 

"갈 길이 멀다." 1주 차가 마무리되었다. 첫날부터 적응하는데 시간이 많이 걸렸고, 오랜만에 긴 시간을 학습하려 하니 체력적으로도 문제가 있는 것 같다(운동의 필요성). 학부생부터 자료구조, 알고리즘 공부를 심심하면 한 번씩(주도적인 학습이 아니라..) 했었는데, 역시 얕은 학습은 되돌아왔을 때 내 것이 아니었다. 토요일은 개인 시간을 보내는데 썼으니 일요일을 갈아 넣는 수밖에.