위 글은 큰돌의 터전 님의 강의자료를 참조해서 정리하고 제가 알고리즘을 풀면서 더 추가적으로 사용할 만한 내용들을 정리한 글입니다.
알고리즘 풀이 강의로 큰돌의 터전님의 강의 강력 추천드립니다.
강의링크
map
map은 고유한 키를 기반으로 키 - 값(key - value) 쌍으로 이루어져 있는 정렬된(삽입할 때마다 자동 정렬된) 연관 컨테이너입니다.
레드 - 블랙트리로 구현됩니다.
레드 - 블랙 트리로 구현되어있기 때문에 삽입, 삭제, 수정, 탐색이 O(logN)의 시간복잡도를 가집니다.
고유한 키를 갖기 때문에 하나의 키에 중복된 값이 들어갈 수 없으며 자동으로 오름차순 정렬되기 때문에 넣은 순서대로 map을 탐색할 수 있는 것이 아닌 아스키코드순으로 정렬된 값들을 기반으로 탐색하게 됩니다.
또한 대괄호 연산자 [] 로 해당 키로 직접 참조할 수 있습니다. 예를 들어서 "이승철" : 1, "김현영" : 2 이런식으로 string : int 형태로 값을 할당해야 할 때 있죠?
그럴 때 map을 씁니다. 맵의 키와 value는 string이나 int 뿐만 아니라 다양한 값이 들어갈 수 있습니다.
- 레드블랙트리 : 균형 이진 검색 트리이며 삽입, 삭제, 수정, 탐색에 O(logN)의 시간복잡도가 보장됨.
#include <bits/stdc++.h>
using namespace std;
map<string, int> mp;
string a[] = {"토끼", "거북이", "음바페"};
int main()
{
for (int i = 0; i < 3; i++)
{
mp.insert({a[i], i + 1});
mp[a[i] = i + 1;
}
// mp에 해당 키가 없다면 0으로 최고하 되어 할당된다. (int인 경우)
// 만약 mp해당키가 있는지 확인하면서 0으로 할당하고 싶지 않다면 find사용해야한다. 되어서 출력이 된다.
//대괄호 이용해서 수정
mp["큰돌"] = 4;
cout << mp.size() << '\n';
mp.erase("큰돌"); //큰돌이라는 key를 가진 걸 삭제한다.
cout << mp["큰돌"] << '\n';//여기선 큰돌에 해당하는 key가 없기 때문에 0이 할당
auto it = mp.find("큰돌");
if (it == mp.end()) //find했는데 없다면 map의 end()에 해당하는 이터레이터 반환한다.
cout << "I can't find 큰돌\n";
mp["큰돌"] = 100; // 큰돌이라는 key의 value로 100을 준다.
it = mp.find("큰돌");
if (it != mp.end())
cout << (*it).first << " : " << (*it).second << '\n';
for (auto it : mp)
{
cout << (*it).first << " : " << (*it).second << '\n';
}
for (auto it = mp.begin(); it != mp.end(); it++)
{
cout << (*it).first << " : " << (*it).second << '\n';
}
mp.clear(); // 모든 요소 삭제
return (0);
}
/*
0
4
I can't find
큰돌
큰돌 : 100
토끼 : 1
큰돌 : 100
음바페 : 3
거북이 : 2
토끼 : 1
큰돌 : 100
음바페 : 3
거북이 : 2
*/메소드
mp.insert({key, value}) : map 에 {key, value} 를 집어 넣는다.
mp.size() : map에 있는 요소들의 개수를 반환합니다.
mp.erase(key); :해당 키에 해당하는 요소를 지웁니다.
mp.find(key)
map에서 해당 key를 가진 요소를 찾아 해당 이터레이터를 반환합니다. 만약 못찾을 경우 mp.end() 해당 map의 end() 이터레이터를 반환합니다.
mp.clear(); : map에 있는 요소들을 다 제거합니다.
map 사용법
[key] = value
대괄호 []를 통해 key에 해당하는 value를 할당합니다.
[key]
대괄호 []를 통해 key를 기반으로 map에 있는 요소를 참조한다.
만약 map에 해당 키에 해당하는 요소가 없다면 0 또는 빈문자열로 초기화가 되어 할당됩니다. (int는 0, string이나 char은 빈 문자열로 할당됩니다.) 할당하고 싶지 않아도 대괄호[]로 참조할경우 자동으로 할당되기 때문에 조심해야 합니다.
for(auto it : mp)
범위기반 for루프로 map에 있는 요소들을 순회합니다. map을 순회할 때는
key는 first, value는 second로 참조가 가능합니다.
for(auto it = mp.begin(); it != mp.end(); it++)
map은 이터레이터로 순회할 수 있습니다.
주의 사항
map의 경우 index만 참조를 해도 map의 값이 생성되서 빈 문자열이 생기게 됩니다. 따라서 map의 요소가 있는지 없는지 검사를 find를 이용해서 하고 그 값을 넣어주면 된다.
또한 map은 key값을 기준으로 정렬이 된다. 이 것을 염두하고 코드를 작성하는 것이 좋다.
unorderded_map
앞서서 나온 map은 정렬이 되는 map 이지만 unordered_map은 정렬 되지 않는 map이며 메서드는 map과 동일합니다.
map과 unordered_map을 비교하면 다음과 같습니다.
- map : 정렬이 됨 / 레드블랙트리기반 / 탐색, 삽입, 삭제에 O(logN)이 걸림
- unordered_map : 정렬이 안됨 / 해시테이블 기반 / 탐색, 삽입, 삭제에 평균적으로 O(1), 가장 최악의 경우 O(N)
unordered_map 은 다음과 같이 씁니다.
#include <unordered_map>
int main()
{
umap["bcd"] = 1;
umap["aaa"] = 1;
umap["aba"] = 1;
for(auto it : umap)
{
cout << it.first << " : " << it.second << '\n';
}
}
/* 정렬이 되지 않는다.
aba : 1
aaa : 1
bcd : 1
*/얼핏보면 정렬이 필요로 하지 않은 문제에는 unordered_map을 써야 할 것같지만 제출해보면 시간초과가 나기도 합니다. 이는 가장 최악의 경우 O(N)이기 때문이죠. 그냥 되도록 map을 쓰는 것을 권장합니다.
Set
셋(set)은 고유한 요소만을 저장하는 컨테이너 입니다. 중복을 허용하지 않습니다. map처럼 {key, value}로 집어넣지 않아도 되며 다음 코드처럼 pair나 int형을 집어넣어서 만들 수 있습니다. 중복된 값은 제거 되며 map과 같이 자동 정렬됩니다. 메서드는 map과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int main()
{
set<pair<string, int>> st;
st.insert({"test", 1});
st.insert({"test", 1});
st.insert({"test", 1});
st.insert({"test", 1});
cout <<st.size() <<"\n";
set<int> st2;
st2.insert(2);
st2.insert(1);
st2.insert(2);
for(auto it : st2)
{
cout << it << '\n';
}
}
/* 1 1 2 */
multiset
multiset은 중복되는 요소도 집어넣을 수 있는 자료구조 입니다. key, value형태로 집어 넣을 필요도 없고 넣으면 자동으로 정렬된다. 메서드는 역시 map과 같습니다.
#include <bits/stdc++.h>
using namespace std;
multiset<int> s;
int main()
{
for(int i = 5; i >= 1; i--)
{
s.insert(i);
s.insert(i);
}
for(int it : s) cout << it << " ";
cout << '\n';
return 0;
} /* 1 1 2 2 3 3 4 4 5 5 */
Uploaded by
N2T