트리, 트라이로 자동 완성 코드 만들기

git branch 생성과 push

1. 원본 repository를 clone

2. 브랜치 생성과 이동을 한번에 git checkout -b 브랜치명 (git project root 경로에서 실행해야 함.)

3. git push origin(원격저장소이름) 브랜치명 git remote -v 로 원격저장소 정보 확인 가능.

fetch와 switch

1. git fetch all

2. git switch (브랜치 명)

3. git log : origin이랑 local이랑 sync가 맞지 않으면 git pull, 맞으면 code .

🤔 과제 1

const Tree = [
    undefined,
             1,
           2, 3,
         4,5, 6,7,
 8,9, 10,11, 12,13, 14,15
]

function preorder(tree, i) {
    if(tree[i] === undefined) {
        return;
    }
    console.log(tree[i]);
    preorder(tree, 2*i);
    preorder(tree, 2*i+1);
}

function inorder(tree, i) {
    if(tree[i] === undefined) {
        return;
    }
    inorder(tree, 2*i);
    console.log(tree[i]);
    inorder(tree, 2*i+1);
}

function postorder(tree, i) {
    if(tree[i] === undefined) {
        return;
    }
    postorder(tree, 2*i);
    postorder(tree, 2*i+1);
    console.log(tree[i]);
}

console.log("---------preorder-------------");
preorder(Tree, 1);
console.log("---------inorder-------------");
inorder(Tree, 1);
console.log("---------postorder-------------");
postorder(Tree, 1);

• 배열에 탐색하고 싶은 값을 담아 순회.

• 각 순회 시 재귀함수로 탐색.

• console.log(접근자)가 호출하는 위치에 따라 순회방식이 달라짐.

🤔 과제 2

import {Queue} from "./Queue.js";

class Node {
    constructor(value = "") {
        this.value = value;
        this.children = new Map();
        this.isEnd = false; //mark end of the word
    }
}

export 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);
        }
        currentNode.isEnd = true;
    }

    has(string) {
        let currentNode = this.root;

        for (const char of string) {
            if (!currentNode.children.has(char)) {
                return false;
            }
            currentNode = currentNode.children.get(char);
        }
        return currentNode.isEnd;
    }

    autocomplete(string) {
        
        //find node by string
        let currentNode = this.root;
        for (const char of string) {
            if (!currentNode.children.has(char)) {
                return [];
            }
            currentNode = currentNode.children.get(char);
        }

        //find searched history
        const history = [];
        const que = new Queue();
        que.enque(currentNode);
        while (que.size > 0) {
            const curNode = que.deque();
            for (const childNode of curNode.children.values()) {
                if (childNode.isEnd) {
                    history.push(childNode.value);
                }
                que.enque(childNode);
            }
        }
        return history;
    }

}

• insert 함수 : 입력받은 문자열을 문자로 나누어 새로운 문자라면 해당 문자로 새로운 노드를 생성함. 기존에 있는 문자라면 다음 노드로 이동함.

• has 함수 : 노드에 문자가 있다면 true를, 없다면 false를 반환함.

• autocomplete 함수 : 입력한 문자가 없다면 빈 배열을 반환하고, 있다면 검색 기록 중 만들 수 있는 단어를 보여줌.

🤩 피드백