힙

힙 Heap 정의 힙은 완전 이진 트리 자료구조 이다. 힙에서는 항상 루트 노드를 제거한다. 종류 최소힙 (min heap) 루트 노드가 가장 작은 값을 가진다. 가장 작은 데이터가 우선적으로 제거된다. 최대힙 (max heap) 루트 노드가 가장 큰 값을 갖는다. 값이 가장 큰 데이터가 우선적으로 제거된다. 완전 이진 트리란? 루트 노드 부터 시작하며 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 데이터가 차례대로 삽입되는 트리를 의미한다. 힙에 새로운 원소가 삽입될 때 새로운 원소가 삽입되었을 때 O(log N)의 시간 복잡도로 힙 성질을 유지할 수 있다. 삽입시에 부모 노드와 크기를 비교하여 자리를 바꾼다. (최소힙은 부모노드 보다 작으면 up, 최대힙은 크면 up) 비교결과가 false 혹은 노드 도..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방법 이번 문제는 최소 힙을 적용한 우선순위 큐를 이용해 풀어야 했던 문제이다. 나는 정렬을 이용해 웨이브가 가장 큰 순서대로 해결하려 했다. 하지만, 이렇게 하게 되면 초반에 작은 웹이브들의 합이 갖고있는 병사의 수를 넘는 경우는 처리하지 못하기에 포기했다. 그렇다면 큰 웨이브는 무적권을 사용한다 치고, 작은 수만 골라 문제를 풀어야 한다는 것이다. 이진 탐색을 통해 웨이..

실행 컨택스트와 스코프, 콜 스택과 힙의 사전 지식이 필요하다. 메모리 누수 Javascript 메모리는 원시값을 저장하는 콜 스택 메모리와 참조 값을 저장하는 힙 메모리로 구분된다. 실행 컨텍스트(GEC, FEC)가 콜 스택에 쌓이게 되면 참조 값이 있다면 힙 메모리에 데이터가 쌓이게 됩니다. 실행 컨텍스트가 차례대로 제거 된다면, 그 순서에 맞게 힙 메모리에 쌓인 데이터는 더이상 참조되지 않으므로 필요가 없어집니다. 이때 계속해서 힙 메모리에 불필요한 데이터가 메모리를 차지하게되면 메모리 누수로 인해 성능이 떨어지게됩니다. 메모리 누수? 사용하지 않는 메모리를 해제하지 못하여 계속 메모리를 점유하는 것 종합하자면, 가비지 컬렉터가 더이상 참조되지 않는 객체를 인지하고, 불필요한 메모리를 해제한다. 가..

1. 정의 자바스크립트 엔진이 자바스크립트를 실행할 때 원시 타입 및 참조 타입을 저장하는 메모리 구조로 콜 스택과 힙을 갖는다. 1-1 콜스택 원시타입 값과 함수 호출의 실행 컨텍스트(Execution Context)를 저장하는 곳이다. 1-2 힙(메모리 힙) 객체, 배열, 함수와 같이 크기가 동적으로 변할 수 있는 참조타입 값을 저장하는 곳이다. 2. 동작 원리 let a = 10; let b = 35; let arr = []; function func() { const c = a + b; const obj = { d: c }; return obj; } let o = func(); 위 코드를 콜 스택과 힙의 동작으로 확인해 보자. 제일 처음으로 GEC(Global Execution Context, 글..