학습(알고리즘)

1.너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)은 시간 복잡도는 동일하지만 일반적으로 트리를 사용하는 경우는 각각의 노드마다 하나 이상의 자식들을 뿌리는 옆으로 퍼진 형태이기 때문에 큐에 데이터를 저장해서 처리해야 하는 너비우선탐색은 공간복잡도면에서 불리하다.   

    BFS(){ //너비 우선 탐색
        let node = this.root, //root에서부터 추적 시작
        let data = [], //탐색한 것 추가
        let queue = []; //탐색할 것 추가
        queue.push(node); //큐에 root 추가

        while(queue.length){ //큐의 길이가 1이상(큐가 존재할 때)이면 반복
           node = queue.shift(); //큐 맨앞을 제거 후 노드에 할당
           data.push(node.value); //노드값 data에 넣어주기
           if(node.left) queue.push(node.left); //left값이 있는 경우 큐에 넣기
           if(node.right) queue.push(node.right); //right값이 있는 경우 큐에 넣기
        }
        return data; //data 배열 반환
    }

DFSPost(){ //DFS 전위순회
        let data = []; //
        function serching(node){ //재귀함수
            data.push(node.value); //node값(아래에서 root값을 넣었다) data에 넣기
            if(node.left) serching(node.left); //좌측 재귀 시행
            if(node.right) serching(node.right); //우측 재귀 시행
        } //메인/좌측/우측의 시행이 아닌 메인/좌측/좌측의 좌측/좌측의 좌측의 좌측 등 시행 후 
          //그 다음에 있는 우측을 하나씩 진행해나가는 방식
        serching(this.root); //재귀함수 시작
        return data; //data 배열 반환
    }

2.힙은 이상하게 이진힙에 대해서만 다루는 것 같은데 이진 힙은 순서와 상관없이 최 상단을 기준으로 규칙을 정해 더 작거나 더 크기만 하면 조건을 만족하는 방식으로 최대값이나 최소값을 추출할 때 최상단(root)값을 추출한 후 한 단계씩 버블링?이라는 방식으로 교체해 나가는 방식으로 편하게 데이터를 정리할 수 있다. 새로운 데이터가 내려갈 때 자식중 더 큰 숫자와 교체하는 방식이기 때문에 최 상단은 항상 최대값 또는 최소값 규칙을 유지할 수 있다. 부모 노드를 찾는 방식은 idx값에서 1을 뺀 후 나누기2를 하고 내림하는 방식으로 Math.Floor((n-1)/2)로 표기할 수 있다.

3.우선순위 큐는 이진힙을 이용해서 우선순위를 비교한 후 최대 또는 최소값을 꺼내오는 방식을 사용하는게 대중적이기 때문에 우선순위 큐와 힙을 같은 개념으로 알 수 있지만 여러 방식이 있다. 하지만 내가 아는건 이진 힙으로 해결하는 방법 뿐이다.
이진 힙과 이진 힙을 이용한 우선순위 큐는 O(logN)이기 때문에 엄청나게 빠른 속도로 데이터를 처리(추가 및 추출)할 수 있다.
하지만 순서가 없기 때문에 데이터의 조회 등에서는 규칙을 가지고 있는 이진트리가 압도적인 효율을 가지고 있으며 추가적인 차이점으로는 트리는 내용물을 다 채울 필요가 없지만 이진 힙은 각 계층이 다 채워지고 난 다음에 자식 노드가 추가된다는 점이 있다.

생각보다 확 나갈 수가 없었다.

아무래도 평일에 하루 한강 이상씩 듣는 방향으로 빠르게 보충해줘야 할 것 같다.