20210609

목표

• 트라이 구현 수정
• 전화번호 목록 트라이를 사용해서 풀이
• 프로그래머스 해시 이용한 최적화 문제 풀이 베스트앨범 진행중
• 최적화 문제 푸는법 - 해시 이용 예제 정리 -> a^3 + b^3 = c^3 + d^3

Facts

• 아침체조 및 운동
• Boyer and Moore 알고리즘 공부
• 목표들 수행

Feelings

퇴사 면담을 했다. 순식간에 지나간 5개월이었다. 당시에는 열심히 했다고 생각했는데 막상 마무리가 다가오니, 모든게 아쉽게 느껴진다. 이직 준비를 하든 공부를 하든 뭘하든지 간에 마무리가 다가왔을때, 후회가 없는 상태가 되고 싶다. 그래도 최선을 다했다라고 스스로 생각할 수 있었으면 좋겠다.

그래도 가는 방향이 다른 것 뿐이니, 너무 아쉬워하지 말고 남은 기간동안 끝까지 매듭을 잘 짓자.

Trials

트라이 구현 수정

어제 자바로 구현했던것을(https://velog.io/@gringrape200/20210608)
자바스크립트로 다시 풀어보았다. 이번에는 재귀를 사용해 보았다.
무슨일이 일어나는지 알기 어려운 수동루프보다는 논리적으로 쉬워진것 같다.

수동루프를 최대한 자제하고 있는데,
현재 노드나 글자 인덱스 같이 상태를 다룰때는
상태변경을 외부로 돌리는 재귀를 사용하거나, reduce, fold 와 같이 고차함수를 이용하는 녀석들을 사용해야 하는것 같다.

최근에 프로그래머스 문제들중 배열 활용 풀면서,
효율성 문제로 어쩔수 없이 불변성을 지키지 못하고 상태를 활용했었는데, TDD 로 접근하기 위해서 어떻게 할지 망설여졌었다. 다행히 답은 이미 배운것이었다.

상태를 인수로 받고 새 상태를 결과와 함께 돌려주는 순수함수를 활용한다.

스칼라로 배우는 함수형 프로그래밍 6장에 나오는 구절인데, 코드숨 1주차 과제에서도 활용되었던 아이디어라서 이해가 잘되었다. 재귀함수를 짤때는 이렇게 짤수 밖에 없기도 하고.

한편, Trie 를 만들면서 단어가 끝나는 지점을 tree 차원에서 관리할지, node 차원에서 관리할지가 많이 고민이 되었다. 글자 차원에서 단어가 끝나는 지점을 아는게 이상하다는 생각이 많이 들었다. tree 차원에서 관리하는 방법도 있을것같다. hashSet 같은 녀석을 활용해서 단어가 끝나는 노드 객체의 해시값을 모아놓을 수도 있을 것 같다. 둘 중에 처리가 단순한 node 단위에서 활용을 선택했다. leetcode에 다른 사람들이 푼것들을 보니 같은 선택을 한 경우가 많았다.

현재 속도측면에서 개선할 점이 좀 있는 것 같다. javascript 제출중에 하위 90% 로 느리다 ㅜㅜ
직접 사용하는건 아니라서 별 상관은 없지만, 어떤 부분이 느린지 궁금하기는 하다. children 관리 방식이 잘못된 걸까? leetcode 의 다른 풀이를 조금 더 참고해서 어떤 디테일의 차이가 있는지 검토해보아야 겠다.

속도개선과 더불어 또 한가지 시도해볼것은 스칼라의 대수적 자료구조로 구현해보는 것이다. 패턴매칭을 활용하면 어떻게 구현될지 궁금하다.

여러가지 시도와 개선을 통해서 다른 자료구조를 학습할때에도 활용할 관전 포인트나 시도 포인트들을 많이 획득했으면 좋겠다.

---> 근데, 다시보니까 node 의 children 이 다른 자료 구조를 사용하면 tree 단위도 터진다. 진짜 바보다... 고쳐야 겠다..

--> 활용할 수 있는 문제가 이만큼이나 된다... 헐 https://leetcode.com/tag/trie/
자료구조를 개별적으로 공부할 때는 leetcode 를 이용하면 확실하게 학습할 수 있을듯하다. 역시 공부는 하려고만 하면 자료는 많다.

class TrieNode {
  constructor() {
    this.ended = false;
    this.children = new Map();
  }

  end() {
    this.ended = true;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word, current = this.root, index = 0) {
    if (index > word.length - 1) {
      current.end();
      return;
    }

    const letter = word[index];
    const newNode = new Node();

    current.children.set(letter, newNode);

    this.insert(word, newNode, index + 1);
  }

  search(word, current = this.root, index = 0) {
    if (index > word.length - 1) {
      return current.ended;
    }

    const letter = word[index];
    const nextNode = current.children.get(letter);

    return nextNode
      ? this.search(word, nextNode, index + 1)
      : false;
  }

  startsWith(word, current = this.root, index = 0) {
    if (index > word.length - 1) {
      return true;
    }

    const letter = word[index];
    const next = current.children.get(letter);

    return next
      ? this.startsWith(word, next, index + 1)
      : false;
  }
}

Affirmation

나는 매일 무언가를 개선하는 사람이다.
나는 나를 믿는다 동시에 내가 판단한 모든것이 잘못되었을수 있다는것도 인정한다.