본문 바로가기

priority_queue1

[우선순위 큐] 최솟값 or 최댓값 찾기 알고리즘(feat. deque) 최솟값, 최댓값 찾기 문제에서 정렬을 사용할 수 없다면, 우선순위 큐를 생각하세요 들어가며시간복잡도를 측정하는 문제 중에서는 까다로운 문제들이 많습니다. 특히 정렬이 필요한 경우인데, 정렬은 기본적으로 NlogN의 시간복잡도를 가집니다. 특정 문제의 요구사항에서는 적어도 N의 시간복잡도를 요구하는 부분이 있습니다. 이럴 땐 우선순위 큐를 사용하면 logN의 시간복잡도를 가질 수 있습니다. 문제백준 11003 처음에는 문제 자체가 이해되지 않았습니다. 슬라이딩 윈도우 형태로 고정된 구간이 이동하면서 그 중 최소값을 찾는 문제더라구요. N의 최대 범위가 5,000,000이므로 정렬을 사용하게 되면 시간초과입니다.저는 문제를 두가지 파트로 나눴습니다. 첫 번째는 구간이 이동함에 따라 최소값 리스트를 갱신해주는.. 2025. 4. 13.

이전 1 다음

티스토리툴바