공부한 내용

• 백트래킹
• DP
• 트리 구조에서의 전위,중위,후위 순회(과제)
• 트라이 자료 구조를 이용한 자동 완성 기능 구현(과제)

오랜만에 백트래킹 문제를 풀어봤는데 굉장히 애를 먹은 문제(N-Queen)였다. 다른 백트래킹 문제들은 조금 풀어 보았는데, 백트래킹의 가장 대표적인 N-Queen 문제는 한번도 풀어본 적이 없었다.

N-Queen 접근 방법(코드 X)

처음 접근 방법은 2차원 배열을 생성하고 퀸이 존재하는 좌표를 하나의 배열에 저장한 뒤 재귀를 통해 퀸의 좌표를 가지고 있는 배열을 순회하며 현재 퀸을 놓으려는 행에 놓을 수 있는지 없는지를 체크한 후, 어떠한 한 행에라도 퀸을 놓을 수 없으면(배열의 크기가 n*n인데 n개의 체스를 놓아야 하므로) result를 증가시키지 않고 모든 행에 하나씩 퀸을 놓을 수 있으면 result를 증가시키는 방향으로 설계를 했다.

아무리 머리속으로 계산을 하고 순서도(콜 스택) 그려봐도 이 아이디어가 맞다고 생각했는데 자꾸 히든 케이스에서 몇가지가 틀렸다. 끝까지 파고들고 어디 부분이 잘못 됐는지 찾았다면 찾을 수는 있었겠지만 그냥 이번엔 강사님의 코드를 보았다.

역시나 강사님의 코드를 보기를 잘 한 것 같다. 나는 2차원 배열을 사용할 것을 생각했지만, 강사님께서는 1차원 배열을 사용하여 백트래킹을 진행하셨다.

강사님이 1차원 배열을 사용하셨다는 것을 보고 강사님의 코드를 보지 않고 다시 아이디어를 설계했고, 코드를 구현했더니 맞았다. 이후 2차원 배열로도 틀렸던 히든케이스를 찾아 고쳐 실행을 해보았는데 가장 오래걸렸던 히든케이스가 각각 대략 200ms와 900ms가 나왔다. 700ms나 차이가 나는 것을 보았고, 앞으로도 구현하고 난 뒤에 더 나은 방법이 없을지 고민해보고 답이 안나온다면 다른 사람의 코드를 보는 것이 도움이 된다는 것을 다시 한 번 느꼈다.

단어 퍼즐(설계도 못함)

이어서 DP문제를 풀어보았는데 이건 아예 아이디어조차 떠오르지 않았다. 평소 코딩테스트 준비를 할 때도 DP는 진짜 못하고 어려웠는데 아니나 다를까 이번에도 어려웠다 .. 더군나나 문제는 레벨4..

결국 강사님의 코드를 보았고 한줄 한줄 분석하며 해답을 찾아 이해는 했지만, 다른 어려운 DP 문제들을 보면 또 헤맬 것 같다. DP만큼은 왜 실력이 늘지 않는 것일까..

전/중/후위 순회

강사님께서 스택 or 재귀를 사용해서 구현하라 하셨는데 갑자기 딱 재귀를 이용한 방법이 떠올라서 바로 구현을 하였다. 그런데 다른 분들 과제 제출 PR 날리신 걸 보니 다른 기능들을 추가하신 분들이 많았다.. 멘토님께 리뷰 받고 난 뒤에 나도 기능을 추가 해봐야겠다.

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

// 트리
class Tree {
    constructor(node) {
        this.root = node;
    }
    
    // 중위순회
    InOrderTree(node, arr) {
        if(!node) {
            return;
        }
    
        this.InOrderTree(node.left, arr);
        arr.push(node.val);
        this.InOrderTree(node.right, arr);

        return arr;
    }
    
    // 전위순회
    preOrderTree(node, arr) {
        if(!node) {
            return;
        }
    
        arr.push(node.val);
        this.preOrderTree(node.left, arr);
        this.preOrderTree(node.right, arr);

        return arr;
    }
    
    // 후위순회
    postOrderTree(node, arr) {
        if(!node) {
            return;
        }
        
        this.postOrderTree(node.left, arr);
        this.postOrderTree(node.right, arr);
        arr.push(node.val);

        return arr;
    }
}

const tree = new Tree(new Node(1));

tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);

console.log(">>>> 중위 순회");
console.log(tree.InOrderTree(tree.root, []).join(" - "), "\n");

console.log(">>>> 전위 순회");
console.log(tree.preOrderTree(tree.root, []).join(" - "), "\n");

console.log(">>>> 후위 순회");
console.log(tree.postOrderTree(tree.root, []).join(" - "));

자동 완성 기능(트라이)

