반응형

코딩테스트 2

[자료구조] 자바스크립트로 우선순위 큐(Priority Queue) 구현하기

우선순위 큐란? - 일반적인 큐는 선입선출 (FIFO)원칙에 따라 데이터가 처리된다. - 우선순위 큐는 각 데이터들이 우선순위가 있어서, 큐에 들어온 순서는 차순위가 되고 정해진 우선순위에 따라 데이터가 큐에서 나가게 된다. Heap 자료구조 - Heap 자료구조는 완전 이진트리의 일종이다. - 완전이진트리란 루트 노드부터 시작하여 왼쪽 자식, 오른쪽 자식 순서대로 데이터가 삽입되는 트리를 말한다. - Heap은 항상 루트 노드를 제거하는 식으로 동작한다. - 자바스크립트로 우선순위 큐를 구현하는데 있어서 이 Min Heap (최소 힙) 자료구조를 사용한다. - 최소 힙은 부모 노드가 항상 자식 노드보다 값이 작다는 특징을 갖고 있다. 일반 배열을 사용하지 않는 이유는 무엇일까? - 데이터를 조회하기 위..

Computer Science 2024.03.09

[알고리즘] 최적 부분 구조

최적 부분 구조란, " 부분 문제의 답을 이용해서 기존 문제의 답을 구할 수 있는 구조"를 가진 구조이다. 예를 들어, 총 5개의 새콤달콤을 팔려는 영희가, 1개에는 100원, 2개에는 400원, 3개에는 800원, 4개에는 900원 , 5개에는 1000원에 팔고자 하고, 이 수익을 최대화 하는 전략을 고민하는 문제가 있다고 하면, 5개를 갖고 최대 수익을 내는 방법 1. 4개를 갖고 최대 수익을 내는 방법 + 1개를 갖고 최대 수익을 내는 방법 2. 3개를 갖고 최대 수익을 내는 방법 + 2개를 갖고 최대 수익을 내는 방법 3. 5개를 한명에게 팔았을 때의 수익 과 같이 구분 지을 수 있다. 3번의 경우에는 심플하지만 1, 2번의 경우 결국 4개를 갖고 최대 수익을 내는 방법은 2개, 2개씩 혹은 3개..

Computer Science 2023.06.25
반응형