기회개발자

안녕하세요 기회개발자 기개 입니다.

오늘은 C++에서 사용하는 priority_queue에 대해 소개해보려고 합니다.

priority_queue를 직접 구현할 때에는 Heap을 사용하게 됩니다.

Heap이 무엇인지를 알아보고, heap으로 어떻게 priorty_queue를 구현하는지 알아보겠습니다.

그리고 STL 중 하나인 priority_queue의 사용법을 알아보도록 하겠습니다.

1. Heap이란

2. priority_queue를 Heap으로 구현?

최대힙, 최소힙의 개념을 보게 되면 조건(최댓값, 최솟값)에 따라 pop을 할 때 가장 먼저 나오게 합니다.

priority_queue를 생각해보면 조건을 사용자가 정한 우선순위(조건)에 따라 힙을 적용하면 된다는 것을 알 수 있게 됩니다.

3. priority_queue의 사용법 (내장함수)

priority_queue에는 데이터의 삽입, 삭제 등을 편하게 하기 위한 내장함수들이 존재합니다.

기본적으로 priority_queue를 선언하는 방법을 살펴보고 자주 사용하는 내장함수들에 대해서 알아봅시다.

#include <queue>

using namespace std;

priority_queue<int> pq; // <>안에 삽입할 데이터의 자료형을 지정해줍니다.

1) 데이터의 삽입

데이터를 삽입할 때마다 앞서서 살펴본 heap의 규칙에 따라 삽입이 됩니다.

pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(5); // 결과 {5, 4, 3, 2, 1}

2) 데이터의 삭제

최상단 노드를 삭제합니다.

pq.pop(); // 최상단에 있던 5가 삭제됩니다.

3) 데이터의 접근

priority_queue는 인덱스로 접근이 불가능합니다.

가장 최상단 노드에 어떤 값이 있는지만 알 수 있습니다.

pq.top() // 최상단 노드의 값인 4를 확인할 수 있다.

4) 이외에 유용한 내장함수

priority_queue에 데이터가 있는지, 몇 개의 데이터를 가지고 있는지를 알 수 있는 내장함수가 있습니다.

pq.empty(); // 데이터가 존재한다면 0 반환, 존재하지 않는다면 1 반환
pq.size(); // 데이터의 갯수 반환 | 결과 4

5) 응용

typedef struct st // 우선순위 정할 정보
{
    string word;
    int id;
}DATA;

struct compare // 부등호 방향이 set, map과 반대
{
	// id가 클수록 우선순위, id가 같다면 사전상 앞에 있을 경우 우선순위
    bool operator()(DATA a, DATA b) const{   
        if(a.id < b.id) return true; // id 내림차순(큰게 앞으로)
        else if(a.id == b.id && a.word > b.word) return true; // word 오름차순(작은게 앞으로)
        return false;
    }
};

// 선언, 직접 만든 비교 구조체(compare)을 넣을 경우 vector<{data_type}>을 중간에 넣어줘야 한다.
priority_queue<DATA, vector<DATA>, compare> pq;

DATA d1 = {"abc", 3};
DATA d2 = {"asdf", 2};

pq.push(d1);
pq.push(d2);

pq.top().word; // "asdf" 를 확인한다.
pq.pop(); // d2가 pq에서 삭제된다.

// 초기화 팁 (내장함수 clear() 없음)
while(!pq.empty()) pq.pop(); // 전부 꺼내주는 방법이 있지만 데이터 양이 많을 경우 오래 걸린다.

pq = {}; // 그냥 이렇게 해주면 초기화가 된다.

안녕하세요 기회개발자 기개입니다.

오늘은 Hash로 사용할 수 있는 unordered_set과 unordered_map에 대해서 알아보려고 합니다.

Hash는 빠른 검색을 할 때 사용하기 매우 유용합니다.

검색을 할 때, 해시충돌이 많이 일어나지 않는 이상

