Javascript에서 힙이 필요하면 매번 구현을 해줘야하는 정말.. 험난한 여정이 있는데요. 저번에 제가 대략적으로 공유한 코드가 모든 상황에서 쓰이기 힘들더라구요. 특히 pop에서 최상단 노드부터 왼쪽 노드, 오른쪽 노드를 비교해줘야하는데, 이 과정에서 undefined와 관련해서 많은 오류가 있는 걸 확인했습니다. 새로 짠 코드를 공유해드릴게요. Heap.js class MinHeap { constructor() { this.heap = [null]; } push(val) { this.heap.push(val); let currentIndex = this.heap.length - 1; let parentIndex = Math.floor(currentIndex / 2); while (parentInd..

안녕하세요. 카카오 2021 인턴 표 편집을 하던도중 이건 그냥 봐도 연결리스트를 쓰라는 것 같더라구용. 자바스크립트에서 한 번도 연결리스트를 써본 적이 없었는데 구현 코드를 보니 상당합니다. 이건 정리 한 번 해야겠어요! 자 그럼 같이 한 번 보죠! 1. 연결리스트가 유용한 상황 연결리스트는 배열 중간에 자료를 없앤다던가, 새로 삽입해야한다던가 하는 상황에서 매우 유용한 자료입니다. 일반적인 stack 구조에서는 pop이나 push가 아닌 중간에서 자료를 조작해줘야하는 상황이 오면, 뒤에 모든 요소를 같이 조작해줘야하거든요. 이런 구조에서 유용하게 쓰입니다. 그럼 javascript에서 구현을 한 번 알아볼까요? 2. javascript에서 구현 팁 큐나 힙처럼 배열안에서 조작한다면 결국엔 나중에 fi..

스택과 큐로 모든 자료구조를 다 처리할 수 있었던 프로그래머스의 레벨 2문제와 다르게 레벨 3만 되어도 다양한 자료구조들을 쓰는 걸 발견했다. 힙(Heap)이나 트라이(Trie)등 아직 익숙하지 않은 자료 구조를 하나하나 정리해볼 생각이다. 그리고 여담이지만 js에서는 자료구조 라이브러리가 없어서 다 직접 구현해줘야한다. js 환경에서 class만드는게 익숙하진 않았지만, 수 십 번의 큐를 만들면서 구조가 나름 익숙해졌다. 자 힙에 대해 알아보자! 힙과 우선순위 큐 일반적인 큐는 FIFO 구조를 따르기 때문에 먼저 enqueue 된 요소가 먼저 나가지만, 우선순위 큐에서는 가장 우선 순위가 높은 요소가 먼저 나간다. 조금만 생각해보면 이 이상한 구조가 매번 요소 삽입때마다 정렬을 해줘야한다는 걸 알 수 ..