힙
-
프로그래머스 코딩테스트 - 디스크 컨트롤러코딩테스트 풀이 2024. 12. 1. 18:21
2024.11.29 - [프로그래머스 데브코스: 클라우드 기반 웹 프론트엔드 3기] - Javascript로 Heap을 구현해보자 Javascript로 Heap을 구현해보자힙이란?완전 이진 트리의 일종정렬, 우선순위 큐, 스케쥴링 등 다양한 알고리즘에 사용된다.용어 정리부모 노드자식 노드루트 노드리프 노드레벨높이특정 노드의 상위특정 노으의 하위트리의yoolabong.tistory.com지난 포스팅 내용인 heap 자료구조를 사용하는 가장 대표적인 예시인 스케줄링과 관련있는 문제라 선택해서 풀어봤다. 문제 설명https://school.programmers.co.kr/learn/courses/30/lessons/42627?language=javascript 프로그래머스SW개발자를 위한 평가, 교육, 채용까..
-
Javascript로 Heap을 구현해보자프로그래머스 데브코스: 클라우드 기반 웹 프론트엔드 3기 2024. 11. 29. 11:38
힙이란?완전 이진 트리의 일종정렬, 우선순위 큐, 스케쥴링 등 다양한 알고리즘에 사용된다.용어 정리부모 노드자식 노드루트 노드리프 노드레벨높이특정 노드의 상위특정 노으의 하위트리의 최상단트리의 말단루트 ~ 리프트리의 깊이0부터 시작리프 ~ 루트트리의 높이1부터 시작 종류최대 힙부모 노드의 값 >= 자식 노드의 값항상 부모 노드의 값이 자식 노드의 값보다 크거나 같음최소 힙부모 노드의 값 항상 부모 노드의 값이 자식 노드의 값보다 작거나 같음활용 예시삽입/삭제 정렬 시간복잡도 삽입삭제순서 없는 배열O(1)O(n)순서 없는 연결 리스트O(1)O(n)정렬된 배열O(n)O(1)정렬된 연결 리스트O(n)O(1)힙O(logn)O(logn)우선순위 큐배열, 연결리스트, 힙으로 구현하능하지만 힙이 가장 효율적이다.최단..