O(1)의 시간이 걸리게 되니 코딩테스트할 때 값이 존재하는지 안하는지를 파악하는데 좋습니다.

set과 map의 차이 처럼 차이는 한 가지 밖에 없습니다.

unordered_set은 key만 가지고, unordered_map은 key와 value를 가지고 있습니다.

Hash에 대해서 알아보고, unordered_set과 unordered_map의 사용법에 대해서 알아보도록 하겠습니다.

1. Hash란

2. unordered_set과 unordered_map의 사용법(내장함수)

데이터의 검색과 삽입 및 삭제 등을 편하게 하기 위한 내장함수들이 존재합니다.

unordered_set과 unordered_map은 가지고 있는 내장함수가 동일합니다.

기본적으로 unordered_set과 unordered_map을 선언하는 방법을 살펴보고 자주 사용하는 내장함수들에 대해서 알아봅시다.

#include <unordered_set>
#include <unordered_map>
#include <string>

#define MAX 50000

using namespace std;

unordered_set<string> s;
unordered_map<string> m;

s.reserve(MAX); // 삽입될 데이터의 총량을 알고 있다면, 미리 공간을 확보해
m.reserve(MAX); // 사이즈를 늘릴때마다 재배치하는 시간을 줄일 수 있다.

1) 데이터의 삽입

데이터를 삽입하면 내부에서 해쉬함수를 돌려나온 key에 데이터를 저장합니다.

s.insert("abc");
m.insert({"def", 3});

2) 데이터의 삭제

해당 데이터의 key에 접근해 삭제를 합니다.

s.erase("abc");
m.erase("def");

3) 데이터의 검색

unordered_set과 unordered_map은 순서가 없기 때문에 인덱스로 접근이 불가능합니다.

검색을 할 때는 find() 내장함수를 사용하여 접근할 수 있습니다.

find() | 찾고자 하는 데이터의 위치를 찾습니다.

auto it = s.find(id);
if(it == s.end()) // key값으로 id가 존재하지 않을 경우 처리
{
	// TODO
}
else { // key값으로 id가 존재할 경우 처리
	// TODO
}

auto it2 = m.find(id);
if(it2 == m.end()) // key값으로 id가 존재하지 않을 경우 처리
{
	// TODO
}
else { // key값으로 id가 존재할 경우 처리
	// TODO
}

4) 이외에 유용한 내장함수

s.empty(); // 데이터가 존재한다면 0 반환, 존재하지 않는다면 1 반환
s.size(); // 데이터의 갯수 반환
s.clear(); // 초기화 | 결과 {}

5) 응용

typedef struct st{ // value에 넣어줄 정보
    int grade;
    int gender;
    int score;
}DATA;

unordered_map<int, DATA> db; // 선언

db.clear(); // 초기화
db.reserve(ADD_MAX); // ADD_MAX 만큼 공간을 늘려줌

db.insert({mId, {mGrade, gender, mScore}}); // 삽입

auto it = db.find(mId); // mId라는 key를 가지고 있는지 검색
if(it == db.end()) // 찾지 못했을 때 처리

// 찾았을 때 value에 넣어둔 정보 가져와 사용하기
int grade = it->second.grade;
int gender = it->second.gender;
int score = it->second.score;

db.erase(mId); // 삭제

안녕하세요 기회개발자 기개 입니다.

오늘은 C++에서 binary search tree처럼 사용할 수 있는 set과 map에 대해 소개해보려고 합니다.

set과 map의 차이점은 한 가지만 존재하여 같이 다루려고 합니다.

둘의 차이점을 알아보고 binary search tree가 무엇인지, set 과 map의 사용법에 대해 알아봅시다.

1. set과 map의 비교

2. binary search tree 란

