공부방

Heap이란?heap은 우선 순위 큐를 구현하는 자료구조로 이진 트리를 기반으로 구현된다. 부모 노드가 자식 노드보다 큰 경우 최대 힙, 부모 노드가 자식 노드보다 작은 경우 최소 힙이라고 한다. 힙의 삽입 및 삭제 연산은 O(logn)의 시간 복잡도로 이루어진다. 파이썬에 내부에서 사용 방식heapq 모듈을 이용하여 사용할 수 있다. 삽입 (heappush), 삭제 (heappop), 특정 배열을 힙 형태로 만들어주는 함수 (heapify) 지원heappop을 사용하면 배열 내의 가장 작은 값이 나오지만, 값이 삭제된다. 만약 삭제되길 원하지 않는다면 배열의 첫번째 원소에 접근하는 방식으로도 사용 가능하다. 기본적으로 최소힙만 지원하기 때문에 최대힙을 구현하기 위해서는 들어가는 값에 -를 곱해주어야 ..

https://leetcode.com/problems/minimum-size-subarray-sum/description/자연수를 담고 있는 리스트 nums와 목표 자연수 target이 주어진다nums의 subarray 중, subarray 내의 모든 원소의 합이 target 이상이면서 길이가 가장 짧은 subarray의 길이를 구하는 문제아이디어1. subarray의 시작 지점이 고정이라면, subarray의 합을 늘리기 위해 끝 지점을 늘려가면서 탐색할 수 있음2. subarray의 끝 지점을 늘려가다 합이 target 보다 같거나 커지면 더 이상 subarray를 늘려볼 필요가 없음3. subarray의 합을 줄이기 위해서는 시작 지점을 늘린다-> 기본적인 two-pointer 흐름이니까 기억해둘 ..