민규의 흔적

2024년 7월 15일문제 링크 : 프로그래머스 - 이중우선순위큐문제 접근 최소 힙과 최대 힙을 다룰 수 있는지를 묻는 문제이다. 문제만 읽어보면 최소 힙과 최대 힙 성질을 모두 갖는 하나의 자료구조를 만드는 것을 요구하지만, 실제로는 최소 힙과 최대 힙 두 가지 자료구조를 모두 활용하여 하나의 자료구조처럼 사용해야하는 문제이다. (힙 자료구조와 우선순위 큐란? : https://ymg5218.tistory.com/120) 최소 힙, 최대 힙을 모두 선언하고 값을 삽입하는 연산이 들어올 때마다 해당 값을 최소 힙, 최대 힙에 모두 삽입한다.여기서, 라이브러리가 최소 힙만 지원해준다고 최대 힙을 따로 구현할 필요는 없다. 삽입하는 값에 -1을 곱해주어 최소 힙에 저장하면, 해당 값을 꺼낼 때마다 다시 -1..

2024년 7월 7일힙(Heap) 힙이란, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 기반의 자료구조이다. 부모 노드와 자식 노드의 일련된 대소 관계가 성립하는 구조를 보인다. 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리를 의미한다. 위 그림과 같이, 자식 노드를 가지고 있는 모든 부모 노드는 무조건 자식 노드보다 크거나 같은 값을 지니는 양상을 보인다. 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리를 의미한다. 위 그림과 같이, 자식 노드를 가지고 있는 모든 부모 노드는 무조건 자식 노드보다 크거나 같은 값을 지니는 양상을 보인다. 부모 노드와 자식 노드의 연결 관..