[TIL] JS : 트리, 트라이 과제하기😢

21년 08월 08일의 소회

하, 정말 어찌저찌 과제를 끝냈다. 사실 7일에 작성해야 맞는 TIL이지만 9일 아침에 쓰고 있어요? JS 문법을 정말 무지랭이처럼 모르는 게 너무 많다는 사실을 깨달았고! 프로그래머스 레벨1이나 겨우겨우 푸는 쪼렙인데 레벨 3~4 수준의 과제를 던져주셔서 너무 눈물이 나고 밤새 구글링을 했지만 쉽지 않았다는 그런.. 슬픈 이야기를 잠시 써보겠습니다. 그래도 나름 이진 트리를 순회하는 전위, 후위, 중위 순회는 나름대로 그 순회의 방식을 이해하고 재귀 호출을 통해 반복적인 동작을 간결한 코드로 구현을 했다면!(중요) 트라이는 정말 뭔가 머리속에 그 구조가 잘 세부적으로 그려지지가 않고 그렇기 때문에 이걸 통해서 어떻게 자동완성 메서드를 구현할 수 있을까?에 대한 심난함. 게다가 내가 그걸 논리적으로 짠다고 하더라도 거기에 적합한 문법을 잘 모른다는 함정.. 속에서 구글링만 하다가 결국 과제 제출 시간 3시간이 남았고 혼자해서는 끝을 낼 수 없다는 생각 하에 도움을 요청했고! 승록님(천사😇)께서 진짜 기초적인 문법부터 차근차근 설명해주셔서 남은 코드를 혼자 작성해볼 수 있었다!

그리고 남은 주말 동안 정말 하려고 했던 학습이 정말 많았는데 평일에 너무 달렸다보니 일요일인 어제 결국 밤 10시에 쓰러져서 잠들고 말았고 특히 오늘 생일이라 주말에 가족 및 연인과 식사 약속도 챙기느라(내 생일인데.. 왜 힘들지?) 시간을 써야 했기 때문에 학습에 많은 투자를 하지는 못 했는데 그래도 그런 시간을 가졌기 때문에 기분도 리프레시가 되어서 또 이번주를 달릴 힘을 얻은 것 같다.

📝 이진 트리(Binary Tree)를 전위, 중위, 후위 순회로 탐색하기

이진 트리가 뭔지 알게 무엇인가? 이진 탐색이나 CS 공부할 때 겨우 배웠다구요? 이진 탐색을 하면 탐색 시간이 O(n)에서 O(log n)으로 줄어든다..(TMI)

암튼 그래서 이번 기회에 이진 트리, 그리고 순회 탐색에 대해 확실히 배우는 시간이 되었다! 나는 이런 방식으로 재귀 호출을 통해 구현을 했는데

특히 사용을 하면서도 재귀 호출에 대해 명확하지 않은 부분이 있었는데 과제를 끝낸 후 민정님께서 정말 정말 감사하게도 자료까지 제작해서 재귀 호출이 동작하는 방법에 대해 설명을 해주셔서 조금 더 명확하게 이해를 하는 시간이 되었다.

그리고 추가적으로 메서드 별 재귀호출의 기본 단계에서,

if(node != null) 

을 통해서 빈 노드를 판단하는 조건을 주는 것보다

if(!node)

를 사용하는 것이 null과 undefined를 모두 다 처리해주기 때문에 더 좋다고 한다.

구현을 하면서 고민했던 부분

• 탐색 순서를 출력할 때 console.log()로 한 줄 한 줄 구현되는 것은 시각적으로도 그렇고 추후에 실질적으로 해당 기능을 구현한다고 가정했을 때 효율적이지 못 할 것이라고 생각을 해서 순회 메서드에서는 순회의 순서대로 노드를 임시로 배열을 선언해 넣어놓고 마지막에 해당 순회 순서를 출력해보고자 할 때 배열로 깔끔하게 출력이 되도록 했다.

• 그리고 이 과정에서 해당 배열을 어디에 선언하느냐도 고민 포인트였다. Tree 클래스 위에 선언해서 아래에 클래스 코드가 실행될 때 이 배열이 존재하게 해야 하는지, 혹은 Tree 클래스와 메서드는 함수와 같은 역할을 해줄 뿐 이걸 사용해서 직접 실행이 될 때는 Tree 클래스를 사용한 tree 변수를 선언하고 난 후니까, 그 위에만 적어주면 되는지였다. (말로 명확하게 설명이 되는 건가..) 아무튼 나는 후자를 선택했고 동작은 정상적으로 이루어졌으나 이 부분에 대해 기동멘토님께서 배열 선언은 코드 최상단에 하는 게 좋겠다는 피드백을 받아 수정했다.

