[자료구조] 자바스크립트로 큐(Queue) 구현하기

큐(Queue) 후입선출 나중에 넣은 아이템을 먼저 뺀다. 자바스크립트 코드 자바스크립트에서 shift와 push를 이용하고 배열을 이용해서 푸는 방법이 있다. 근데 아래 추천문제에서는 시간 초과가 나기 때문에 자바스크립트는 큐를 직접 구현해서 써야한다... Node와 Queue를 구현해 아래문제를 풀어보았다. const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다. const input = require("fs").readFileSync(path).toString().trim().split("\n"); class Node { constructor(item) { this.item ..

→2022.02.07

[자료구조] 자바스크립트로 스택(Stack) 구현하기

스택(Stack) 블록을 아래에서 부터 위로 쌓아 올리는 구조를 가지고 있습니다. 가장 마지막에 삽입한 데이터를 가장 먼저 사용하게 됩니다. 이러한 자료구조의 특성을 LIFO(Last-in, First-out)라고 합니다. 시간 복잡도 삽입 O(1) 삭제 O(1) 검색 O(n) 삽입과 삭제는 맨 위에서 모두 진행이 되기 때문에 O(1)의 시간복잡도를 가집니다. 검색은 스택안의 데이터를 찾을 때 까지 진행되기 때문에 O(n)의 시간복잡도를 가지게 됩니다. 자바스크립트 코드 스택은 자바스크립트에서 쉽게 구현할 수 있습니다. 자바스크립트 내장 메소드인 pop()과 push()를 이용하면 됩니다. 자바스크립트에서 배열을 하나 생성하고, 아이템을 넣고 싶다면 push(아이템) 아이템을 빼고 싶다면 pop() 을 ..

→2022.01.18

[파이썬] 우선순위 큐(Priority Queue), 힙(Heap)

우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 데이터를 우선순위에 따라 처리하고 싶을 때 사용 어떤 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우에 사용을 한다. 자료구조 추출되는 데이터 스택 가장 나중에 삽입된 데이터 (불공평하다) 큐 가장 먼저 삽입된 데이터 (공평하다) 우선순위 큐 가장 우선순위가 높은 데이터 구현하는 방법에는 두 가지 방법이 있다. 1. 리스트를 이용 2. 힙을 이용 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙 O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. 이것을 힙 정렬이라고 부른다. 이 경우 시간 복잡도는 O(..

→2021.01.07