1) 삽입 O(log_2​ N) {5, 7, 2, 6, 4, 3} 을 순서대로 넣는다고 하면, 처음에 놓는 5를 root 노드로 배치한다. 7은 5보다 크니 5의 오른쪽에 배치한다. 2는 5보다 작으니 5의 왼쪽에 배치한다. 6은 5보다 크니 5의 오른쪽인 7과 비교를 하면 작으니 7의 왼쪽에 배치한다. 4는 5보다 작으니 5의 왼쪽인 2와 비교를 하면 크니 2의 오른쪽에 배치한다. 3은 5보다 작으니 5의 왼쪽인 2와 비교를 하면 크니 2의 오른쪽인 4와 비교를 하면 작으니 4의 왼쪽에 배치한다. 2) 삭제 O(log_2​ N) ① 자식이 없는 노드 지울 때 그냥 삭제하면 됨 ② 자식노드가 하나인 노드 지울 때 해당 자식노드를 삭제하는 노드의 parent와 연결해주고, 해당 노드를 삭제 ③ 자식노드가 두개인 노드 지울 때 2가지 방법이 있다. 오른쪽 자식 중에 가장 작은 값을 삭제하는 노드 자리로 옮기고 옮긴 노드를 삭제할 때 ①,②,③의 규칙을 따라 다시 진행. 왼쪽 자식 중에 가장 큰 값을 삭제하는 노드 자리로 옮기고 옮긴 노드를 삭제할 때 ①,②,③의 규칙을 따라 다시 진행. 3) 검색 O(log_2​ N) root 노드부터 비교를 진행 찾고자 하는 노드의 우선순위가 비교하는 것보다 작을 경우 왼쪽으로, 클 경우에는 오른쪽으로 이동하며 검색을 진행한다.

3. set과 map 사용법 (내장함수)

데이터의 삽입, 삭제, 검색 등을 편하게 하기 위한 내장함수들이 존재합니다.

set과 map은 가지고 있는 내장함수가 동일합니다.

기본적으로 set과 map을 선언하는 방법을 살펴보고 자주 사용하는 내장함수들에 대해서 알아봅시다.

#include <set>
#include <map>
#include <string>

using namespace std; // STL을 사용할 때 선언해주면 사용하기 편리합니다.

set<string> s; // key의 자료형 지정
map<string, int> m; // key와 value의 자료형 지정

1) 데이터의 삽입

위에서 정리한 binary search tree의 규칙에 맞게 데이터들이 삽입 됩니다.

s.insert("abc");
m.insert({"def", 3});

2) 데이터의 삭제

위에서 정리한 binary search tree의 규칙에 맞게 데이터들이 삭제 됩니다.

s.erase("abc");
m.erase("def");

3) 데이터의 접근

set과 map은 binary search tree에 따라 규칙적으로 데이터들이 배치되어 있어 인덱스로도 접근이 가능합니다.

front()와 back()은 없지만 begin()과 end()가 있어서 순회를 할 때 사용할 수도 있습니다.

begin() | root 노드를 포인터로 가르킵니다.

s.begin(); // root 노드의 위치를 가르킵니다. *s.begin() == s.front()
m.begin(); // root 노드의 위치를 가르킵니다. *m.begin() == m.front()

end() | 데이터의 끝을 포인터로 가르킵니다.

s.end(); // 데이터의 끝을 가르킵니다. *(s.end() - 1) == s.back()
m.end(); // 데이터의 끝을 가르킵니다. *(m.end() - 1) == m.back()

find() | 찾고자 하는 데이터의 위치를 찾습니다.

auto it = s.find(id);
if(it == s.end()) // key값으로 id가 존재하지 않을 경우 처리
{
	// TODO
}
else { // key값으로 id가 존재할 경우 처리
	// TODO
}

auto it2 = m.find(id);
if(it2 == m.end()) // key값으로 id가 존재하지 않을 경우 처리
{
	// TODO
}
else { // key값으로 id가 존재할 경우 처리
	// TODO
}

4) lower_bound, upper_bound (set, map의 핵심)

lower_bound : 찾고자 하는 key 값 이상인 것들 중 가장 작은 key 값을 찾는다.

