프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 책 내용 정리입니다.

요약

우선순위큐: 우선순위 높은 것을 먼저 삭제하는 큐

구현: 힙으로 하면 좋다

힙의 목적: 가장 큰/작은 원소 빠르게 찾기

힙의 규칙:

1. 자식은 부모보다 작다
2. 처음부터 채워져 있다 → 배열로 구현하기 좋음

23.1 도입

우선순위 큐

• 순서대로 기다리고 있는 자료들을 저장
• 우선순위가 가장 높은 자료가 가장 먼저 꺼내짐

구현

• 배열/연결리스트

  삽입: $O(1)$

  삭제: $O(N)$ : 모든 원소 순회하며 우선순위가 가장 높은 것 찾음

• 균형잡힌 이진 검색 트리

  원소들을 우선순위로 정렬해둔다.

  삽입, 삭제: $O(logN)$

• 힙 (heap)

  • 가장 큰(작은) 원소를 찾는 데 최적화된 이진 트리

    삽입, 삭제: $O(logN)$

  • 표준 라이브러리에 구현되어 있다.

23.2 힙의 정의와 구현

힙

• 특정 규칙을 만족하도록 구성된 이진 트리

• 최대 원소를 가능한 빠르게 찾을 수 있는 방법으로 설계

  → 단순한 알고리즘으로 효율적 동작

• 대소 관계 규칙: 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이다.

  • sibling 끼리의 대소관계는 제한되지 않음
  • 가장 큰 원소는 항상 트리의 루트에 있음

• 균형잡기 규칙

  1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.

  2. 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워져 있어야 한다.

     cf) level: 높이가 같은 노드들의 집합

     cf) 힙의 높이는 $O(logN)$

배열을 이용한 힙의 구현

             A[ (i-1) / 2 ]

            /

          A[i]

      /          \
 A[2i + 1]     A[2i + 2]

   

벡터로 구현 가능.

새 원소의 삽입

모양 규칙을 먼저 만족→ 대소 규칙 만족

1. 마지막에 원소 추가: 모양 규칙
2. 추가한 원소를 부모와 비교 후, 부모가 작다면 두 원소의 위치를 바꾸는 연산 반복 : 대소 규칙

[시간복잡도]

while문 내부가 한 번 수행될 때마다 트리에서 한 레벨 위로 올라감

∴ $O(logN)$ : 트리의 높이와 같다

최대 원소 꺼내기 (삭제)

1. 루트 삭제
2. 마지막 노드를 루트 자리에 올림
3. 루트의 두 자식 노드 중 더 큰 원소와 맞바꿈: 두 자손이 모두 자기 자신 이하일때까지

[시간복잡도]

while문 내부가 한 번 수행될 때마다 트리에서 한 레벨 아래로 내려감

∴ $O(logN)$ : 트리의 높이와 같다

다른 연산

힙 만들기

• N개의 원소를 텅 빈 힙에 순서대로 삽입해야 하는 경우
• $O(N)$에 힙으로 만듦: push_heap()을 N번 호출하는 $O(NlogN)$보다 빠름
• N개의 원소를 꺼내는 데 $O(NlogN)$이 걸림...

힙 정렬

• 주어진 배열을 힙으로 만든 뒤, 모든 원소들을 꺼내고, 반환 순서대로 나열
  • 힙에서 원소를 하나 꺼내면 힙을 담은 배열의 맨 뒤쪽에 한 칸이 비게 되므로, 최대 원소를 여기에 옮기면 추가 메모리 없이 정렬 가능
  • 최악의 경우에도 $O(NlogN)$

이미 힙에 들어 있는 원소 중 하나 증가시키기

• 힙을 이용해 우선순위 큐 구현 시 유용
• 새 원소를 삽입할 때처럼 변경된 원소를 위로 올려 주는 방식으로 구현
  • 각 원소가 힙의 어디에 위치하는지를 별도의 배열에 유지해야 함
  • 대부분 표준 라이브러리에서 지원하지 않음

23.3 문제: 변화하는 중간 값 (RUNNINGMEDIAN)

이진 검색 트리로 풀어도 되지만 구현이 복잡하다...

[힙으로 풀기]

숫자들을 정렬

앞의 절반을 최대 힙, 뒤의 절반을 최소 힙에 넣음

수열 길이가 홀수라면 최대 힙에 하나 더 넣음

그러면 다음을 만족

1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다
2. 최대 힙의 최대 원소는 최소 힙의 회소 원소보다 작거나 같다

그러면 이 수열의 중간 값은 최대 힙의 루트에 있음

삽입

1. 둘 중 한 힙에 숫자 추가해 1번 식 만족
2. 2번 식이 만족되지 않으면, 최대 힙의 최대 원소와 최소 힙의 최소 원소 맞바꿈

숫자를 하나만 추가했으므로 한 번만 숫자들을 바꿔도 2번 불변식 유지 가능

C++ STL priority_queue를 사용해보자.

//코드 23.4 힙을 이용해 변화하는 중간 값 문제를 해결하는 함수의 구현
int runningMedian(int n, RNG rng> {
	priority_queue<int, vector<int>, less<int> > maxHeap; 
	priority„queue<int, vector<int>, greater<int> > minHeap; 
	int ret = 0;
	// 반복문 불변식:
	// 1. maxHeap의 크기는 minHeap의 크기와 같거나 1 더 크다.
	// 2. maxHeap.topO (= minHeap.topO
	for(int cnt = 1; cnt <= n; ++cnt) {
		// 우선 l 번 불변식부터 만족시킨다. 
		if(maxHeap.size() == minHeap. sizeO) 
		maxHeap.push (rng .： next ()};
		else
		minHeap.push(rng.next(》);
		// 2번 불변식 이 깨졌을 경우 복구하자. 
		if(!minHeap.empty() && ImaxHeap.empty() && minHeap.top() < maxHeap.top()) {
			int a = maxHeap.top(), b = minHeap.top(); 
			maxHeap.pop(); minHeap.popO; 
			maxHeap.push(b); 
			minHeap.push(a);
		}
		ret = (ret + maxHeap.topO) % 20090711;
	}
	return ret;
}

[시간복잡도]

for 문 내부의 수행 시간을 힙의 추가/삭제 연산이 지배

∴ $O(NlogN)$