반응형 Study/CS8 [자료구조] 우선순위큐(Priority Queue)에 사용되는 Heap 자료구조 서론 우선순위큐를 사용하며 이 자료구조를 정확히 이해하기 위해선 그 전에 힙을 완벽히 이해하여야 겠다는 생각이 들었다. 이전과 같이 모르는 것을 그냥 넘어가는 일이 없도록 하자. Heap Priority Queue 데이터에 가중치를 두어 가중치의 오름차순 또는 내림차순으로 정렬한 큐. 주로 시뮬레이션 시스템, 작업 스케줄링에 사용. 배열 또는 연결 리스트로도 구현이 가능하지만 힙 자료구조를 사용하는 것이 가장 효과적. 리스트를 사용하여 구현한 경우 삽입의 시간 복잡도는 O(1), 삭제의 시간 복잡도는 O(n). Heap을 사용하여 구현한 경우 삽입과 삭제 모두 시간 복잡도는 O(logN) Heap 자료구조의 개념 배열을 기반으로 한 완전 이진 트리로 구성. 일반적 이진 트리와 다르게 중복된 값을 허용. .. 2021. 10. 25. [OS] 교착상태(DeadLock)란? 교착상태란? 다중프로그래밍을 지원하는 프로세스는 한정된 데이터를 읽고 쓰기 위해 경쟁하게 된다. 이 경쟁 과정에서 생길 수 있는 문제를 예방하기 위해 데이터는 프로세스가 점유 상태라면 다른 프로세스의 접근을 막는 방법을 주로 사용하게 되는데 그 결과 같은 두개의 데이터를 필요로 하는 두 프로세스가 각각 하나씩 점유하게 되면 무한정 대기상태에 빠지게 되는데 이러한 상태를 교착상태라 한다. 교착 상태가 생기기 위한 조건 교착상태는 아래의 네가지 조건을 충족해야 일어난다 상호배제(mutual exclusion) 한 리소스는 한번에 한 프로세스만이 사용 할 수 있음(화장실 키) 점유하며 대기(hold-and-height) 프로세스는 최소한 하나의 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기.. 2021. 9. 2. 이전 1 2 다음 반응형