말랑말랑한 개발자 이야기

[백준 11000번] 강의실 배정 www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ..

[백준 1655번] 가운데를 말해요 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하..

[코테를 위한 압축 개념] C++ STL 힙(Heap), 우선순위 큐(Priority queue) Heap Heap(힙)은 이진 트리 자료구조이다. 사진으로 보면 이해가 빠르다. - index 0은 최상단 노드임을 의미한다. - i 번째 노드의 자식 노드는 i * 2 + 1 번째 노드와 i * 2 + 2 번째 노드가 된다. - i 번째 노드의 부모 노드는 (i - 1) / 2 번째 노드가 된다. - 부모노드는 항상 자식 노드보다 작거나 같다. / 크거나 같다. 위 사진에서 트리 구조를 살펴보면 부모노드는 자식노드 보다 작은 규칙이 있다. 이러한 구조를 Min Heap이라고 한다. Heap은 두가지의 경우로 나뉘는데 위 사진과 반대로 부모가 자식보다 항상 큰 규칙을 가지면 Max Heap이 된다. 이러한 ..