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

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

이 문제 풀면서 스택에서 쓰이는 팝, pop과 큐에서 쓰이는 디큐, dequeue가 같이 있을 수 있지 않을까 하는 생각이 들었습니다. 일단 제 입맛대로 만들고 찾다보니.. 덱(Deque)이라는 자료 구조가 이미 있더라구요. 간단히 말해서 입출력을 같은 곳에서 하는 스택, 입력(rear)과 출력(front)를 구분해놓은 큐보다 자유도가 높습니다. front에서 입력과 출력을 할 수 있고, rear에서 입력과 출력을 할 수 있습니다. 이게 어떻게 이 문제와 연관되는지 같이 알아보시죠! 문제 요약 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람..