upper_bound : 찾고자 하는 key 값을 초과하는 것들 중 가장 작은 key 값을 찾는다.

auto it = s.lower_bound(id);
if(it == s.end()) // 찾지 못했을 때 처리
{
	// TODO
}
else // 찾았을 때 처리
{
	// TODO
}

auto it2 = m.upper_bound(id);
if(it2 == s.end()) // 찾지 못했을 때 처리
{
	// TODO
}
else // 찾았을 때 처리
{
	// TODO
}

5) 이외에 유용한 내장함수

s.empty(); // 데이터가 존재한다면 0 반환, 존재하지 않는다면 1 반환
s.size(); // 데이터의 갯수 반환
s.clear(); // 초기화 | 결과 {}

6) 응용

typedef struct st{ // key에 넣을 구조체
    int score;
    int id;
}ST;

struct compare { // 이 기준에 따라 우선순위를 정함
    bool operator()(ST a, ST b) const {
        if(a.score < b.score) return true;
        else if(a.score == b.score && a.id < b.id) return true;
        return false;
    }
};

set<ST, compare> students[GRADE][GENDER]; // 선언

students[mGrade][gender].insert({mScore, mId}); // 삽입

auto it = students[mGrade][gender].end();
--it;
it->id; // 우선순위 가장 낮은 것의 id를 가져옴

students[grade][gender].erase({score, mId}); // 삭제
if(students[grade][gender].empty()) // 비어있을 때 처리

students[grade][gender].begin()->id; // 우선순위 가장 높은 것의 id

auto it2 = students[grade][gender].lower_bound({mScore, -1}); // mScore이상의 score를 가진 것을 가르킴
--it2; // mScore 보다 작은 것 중 가장 큰 것을 가르키게 됨.

안녕하세요 기회개발자 기개 입니다.

오늘은 C++에서 char 배열 대신 자주 사용하는 string에 대해 소개해보려고 합니다.

앞서서 배열과 vector를 비교했는데요, vector와 string은 꽤나 유사합니다.

왜 char 배열 대신 string을 사용할까요?

우선, char 배열과 string의 비교가 필요할 것 같습니다.

char 배열과 비교해서 sring의 장점이 무엇인지, 어떤 상황에서 사용하면 좋을지를 알아본 후 사용법에 대해 알아봅시다.

1. char 배열과 string의 비교

2. 어떤 상황에서 string을 사용하는게 좋을까

3. string의 사용법 (내장함수)

string에는 데이터의 삽입, 삭제, 접근 등을 편하게 하기 위한 내장함수들이 존재합니다.

기본적으로 string을 선언하는 방법을 살펴보고 자주 사용하는 내장함수들에 대해서 알아봅시다.

#include <string>

using namespace std; // STL을 사용할 때 선언해주면 사용하기 편리합니다.

string s;

1) 데이터의 삽입

데이터들이 순차적으로 삽입되기 때문에 마지막에 삽입된 데이터 뒤에 삽입을 합니다.

s = "abcde";
s += "f";
s.push_back('g') // 결과 {'a', 'b', 'c', 'd', 'e', 'f', 'g'}

2) 데이터의 삭제

데이터들이 순차적으로 삽입되기 때문에 마지막에 삽입된 데이터를 삭제합니다.

s.pop_back(); // 가장 마지막에 삽입했던 'g'가 삭제됩니다.

3) 데이터의 접근

string은 인덱스로 데이터에 접근이 가능하지만,

순차적으로 데이터를 삽입하기에 데이터의 맨 앞과 맨 뒤를 접근할 수 있는 내장함수가 존재합니다.

front() | string에 가장 먼저 삽입된 데이터를 알려줍니다.

s.front(); // 'a'를 반환해 줍니다.

back() | string에 가장 마지막에 삽입된 데이터를 알려줍니다.

s.back(); // 'f'를 반환해 줍니다.

begin() | string에 가장 먼저 삽입된 데이터를 포인터로 가르킵니다.

