말씀해주신 것처럼, heap은 완전 이진 트리를 통해 최솟값을 항상 맨 위 노드에 위치하게 하므로 삽입, 삭제에 O(logN)의 시간 복잡도를 가지게 됩니다.
deque는 삽입, 삭제에 O(1)의 시간 복잡도를 가지므로, 최솟값을 항상 찾아야 되는 상황 or 최솟값부터 들어오지 않는 상황이 아니라면 deque를 사용하시는 것이 이득입니다 :)
9019번 - DSLR
말씀해주신 것처럼, heap은 완전 이진 트리를 통해 최솟값을 항상 맨 위 노드에 위치하게 하므로 삽입, 삭제에 O(logN)의 시간 복잡도를 가지게 됩니다.
deque는 삽입, 삭제에 O(1)의 시간 복잡도를 가지므로, 최솟값을 항상 찾아야 되는 상황 or 최솟값부터 들어오지 않는 상황이 아니라면 deque를 사용하시는 것이 이득입니다 :)
댓글을 작성하려면 로그인해야 합니다.
ksm30546 3년 전
하루종일 시간초과로 헤맸는데.. 마지막에 형변환 없애고 역추적 알고리즘 구현했는데도 계속 시간초과 나오길래..
heap이 이진트리로 정렬해주는 알고리즘이니까 들어가면 뭐라도 작업하지않을까? deque는 작업을 안하니 deque로 바꿔볼까? 했더니 정답뜸.. 내 3시간..