[Front-end🦁] #35 알고리즘 / 이진트리

1. 코테 문제풀이

문제 풀이는 전부 풀 수 있는 문제들이라서 서론을 설명하실 때 파이썬으로 후딱 풀고 설명 들으면서 자바스크립트 참고할 점이나, 내 로직에서 수정할 점을 체크했다.

1. 비밀지도

전에 정규표현식 처음 나올 때 언급하신 문제라서 정규식으로 바로 접근할 수 있었다. 정규식은 사실 쓰려고 하면 몇 개 빼고는 다 기억이 나는데.. 정규식 모듈 함수들이 기억이 안난다. 파이썬 re 문서, apple regex 문서 정독 필수

비밀 지도

2. 다트 게임

다트 게임은 공교롭게도.. 저번주 스터디 문제였는데 저번 주에 너무 바빠서 못풀다가 어제 푼!! 문제였다. 선생님의 풀이가 내 풀이랑은 조금 차이가 있었지만, 기본 로직은 같았다.

다트 게임

3. 캐시

캐시는 LRU를 이용하는 문제였는데, 캐시 사이즈가 0인 테스트 케이스 하나 빼먹고.. 문제를 너무 세분화해서 풀었다가 중복되는 코드가 많음을 깨닫고 마지막에 압축했다.

캐시

2. 이진트리

class Node {
    constructor(data){
        this.data = data;
        // this.child = []; // 2진트리가 아닌 트리가 됨
        this.left = null;
        this.right = null;
    }
}

class Tree {
    constructor(data) {
        let init = new Node(data);
        this.root = init;
        this.데이터수 = 0;
    }

    length(){
        return this.데이터수;
    }

    insert(data){
        let 새로운노드 = new Node(data);
        let 순회용현재노드 = this.root;

        while(순회용현재노드){
            if (data === 순회용현재노드.data){
                // 중복된 값은 탈락!
                return;
            }
            if (data < 순회용현재노드.data){
                // 들어온 데이터가 작으면 왼쪽
                // 비어있으면 데이터를 넣고, 비어있지 않으면 타고 또 내려가야합니다.
                if (!순회용현재노드.left){
                    순회용현재노드.left = 새로운노드;
                    return;
                }
                순회용현재노드 = 순회용현재노드.left;
            }
            if (data > 순회용현재노드.data){
                if (!순회용현재노드.right){
                    순회용현재노드.right = 새로운노드;
                    return;
                }
                순회용현재노드 = 순회용현재노드.right;
            }
        }
        this.데이터수 += 1;
    }

    DFS(){
        // 깊이우선탐색, DFS(Depth First Search)
        // Stack 이용!
        let 결과값 = [];
        let 스택 = [this.root];
        
        while(스택.length !== 0){
            let current = 스택.pop();
            if (current.right) {
                스택.push(current.right);
            }
            if (current.left) {
                스택.push(current.left);
            }
            결과값.push(current.data);
        }
        return 결과값;
    }

    BFS(){
        // BFS는 DFS의 스택을 큐로만 바꾸어주면 된다.
        // .pop() 대신 .shift()
    }
}

+ 레드 블랙 트리 : 불균형한 이진트리가 생겨서 탐색 효율이 안좋아지는 경우를 해결하기 위한 트리.

• 루트와 자식은 모두 블랙!
• 레드는 자식이 모두 블랙이어야 함.
• 블랙은 자식이 어떤 색이어도 괜찮다.
• BFS를 통해서 새로운 노드를 넣을 자리를 판단. (이진트리는 그냥 작으면 왼쪽 크면 오른쪽)