s.begin(); // 'a'의 위치를 가르킵니다. *s.begin() == s.front()

end() | string에 가장 마지막에 삽입된 데이터의 뒤를 포인터로 가르킵니다.

s.end(); // string의 끝을 가르킵니다. *(s.end() - 1) == s.back()

4) (활용) 중간에 존재하는 데이터의 검색 후 삽입과 삭제

string의 경우 iterator라는 순환자를 사용해 데이터를 참조(포인터)합니다.

이를 활용하여 내장함수인 erase와 insert로 중간에 삭제나 삽입을 할 수 있습니다.

erase와 insert를 하면 알아서 기존에 있던 데이터들을 한 칸씩 앞으로 또는 뒤로 이동을 시켜줍니다.

string id = 'b'; // 찾고자 하는 데이터
for(auto it = s.begin(); it != s.end(); ++it) {
	if(*it == id) {
    	s.erase(it); // (위치) 결과 {'a', 'c', 'd', 'e', 'f'} | it - s.begin()은 index 반환(1 반환)
    }
}

string id2 = "c"; // 찾고자 하는 데이터
for(auto it = s.begin(); it != s.end(); ++it) {
	if(*it == id2) {
    	s.insert(it, "b"); // (위치, 삽입할 데이터) 결과 {'a', 'b', 'c', 'd', 'e', 'f'}
    }
}

string에는 iterator를 쓰지 않고, find()라는 내장함수가 있어 이것으로도 원하는 위치를 찾을 수 있습니다.

이것에 관해서는 아래에서 설명하겠습니다.

5) 이외에 유용한 내장함수

string에 데이터가 있는지, 몇 개의 데이터를 가지고 있는지를 알 수 있는 내장함수가 있습니다.

또한 string를 초기화 해줄 수 있는(모든 데이터를 없애주는) 내장함수도 있습니다.

s.empty(); // 데이터가 존재한다면 0 반환, 존재하지 않는다면 1 반환
s.size(); // 데이터의 갯수 반환 | 결과 6
s.clear(); // 초기화 | 결과 {} | 예제에는 적용하지 않음.

string의 일정 부분만 떼어낼수도 있고, 원하는 문자열이 있는지 찾을 수도 있습니다.

s.substr(1,4); // "bcde"
s.find("cde"); // 해당하는 문자열이 없다면 -1 반환, 있다면 찾는 문자열 첫 글자의 인덱스 반환 | 결과 2

문자열이 숫자로 이뤄져 있다면 int형으로 바꿀 수 있습니다.

string str = "12345";
int a = atoi(str); // a = 12345

// 문자열에 있는 하나만 int 형으로 변환하는 경우
string tmp = str[1]; // index를 포함하고 있기에 선언과 할당을 분리해줘야 함
int b = atoi(tmp); // b = 2

int 형도 문자열로 바꿀 수 있습니다.

int c = 123;
string str2 = to_string(c); // 결과 {'1', '2', '3'}

대문자를 소문자로, 소문자를 대문자로 바꿀 수도 있습니다.

string s2 = "abcde"
toupper(s2) // 결과 {'A', 'B', 'C', 'D', 'E'}
tolower(s2[1]) // 결과 {'A', 'b', 'C', 'D', 'E'}

숫자인지 문자인지도 구분할 수 있습니다. (한 글자씩만 구분 가능)

string s3 = "1aBCd2e34";
isdigit(s3[0]) // 숫자일 경우 1반환, 숫자가 아닐 경우 0 반환 | 결과 1
isalpha(s3[1]) // 문자일 경우 1반환, 문자가 아닐 경우 0 반환 | 결과 1

6) char 배열과 string 변환

① char 배열을 string으로

char arr[] = "abcdefg1234";
string s4 = arr;

② string을 char 배열로

string s5 = "abcdefgh";
char ch[100];

strcpy(ch, s5.c_str());