• 또한 반복적인 동작을 코드로 처리할 때 재귀 호출을 사용하면 코드의 간결성은 훨씬 높아지긴 하는데 과연 for, while과 같은 반복문을 사용하는 것보다 메모리 효율성 측면에서도 더 좋은지에 대해 궁금했는데 이에 대해 멘토님이 답변을 남겨주시기로는 재귀 함수가 반복적으로 자기 자신을 호출하면서 stack 메모리에 계속해서 쌓이기 때문에, 메모리 측면에서는 반복문(for문)이 더 좋다고 생각하며 재귀 함수는 overflow 문제도 발생할 수 있어 멘토님께서는 for문을 더 선호하신다고 했다.

이진 트리와 순회에 대한 개념은 다음에 다시 자세히 적어보도록 하겠어요.

📝 트라이(Trie)구조를 통해 키워드 자동완성 구현하기

트라이 구조는 소회에도 적었듯 정말 머릿속에 잘 들어오지 않았다. 사실 지금도 이게 명확하다고 말할 수는 없고 컴퓨터가 동작하는 방식을 내 머릿속에서 구현하는 것은 아직 조금 어려운 측면이 있다고 생각하지만 차차 공부하며 적응해나갈 문제라고 생각하기 때문에 조급하지 않으려고 한다.

아무튼 해당 과제는 유저가 어떤 문자를 입력했을 때 기존에 입력돼있는 데이터 셋에서 유저가 입력한 문자열과 일치하는 문자열을 자동완성 키워드로 제공하는 것이었다.

👇 autoComplete method 코드는 다음과 같다.

구현을 하면서 고민했던 부분

• 모든 것이기 때문에.. 더이상 적지 않겠다.

• 다만, 코드를 이해하고 내 것으로 만든 다음에 해당 코드 구현에서 조금 신경 쓴 점은(아주.. 미세한 부분이지만) 자동 완성 키워드를 출력할 때 단순히 나열하고 끝나는 게 아니라 alphabet 순서대로 정렬을 한 뒤에 출력을 해주도록 한 것이었다. 추후에 실제로 자동 완성 기능을 구현한다면 이런 부분은 유저들이 더 많이 검색을 한 키워드를 횟수 순서대로 정렬을 해 보여줄 수 있도록 구현해보는 게 더 좋을 것 같다고 생각해 시간이 되면 나중에 검색 횟수도 입력 값으로 넣어놓고 한 번 구현해보고 싶다.

피드백을 통해 처리한 부분

• trie.autoComplete("");이 실행됐을 때 실제적으로 유저는 빈 문자열을 입력하여 보여줄 키워드가 없어야 하지만 빈 문자열과 일치하는 문자열을 현재 트라이에 존재하는 모든 문자열이기 때문에 입력되어있는 모든 데이터셋이 출력되는 문제가 있다는 것을 멘토님께 피드백 받았다.

// when users search an empty string, we will quit this process

    if (userInput === "") {
      console.log('검색을 희망하는 키워드를 입력해주세요.');
      return false;
    }

그래서 autoComplete 메서드 상단에 해당 코드를 추가해서 빈 문자열인지 판단하고 빈 문자열일 경우, 해당 메서드 실행을 종료하도록 했다.

• 팀원분께서 기존 데이터셋에 abc, abcd가 포함이 되어있어도 trie.autoComplete("a");를 실행했을 때 가장 abc는 리프노드로 인식되지 않기 때문에 abcd만 출력되는 예외 케이스 처리가 필요하다는 피드백을 해주셨다. 사실 처음에 무슨 말인지 잘 이해가 되지 않았는데 출력 값을 확인해보니 바로 알 수 있었다. 그래서 insert(userInput) 메서드에서 기존 데이터 입력 값을 받을 때 문자열의 가장 마지막에

userInput += '*'; // endpoint

이렇게 엔드 포인트를 지정해줬고 다만 이게 출력이 되었을 때도 노출이 되는 건 원치 않아서 autoComplete 메서드에서 자동 완성 키워드 출력을 위한 스택에 해당 문자열을 최종적으로 push하기 전에

let keyword = currentNode.value.replace(/\*$/, '');

문자열의 맨 마지막에 '*'이 있으면 빈 문자열로 대체해주는 코드를 추가했다.
정말 생각도 못 한 부분이었는데 팀원분께서 피드백을 해주셔서 너무 감사했고 이걸 위해 코드를 수정하는 덕분에 얼마 전 공부한 정규표현식도 활용해서 사용을 해봤다. (뿌듯합니다)

결론

주말 동안 작성한 이 코드가 온전히 내 것이라고 말하기는 사실 아직 어려운 부분이 많다고 생각한다. 차차 더 다른 방식으로 더 좋은 방식으로 그리고 나 스스로 수월하게 이런 기능을 구현하는 개발자가 되도록 더 노력을 해야겠다. 라는 다짐을 하면서 이 과제를 마치겠다! 끝

이번 한 주도 화이팅!