[ALGOS STUDY] 2023-1-WEEK3 Priority Queue, Map, Set

Priority Queue

- 우선순위 큐 : 지정된 우선순위 규칙에 따라 우선순위가 큰 데이터를 먼저 반환

- 힙(heap) 자료구조 이용

• 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 완전이진트리의 형식으로 매순간 최대, 최소를 얻도록 정렬되어 있음 (모든 데이터가 정렬되어 있는 것은 아님.)
• 최댓값을 반환하는 최대 힙, 최솟값을 반환하는 최소 힙
• 최악의 경우에도 O(logN)을 보장함.

- STL 

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<자료형, 컨테이너형, 정렬기준> 변수명;
    return 0;
}

 

• 정렬은 내림차순이 기본
• 오름차순을 사용하기 위해서 정렬기준 자리에 함수를 만들어서 넣어주거나, greater<자료형>을 넣어주면 됨. 
• push() : 원소 추가
• pop() : 루트 노드 원소 삭재
• empty() : 우선순위 큐가 비어있는지 확인
• top() : 루트 노드 확인
• emplace() : 우선순위 큐에 원소 추가
• swap() : 우선순위 큐 두 개를 바꾸기
• size() : 우선순위 큐의 크기 반환

- 문제 풀이 예시 : 백준 1927 최소 힙 (https://www.acmicpc.net/problem/1927)

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, x, removeValue;
	priority_queue<int, vector<int>, greater<int>>q;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		if (!x)
		{
			if (q.empty()) cout << 0 << "\n";
			else
			{
				cout << q.top() << "\n";
				q.pop();
			}
		}
		else q.push(x);
	}
	return 0;
}

 

Map

- 맵 자료구조

• key : value 관계를 갖는 연관 컨테이너
• key 값을 기준으로 정렬됨.
• ¹⁾레드 블랙 트리(red-black tree) 자료구조 이용
• vector와 비교시 데이터를 추가할 때는 vector가 더 빠르지만 데이터 검색 시에는 map이 더 빠름.

- unordered_map

• key : value 관계를 갖는 연관 컨테이너
• 정렬되어 있지 않음
• ²⁾해시테이블 자료구조 사용
• 시간 복잡도 
  • 데이터 추가(insert) : 평균 O(1), 최악 O(N)
  • 데이터 삭제(erase) : 평균 O(1), 최악 O(N)
  • 데이터 검색([], find) : 평균 O(1), 최악 O(N)
  • 최악 : 해시 충돌이 계속 일어나는 경우

- STL

#include <iostream>
#include <map>
using namespace std;

int main()
{
    map<string, string>m;
    // map<자료형, 자료형> 변수명;
    return 0;
}

• 시간 복잡도 
  • 데이터 추가(insert) : O(logN)
  • 데이터 삭제(erase) : O(logN)
  • 데이터 검색([], find) : O(logN)
• 데이터 검색
  • m.find("A") : key 값이 존재하지 않을 경우 end() 주소 반환
  • m.at("A") : key 값이 존재하지 않을 경우 오류 반환
  • m["A"] : value가 0인 데이터를 추가해 결과 반환
• 데이터 추가
  • m.insert({"A", "1"})
  • m["A"] = 1
• 데이터 삭제
  • m.erase("A") :  특정 원소 삭제
  • m.clear() : 전체 원소 삭제

 

Set

- 세트 자료구조 

• key 값만을 가진 컨테이너
• key 값을 기준으로 정렬되며, key값 자체가 value인 경우 활용도가 높음.
• ¹⁾레드 블랙 트리(red-black tree) 자료구조 이용
• vector와 비교시 데이터를 추가할 때는 vector가 더 빠르지만 데이터 검색 시에는 set가 더 빠름.

- unordered_set

• key 값만을 가진 컨테이너
• 정렬되어 있지 않음
• ²⁾ 해시테이블 자료구조 사용
• 시간 복잡도 
  • 데이터 추가(insert) : 평균 O(1), 최악 O(N)
  • 데이터 삭제(erase) : 평균 O(1), 최악 O(N)
  • 데이터 검색([], find) : 평균 O(1), 최악 O(N)
  • 최악 : 해시 충돌이 계속 일어나는 경우

- STL

#include <iostream>
#include <set>
using namespace std;

int main()
{
    set<int>s;
    // set<자료형> 변수명;
    return 0;
}

• 시간 복잡도 
  • 데이터 추가(insert) : O(logN)
  • 데이터 삭제(erase) : O(logN)
  • 데이터 검색([], find) : O(logN)
• 데이터 추가 : s.insert(10)
• 데이터 검색 : s.find(11)
• 데이터 삭제
  • s.erase(20)  :특정 원소 삭제
  • s.clear() : 모든 원소 삭제

- 문제 풀이 예시 : 백준 11478 서로 다른 부분 문자열의 개수 (https://www.acmicpc.net/problem/11478)

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<string>result;
	string in;

	cin >> in;

	for (int i = 0; i < in.length(); i++)
	{
		string make = "";
		for (int j = i; j < in.length(); j++)
		{
			make += in[j];
			result.insert(make);
		}
	}
	cout << result.size();

	return 0;
}

 

1) 레드 블랙 트리(red-black tree) 자료구조

- 개념

• 데이터 추가/삭제가 발생해도 시간복잡도는 O(logN)
• 모든 노드는 빨간색 혹은 검색은
• 루트 노드와 모든 리프 노드는 검은색
• 빨간색 노드의 자식은 검은색 => 빨간색 노드가 연속 해서 나올수 없음. (No Double Red)
• 모든 리프 노드에서 Black Depth는 같음 (리프노드에서 루트 노드로 가는 경로에서 만나는 검은색 노드의 수는 같음.)

- Double Red 발생 시 해결 방법

• 부모의 형제 노드가 검정일 때 : Restructuring
• 부모의 형제 노드가 빨강일 때 : Recoloring

 

2) 해시테이블(hash table) 자료구조

- 개념

• key, value를 대응시켜 저장하는 데이터 구조
• 키를 통해 해당 데이터에 빠르게 접근 가능
• 해싱 : 키를 특정 계산식에 넣어 나온 결과를 사용해서 값에 접근하는 과정
• 키(key) : 해시 테이블 접근을 위한 입력 값
• 해시 함수 : 키를 해수 값으로 매핑하는 연산
• 해시 값 : 해시 테이블의 인덱스
• 해시 테이블 : 키-값을 연관시켜 저장하는 자료구조

- 해시 중복 문제 발생 시 해결 방법

• 개방 주소법 : 임의의 칸만큼 이동해서 비어있다면 해당 칸에 데이터 삽입 ex. 선형 탐사법, 제곱 탐사법, 이중 해싱
• 체이닝 : 해당 노드의 연결리스트 헤드에 새로운 노드 연결

---

ALGOS 스터디의 경우 팀원들이 만든 자료를 바탕으로 스터디를 진행합니다. 해당 주차는 제가 스터디 자료를 만들지 않았기 때문에 팀원의 자료 내 출처가 표기되었을 경우, 표기된 모든 출처를 옮겨 작성합니다.