Portfolio

과제 내용(각자 카드에 복사해 주세용!)

필수 과제 - 코드 리뷰 필수 (~8/6)

트리를 이용하여 전위 순회, 중위 순회, 후위 순회를 검색하여 직접 구현해보세요.

힌트: 스택, 재귀 호출

트라이를 사용하여 자동 완성 코드를 구현하세요.

이전에 트리 파트에 사용된 레벨 순회를 응용하여 구현하시오!

추가 과제 - 코드 리뷰 선택 https://prudhvignv.github.io/pathFinderVisualizer/ 구현해보기 (~8/14)

학생 CheckList

남명훈

김형욱

나은찬

도가영

김현석

김태중

김홍중

김희진

임효성

채점 기준

공통

var와 let, const를 적절히 잘 사용했는가.

올바른 자료구조를 사용했는다.

올바른 결과가 나오는가.

예외 처리가 잘 되었는가.

트리

스택 원리를 잘 이용했는가가 핵심

트리 전위, 중위, 후위 순회를 Stack으로 구현 (120점)


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

class Tree {
  constructor(node) {
    this.root = node;
  }

  preorder() {
    const answer = [];
    const stack = [this.root];

    while (stack.length > 0) {
      const currentNode = stack.pop();
      answer.push(currentNode.value);
      if (currentNode.right) stack.push(currentNode.right);
      if (currentNode.left) stack.push(currentNode.left);
    }

    return answer;
  }

  inorder() {
    const answer = [];
    const stack = [];

    let currentNode = this.root;
    while (true) {
      while (currentNode) {
        stack.push(currentNode);
        currentNode = currentNode.left;
      }

      if (stack.length > 0) {
        currentNode = stack.pop();
        answer.push(currentNode.value);
        currentNode = currentNode.right;
      } else {
        break;
      }
    }

    return answer;
  }

  postorder() {
    const answer = [];
    const stack = [];

    let currentNode = this.root;
    while (true) {
      while (currentNode) {
        if (currentNode.right) stack.push(currentNode.right);
        stack.push(currentNode);
        currentNode = currentNode.left;
      }

      if (stack.length > 0) {
        currentNode = stack.pop();

        if (currentNode.right && stack[stack.length - 1] === currentNode.right) {
          stack.pop();
          stack.push(currentNode);
          currentNode = currentNode.right;
        } else {
          answer.push(currentNode.value);
          currentNode = null;
        }
      } else {
        break;
      }
    }

    return answer;
  }
}

const tree = new Tree(new Node(9));
tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4);

console.log(tree.preorder());
console.log(tree.inorder());
console.log(tree.postorder());

트리 전위, 중위, 후위 순회를 재귀로 구현 (100점)


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

class Tree {
  constructor(node) {
    this.root = node;
  }

  preorder(currentNode) {
    console.log(currentNode.value);
    if (currentNode.left) this.preorder(currentNode.left);
    if (currentNode.right) this.preorder(currentNode.right);
  }

  inorder(currentNode) {
    if (currentNode.left) this.inorder(currentNode.left);
    console.log(currentNode.value);
    if (currentNode.right) this.inorder(currentNode.right);
  }

  postorder(currentNode) {
    if (currentNode.left) this.postorder(currentNode.left);
    if (currentNode.right) this.postorder(currentNode.right);
    console.log(currentNode.value);
  }
}

const tree = new Tree(new Node(9));
tree.root.left = new Node(3);
tree.root.right = new Node(8);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
tree.root.right.right = new Node(7);
tree.root.left.right.right = new Node(4);

tree.preorder(tree.root);
tree.inorder(tree.root);
tree.postorder(tree.root);

트라이

자동완성이 없을 때 예외 처리

Queue를 이용했는지

결과가 잘 나오는지

Trie 자동완성 코드


class Node {
  constructor(value = '') {
    this.value = value;
    this.children = new Map();
  }
}

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);
    }
  }

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

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

      currentNode = currentNode.children.get(char);
    }

    return true;
  }

  autocomplete(string) {
    if (string === '') {
      return [];
    }

    let targetNode = this.root;
    for (const char of string) {
      targetNode = targetNode.children.get(char);
    }

    const answer = [];
    const stack = [targetNode]; // DFS가 아닌 BFS로 해결해도 상관없다.
    while (stack.length > 0) {
      const currentNode = stack.pop();
      if (currentNode.children.size > 0) {
        for (const [_, node] of currentNode.children) {
          stack.push(node);
        }
      } else {
        answer.push(currentNode.value);
      }
    }

    return answer;
  }
}

const trie = new Trie();
trie.insert('cat');
trie.insert('can');
trie.insert('cap');
trie.insert('code');
trie.insert('coworker');
trie.insert('cookie');
console.log(trie.autocomplete('co')); // ['cookie', 'coworker', 'code']

[달리팀] 1주차 과제 리뷰

필수 과제 - 코드 리뷰 필수 (~8/6)

학생 CheckList

채점 기준