안녕하세요 기회개발자 기개 입니다.

오늘은 C++에서 배열 대신 자주 사용하는 vector에 대해 소개해보려고 합니다.

왜 배열 대신 vector를 사용할까요?

우선, 배열과 vector의 비교가 필요할 것 같습니다.

배열과 비교해서 vector의 장점이 무엇인지, 어떤 상황에서 사용하면 좋을지를 알아본 후 사용법에 대해 알아봅시다.

1. 배열과 vector의 비교

2. 어떤 상황에서 vector를 사용하는게 좋을까

3. vector의 사용법 (내장함수)

vector에는 데이터의 삽입, 삭제, 접근 등을 편하게 하기 위한 내장함수들이 존재합니다.

기본적으로 vector를 선언하는 방법을 살펴보고 자주 사용하는 내장함수들에 대해서 알아봅시다.

#include <vector>

using namespace std; // STL을 사용할 때 선언해주면 사용하기 편리합니다.

vector<int> v; // <>안에 삽입할 데이터의 자료형을 지정해줍니다.

1) 데이터의 삽입

데이터들이 순차적으로 삽입되기 때문에 마지막에 삽입된 데이터 뒤에 삽입을 합니다.

v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4); 
v.push_back(5); // 결과 {1, 2, 3, 4, 5}

2) 데이터의 삭제

데이터들이 순차적으로 삽입되기 때문에 마지막에 삽입된 데이터를 삭제합니다.

v.pop_back(); // 가장 마지막에 삽입했던 5가 삭제됩니다.

3) 데이터의 접근

vector는 인덱스로 데이터에 접근이 가능하지만,

순차적으로 데이터를 삽입하기에 데이터의 맨 앞과 맨 뒤를 접근할 수 있는 내장함수가 존재합니다.

front() | vector에 가장 먼저 삽입된 데이터를 알려줍니다.

v.front(); // 1을 반환해 줍니다.

back() | vector에 가장 마지막에 삽입된 데이터를 알려줍니다.

v.back(); // 4를 반환해 줍니다.

begin() | vector에 가장 먼저 삽입된 데이터를 포인터로 가르킵니다.

v.begin(); // 1의 위치를 가르킵니다. *v.begin() == v.front()

end() | vector에 가장 마지막에 삽입된 데이터의 뒤를 포인터로 가르킵니다.

v.end(); // vector의 끝을 가르킵니다. *(v.end() - 1) == v.back()

4) (활용) 중간에 존재하는 데이터의 검색 후 삽입과 삭제

vector의 경우 iterator라는 순환자를 사용해 데이터를 참조(포인터)합니다.

이를 활용하여 내장함수인 erase와 insert로 중간에 삭제나 삽입을 할 수 있습니다.

erase와 insert를 하면 알아서 기존에 있던 데이터들을 한 칸씩 앞으로 또는 뒤로 이동을 시켜줍니다.

int id = 2; // 찾고자 하는 데이터
for(auto it = v.begin(); it != v.end(); ++it) {
	if(*it == id) {
    	v.erase(it); // (위치) 결과 {1, 3, 4} | it - v.begin()은 인덱스 반환(1 반환)
    }
}

int id2 = 3; // 찾고자 하는 데이터
for(auto it = v.begin(); it != v.end(); ++it) {
	if(*it == id2) {
    	v.insert(it, 2); // (위치, 삽입할 데이터) 결과 {1, 2, 3, 4}
    }
}

5) 이외에 유용한 내장함수

vector에 데이터가 있는지, 몇 개의 데이터를 가지고 있는지를 알 수 있는 내장함수가 있습니다.

또한 vector를 초기화 해줄 수 있는(모든 데이터를 없애주는) 내장함수도 있습니다.

v.empty(); // 데이터가 존재한다면 0 반환, 존재하지 않는다면 1 반환
v.size(); // 데이터의 갯수 반환 | 결과 4
v.clear(); // 초기화 | 결과 {}