강사님의 강의를 통해 만들어 놓았던 트라이 자료구조에 덧붙혀 자동 완성 기능을 구현하는 과제였다. 처음 생각 했던 건 자동 완성된 단어들을 보여줄 때 길이 순으로 보여주고 싶었고 그러기 위해서는 BFS 알고리즘을 사용한 방법이 맞다고 생각했다(이미 강사님께서 레벨 순회를 이용하라고 써 놓으신걸 못보고 혼자 고민하고 있었다..ㅎ).

레벨 순회를 통해 자동 완성된 단어들이 자연스레 단어의 길이 순서대로 출력이 되었고 찾을 수 없는 단어를 입력했을 때의 예외처리와 내가 찾고자 하는 단어가 자료구조에 포함되어 있는지에 대한 에외처리를 추가로 구현하여 과제를 제출했다.

이 부분도 코드리뷰를 받고 난 뒤에 추가할 기능에 대해 고민해보고 기능을 추가해 보아야겠다.

// level order traversal을 위한 Queue
class Queue { 
    constructor(){
        this.queue = [];
        this.front = 0;
        this.back = 0;
    }

    enqueue(value){ 
        this.queue[this.back++] = value;
    }

    dequeue(){   
        const value = this.queue[this.front];
        delete this.queue[this.front]; // 
        this.front += 1;
        return value;
    }

    size(){
        return this.back - this.front;
    }
};

class Node {
    constructor(value = '') {
        this.value = value; // 현재 경로까지의 누적 값
        this.end = false; // 해당 노드에서 끝나는 문자열이 있는지 여부
        this.child = new Map() // 자식
    }
}

// 트라이
class Trie {
    constructor() {
        this.root = new Node();
    }

    // 단어 삽입
    insert(string) {
        let currentNode = this.root; // 루트노드를 시작으로 탐색하면서 삽입

        for (let char of string) {
            // 만일, 해딩 키를 가진 자식이 없다면 새 노드를 만들어준다
            if (!currentNode.child.has(char)) {
                currentNode.child.set(
                    char,
                    new Node(currentNode.value + char)
                );
            }
            currentNode = currentNode.child.get(char); // 자식 노드로 이동한다
        }
        
        currentNode.end = true; // 해당 노드에서 끝나는 단어가 있음을 알린다
    }

    // 단어 탐색 
    search(string) {
        let currentNode = this.root; // 시작은 루트

        for (let char of string) {
            // 찾고자 하는 문자가 있으면 노드 이동, 없으면 false 리턴
            if (!currentNode.child.has(char)) {
                return false;
            } 

            currentNode = currentNode.child.get(char);
        }
        
        // 찾는 문자열의 마지막까지 탐색했다는 건, 문자열을 찾았다는 것이므로 마지막 문자의 Node 리턴
        return currentNode;
    }

    // 입력한 단어의 마지막 문자를 기준으로 level order traversal
    levelOrder(node) {
        const queue = new Queue(); 
        queue.enqueue(node);

        while (queue.size()) {
            const currentNode = queue.dequeue();
            
            // 등록된 단어만 출력
            if (currentNode.end) console.log(currentNode.value);
            // 키에 해당하는 노드(value: 현재까지의 문자를 더한 단어, end: 등록된 단어 유무, child: 다음에 이어지는 문자)를 큐에 입력
            for (let key of currentNode.child.keys()) {
                queue.enqueue(currentNode.child.get(key))
            }
        } 
    }

    autoComplete(string) {
        // string을 가지고 있는 node를 찾아서
        let node = this.search(string);
        console.log("검색어 :", string);

        // 예외 처리
        if (!node) return console.log("❌ 해당하는 문자로 시작되는 단어를 찾을 수 없습니다 ❌");

        this.levelOrder(node);
    }
};

// 트라이 생성 후, 단어 입력
const trie = new Trie();
trie.insert("pro");
trie.insert("proud");
trie.insert("programmers");
trie.insert("proto");
trie.insert("prou");
trie.insert("prototype");
trie.insert("primary");
trie.insert("picnic");
trie.insert("plz dm");

// 트라이 자료구조 특성상(레벨 순회) 단어의 길이가 짧은 순으로 자동완성이 됨.
trie.autoComplete("pro");
console.log("");

trie.autoComplete("br");
console.log("");

// 단어 탐색
let word = trie.search("proud");
word ? console.log(word.value) : console.log("찾는 단어가 없습니다.");
console.log("");

// 단어 탐색
word = trie.search("proudddd");
word ? console.log(word.value) : console.log("찾는 단어가 없습니다.");

느낀점

DP에 대해서는 완벽하게 부족하다는 걸 느꼈고, 백트래킹은 여러 문제를 더 풀어보면 좋을 것 같았고, 과제를 통해 앞으로 있을 프로젝트에 검색 기능을 넣는다면 직접 자동완성 기능을 구현하여 넣어보고 싶었다.

하나씩 하나씩 결과물이 나오니 점점 재미있어진다. 더욱 열심히 해봐야겠다!