데이터의 개수가 N이기 때문에 가운데 값을 추출하는데 lgN의 시간으로 해결해야 한다. 우선순위 큐 STL은 top 값만 알 수 있고, 그 뒤의 값은 알 수가 없다. 힙 구조로 되어있기 때문에 최대, 최소값만 알 수 있게 해놓은 것 같다 따라서 가운데 값을 한 번에 알기 위해서는 우선순위 큐 2개를 사용하는 것이다. 하나는 최대 힙, 나머지는 최소 힙으로 구성한다. 크기는 최대 힙의 가장 큰 값 < 최소 힙의 가장 작은 값을 유지하는 구조를 가져야 한다. 짝수개의 데이터가 들어왔을 때는 가운데 값 중 작은 값을 추출해야기 때문에 반드시 최대 힙의 가장 큰 값이 테스트 케이스의 답이 된다. 1) 두 개의 힙 사이즈가 같다면, 최대 힙으로 넣는다 2) 두 개의 힙 사이즈가 다르다면 최소 힙으로 넣는다 두 개..

큐는 FIFO 성질을 가진 자료구조다. 즉 먼저 들어간 데이터가 먼저 나오게 된다. 스택 2개를 활용해서 큐를 구현할 수 있다. 스택 하나는 push 용도, 나머지 하나는 pop할 때 이용된다. 만일 pop 명령이 들어온다면 push 때 담긴 스택을 위에서부터 빼서 스택 2번에 넣을 수 있다. 그리고 스택 2에서 위에서부터 pop하면 큐와 똑같이 동작시킬 수 있다

캐시가 필요한 이유 : 대부분 프로그램은 한번 사용한 데이터를 다시 사용할 가능성이 높고, 그 주변의 데이터도 곧 사용할 가능성이 높은 데이터 지역성을 가지고 있다. 데이터 지역성을 활용하여 메인 메모리에 있는 데이터를 캐시 메모리에 불러와 두고, CPU가 필요한 데이터를 캐시에서 먼저 찾도록 하면 시스템 성능을 향상시킬 수 있다. Cache hit ratio : cache hit ratio : 적중률 = (캐시히트횟수)/(전체 참조횟수) cache hit : 참조하려는 데이터가 캐시에 존재할때 캐시 히트 cache miss : 참조하려는 데이터가 캐시에 존재하지 않을때 캐시 미스 평균접근시간: cache hit ratio * 캐시접근시간 + (1-cache hit ratio) *메인 메모리 접근시간 단..

최소 힙을 구현해서 새로운 데이터가 들어가는 시간복잡도를 lgN으로 처리해야만 한다 문제: https://www.acmicpc.net/problem/1715 깃허브주소: https://github.com/surinoel/boj/blob/master/1715.cpp

우선순위 큐는 '우선순위'를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 많이 활용된다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. 최대힙은 부모가 자식보다 값이 큰 이진 트리를 의미한다 1. 우선순위 큐의 삽입 1) 배열 맨 끝에 삽입한다 2) 부모와 비교해서 swap을 한다. 가능하다면 루트까지 진행한다 3) 상향식 구조 2. 우선순위 큐의 삭제 1) 0번 인덱스를 추출한다 2) 맨 마지막 원소를 0번으로 넣는다 3) 하향식 구조로 자식들을 비교하면서 0번 인덱스의 기존 위치를 찾는다 #include #define SIZE 1000 typedef struct { int heap[SIZE]; int count; } Pri..