C++을 이용하여 코딩테스트를 볼 때 유용한 STL 함수 및 표현을 정리합니다. 이 글은 지속적으로 업데이트되어 추가 될 예정입니다.
문자열을 대소문자로 변환
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
string s = "AbCdEfGhI";
transform(s.begin(), s.end(), s.begin(), [](char c)
{
return toupper(c);
});
cout << s << endl;
}- std::transform은 C++ STL(표준 템플릿 라이브러리)에서 제공되는 알고리즘 중 하나로, 순차 컨테이너의 요소를 변환하는 함수입니다. 주로 범위 기반 알고리즘 중 하나로 사용됩니다.
- s.begin()과 s.end()는 문자열 s의 시작과 끝을 가리키는 반복자(iterator)입니다.
- 세 번째 인자인 s.begin()은 출력 대상 범위의 시작 지점을 나타냅니다. 여기서는 변환된 값이 다시 s에 저장되기 때문에 입력과 출력이 같은 범위입니다.
- 네 번째 인자는 변환을 수행하는 함수자(람다 함수)입니다. [](char c) { return toupper(c); }는 입력으로 받은 문자 c를 toupper 함수를 사용하여 대문자로 변환한 값을 반환합니다.
문자열에서 숫자만 추출
#include <iostream>
#include <string>
using namespace std;
int main() {
string str = "abc123def456ghi";
string numbers;
// 문자열에서 숫자만 추출하여 numbers에 저장
for (char c : str)
if (isdigit(c))
numbers += c;
// 추출된 숫자 출력
cout << "추출된 숫자: " << numbers << endl;
// string을 int로 변환
stoi(numbers);
return 0;
}- 주어진 문자열에서 숫자만 추출합니다.
- isdigit라는 함수를 이용할 수 있습니다.
#include <iostream>
#include <string>
using namespace std;
int main() {
string str = "abc123def456ghi";
string numbers;
// 문자열에서 숫자만 추출하여 numbers에 저장
for (char c : str)
if (c >= '0' && c <= '9')
numbers += c;
// 추출된 숫자 출력
cout << "추출된 숫자: " << numbers << endl;
// string을 int로 변환
stoi(numbers);
return 0;
}- c++ 버전으로 인해 함수를 사용할 수 없는경우, if (c >= '0' && c <= '9')를 이용하여 직접 구현할 수 있습니다.
vector에서 값을 찾아 제거
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<string> v = { "apple", "orange", "banana", "orange", "grape" };
string _s = "orange";
// 벡터에서 특정 값 찾기
auto it = find(v.begin(), v.end(), _s);
if (it != v.end()) {
// 값을 찾았으면 제거
v.erase(it);
}
// 제거 후 벡터 출력
for (const auto& element : v) {
cout << element << " ";
}
cout << endl;
return 0;
}- std::find 함수를 사용하여 벡터 v에서 _s라는 값을 찾습니다.
- 만약 해당 값이 벡터 안에 존재하면, std::erase 함수를 사용하여 해당 값을 제거합니다.
- std::vector<string>::iterator 타입을 직접 명시하지 않고 auto를 사용하면 더욱 편리하게 사용할 수 있습니다.
vector의 배열 회전
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v{ 0, 1, 2, 3, 4, 5 };
int depth = 1;
for (int n : v)
cout << n << " ";
cout << endl;
rotate(v.begin(), v.begin() + depth, v.end()); // 인덱스가 감소하는 방향으로 depth만큼 회전
for (int n : v)
cout << n << " ";
cout << endl;
rotate(v.rbegin(), v.rbegin() + depth, v.rend()); // 인덱스가 증가하는 방향으로 depth만큼 회전
for (int n : v)
cout << n << " ";
cout << endl;
return 0;
}- rotate 함수를 이용하여 배열을 회전시킬 수 있습니다.
- v.begin()을 시작으로 사용하면, 인덱스가 감소하는 방향으로 회전시킬 수 있습니다.
- {0 1 2 3 4 5} -> {1 2 3 4 5 0}
- v.rbegin()을 시작으로 사용하면, 인덱스가 증가하는 방향으로 회전시킬 수 있습니다.
- {1 2 3 4 5 0} -> {0 1 2 3 4 5}
이분탐색
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = { 1, 2, 3, 3, 3, 3, 5, 6, 7, 8, 9 };
bool found = binary_search(v.begin(), v.end(), 3);
cout << "기존 벡터 값: ";
for (int n : v)
cout << n << " ";
cout << endl;
if (found) {
cout << "3이 존재함" << endl;
}
else {
cout << "3이 존재하지 않음!" << endl;
}
auto it_lower = lower_bound(v.begin(), v.end(), 3);
if (it_lower != v.end()) {
printf("3 이상이 처음으로 나타나는 인덱스 위치: %d, 값: %d\n", distance(v.begin(), it_lower), *it_lower);
}
else {
cout << "3 이상이 나타나는 위치를 찾지 못함!" << endl;
}
auto it_upper = upper_bound(v.begin(), v.end(), 3);
if (it_upper != v.end()) {
printf("3보다 큰 값이 처음으로 나타나는 인덱스 위치: %d, 값: %d\n", distance(v.begin(), it_upper), *it_upper);
}
else {
cout << "3보다 큰 값이 나타나는 위치를 찾지 못함!" << endl;
}
return 0;
}기존 벡터 값: 1 2 3 3 3 3 5 6 7 8 9
3이 존재함
3 이상이 처음으로 나타나는 인덱스 위치: 2, 값: 3
3보다 큰 값이 처음으로 나타나는 인덱스 위치: 6, 값: 5- std::binary_search 함수: 주어진 값이 정렬된 범위에 존재하는지 확인합니다.
- std::lower_bound 함수: 주어진 값 이상이 처음으로 나타나는 위치를 찾습니다.
- std::upper_bound 함수: 주어진 값보다 큰 값이 처음으로 나타나는 위치를 찾습니다.
- 이분 탐색을 위해서는 아래의 조건을 따라야 합니다.
- 정렬된 데이터: 이분 탐색은 정렬된 데이터에서 사용됩니다. 데이터가 정렬되어 있지 않으면 이분 탐색을 적용할 수 없습니다.
- 가능한한 중복되지 않는 키 값: 중복된 값이 많을수록 이분 탐색의 성능이 저하될 수 있습니다. 중복을 줄이는 것이 유리합니다.
- 인덱스 기반 접근이 가능한 데이터 구조: 이분 탐색은 인덱스 기반으로 작동합니다. 배열 또는 벡터와 같이 인덱스로 원소에 접근할 수 있는 데이터 구조에서 사용됩니다.
- 순차적인 데이터: 이분 탐색은 일반적으로 순차적인 데이터에서 사용됩니다. 이는 특정 요소를 찾는 것이지 임의의 요소를 검색하는 것이 아닙니다.
- 탐색 대상의 크기가 충분히 크거나 탐색 빈도가 높을 때 유용: 데이터 크기가 작거나 탐색 빈도가 낮은 경우에는 선형 탐색과 비교해 별다른 이점을 얻을 수 없습니다.
우선순위 큐 오름차순
우선순위 큐는 기본으로 생성하면 내림차순으로 되어있습니다. { 9, 8, 7 .... }
생성을 할 때, 추가 매개변수를 통해 오름차순으로 설정할 수 있습니다.
// pair<int, int>를 오름차순
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqASC;
// int를 오름차순
priority_queue <int, vector<int>, greater<int>> pqIntASC;- pair<int, int>
- 우선순위 큐에 저장될 요소의 형식을 지정합니다. 여기서는 int형 두 개가 묶인 쌍(pair)으로 이루어진 요소입니다. 첫 번째 int는 거리를, 두 번째 int는 노드 번호를 나타냅니다.
- vector<pair<int, int>>
- priority_queue에서 내부적으로 사용되는 컨테이너 타입을 지정합니다. priority_queue는 내부적으로 이 컨테이너를 사용하여 요소를 저장합니다. 여기서는 pair<int, int>를 저장하는 vector가 사용됩니다.
- greater<pair<int, int>>
- 비교 함수 객체를 지정하는 부분입니다. greater는 STL 라이브러리에 내장된 비교 함수 객체로, 두 요소를 비교할 때 첫 번째 요소가 두 번째 요소보다 작은지 여부를 확인하여 우선순위를 정합니다.
- 이 경우에는 내림차순으로 정렬하도록 합니다.
- greater의 반대는 less입니다. (오름차순)
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqASC;
for (int i = 0; i < 10; ++i)
{
pqASC.push({ rand() % 1000, rand() % 1000 });
}
for (int i = 0; i < 10; ++i)
{
pqASC.push({ 500, rand() % 1000 });
}
cout << "오름차순" << endl;
while (!pqASC.empty())
{
printf("%d %d\n", pqASC.top().first, pqASC.top().second);
pqASC.pop();
}
priority_queue <pair<int, int>> pqDESC;
for (int i = 0; i < 10; ++i)
{
pqDESC.push({ rand() % 1000, rand() % 1000 });
}
for (int i = 0; i < 10; ++i)
{
pqDESC.push({ 500, rand() % 1000 });
}
cout << "내림차순" << endl;
while (!pqDESC.empty())
{
printf("%d %d\n", pqDESC.top().first, pqDESC.top().second);
pqDESC.pop();
}
priority_queue <int, vector<int>, greater<int>> pqIntASC;
for (int i = 0; i < 10; ++i)
{
pqIntASC.push({ rand() % 1000 });
}
for (int i = 0; i < 10; ++i)
{
pqIntASC.push({ 500 });
}
cout << "내림차순" << endl;
while (!pqIntASC.empty())
{
printf("%d\n", pqIntASC.top());
pqIntASC.pop();
}
}
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
using namespace std;
int getNextPickaxe(vector<int>& picks)
{
if(picks[0]-- > 0)
return 0;
if(picks[1]-- > 0)
return 1;
if(picks[2]-- > 0)
return 2;
return 3;
}
int solution(vector<int> picks, vector<string> minerals) {
int answer = 0;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
int pickaxeCount = picks[0] + picks[1] + picks[2];
for(int i = 0; i < ceil(minerals.size() / 5.0f); ++i)
{
int arr[3] {0, 0, 0};
for(int j = 0; j < 5 && i * 5 + j < minerals.size() && pickaxeCount - i; ++j)
{
switch(minerals[i * 5 + j][0])
{
case 'd':
++arr[0];
break;
case 'i':
++arr[1];
break;
case 's':
++arr[2];
break;
}
}
pq.push({arr[0], {arr[1], arr[2]}});
}
while(!pq.empty())
{
int diamond = pq.top().first;
int iron = pq.top().second.first;
int stone = pq.top().second.second;
pq.pop();
printf("%d %d %d\n", diamond, iron, stone);
switch(getNextPickaxe(picks))
{
case 0:
answer += (diamond + iron + stone);
break;
case 1:
answer += (diamond * 5 + iron + stone);
break;
case 2:
answer += (diamond * 25 + iron * 5 + stone);
break;
default:
return answer;
break;
}
}
return answer;
}
int main()
{
solution({1, 3, 2}, {"diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"});
}- priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;와 같은 복잡한 형태의 우선순위 큐라 할지라도, 생성 규칙을 제대로 적용하면 내림차순의 우선순위 큐를 만들 수 있습니다.
2차원 벡터의 생성자
동적으로 크기를 할당할 때, 2차원 벡터를 사용할 수 있습니다.
vector<vector<int>> v = vector<vector<int>>(10, vector<int>(20, 30));- vector<vector<int>>: 2차원 벡터를 나타냅니다. 즉, 각 요소가 정수형 벡터인 벡터입니다.
- v = vector<vector<int>>(10, vector<int>(20, 30)): 10개의 요소를 가진 벡터를 생성합니다.
- 각 요소는 20개의 정수로 이루어진 벡터이며, 모든 요소는 30으로 초기화됩니다.
- 이 코드는 10x20 크기의 2차원 벡터를 만들고, 모든 요소를 30으로 초기화하는 데 사용됩니다.
- 만약 예를 들어, v[0][0]을 조회하면 30이 반환됩니다.
또는, 아래와 같이 선언과 동시에 초기화 할 수 있습니다.
vector<vector<int>> v(10, vector<int>(20, 30));
순열
[C++][DFS] 수의 조합 ⭐
#include int sel; int used[10]; int ch[10]; char arr[10]{ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' }; /// /// 순서를 무시하고 가능한 모든 경우의 수를 조합 /// /// void DFS_ALL_Combinations(int s) { if (s == sel) { for (int i = 0;
bonnate.tistory.com
[C++][프로그래머스] 단체사진 찍기
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📄 문제
bonnate.tistory.com
- 주어진 문자열을 서로 다르게 나열하는 모든 경우의 수 순열을 DFS를 통해 직접 구현하지 않고, 알고리즘 함수를 이용하여 간편하게 사용할 수 있습니다.
- next_permutation 함수를 사용합니다.
do {
map<char, int> m;
for(int i = 0; i < cnt; ++i)
m[characters[i]] = i;
if(checkValid(data, m))
++answer;
} while(next_permutation(characters.begin(), characters.end()));- next_permutaion(characters.begin(), characters.end())를 사용하면 characters의 요소 자체의 값이 변경됩니다. 이를 통해 가능한 모든 조합을 얻어낼 수 있습니다.
- DFS를 이용하여 직접 구현하는 방식보다 성능이 좋습니다. DFS를 활용한 구현은 위 문제에서 4500ms가 나온 반면, 함수를 통해 구현한 방식은 4000ms로 약 10%의 성능 개선이 있습니다.
'algorithms (C++)' 카테고리의 다른 글
| [C++][프로그래머스] 배달 ⭐️ (0) | 2023.11.19 |
|---|---|
| [C++][프로그래머스] [1차] 프렌즈4블록 (1) | 2023.11.19 |
| [C++][프로그래머스] [1차] 캐시 (0) | 2023.11.19 |
| [C++][프로그래머스] 다리를 지나는 트럭 rotate(), q.back() (0) | 2023.11.18 |
| [C++][프로그래머스] 주식가격 (0) | 2023.11.17 |
C++을 이용하여 코딩테스트를 볼 때 유용한 STL 함수 및 표현을 정리합니다. 이 글은 지속적으로 업데이트되어 추가 될 예정입니다.
문자열을 대소문자로 변환
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
string s = "AbCdEfGhI";
transform(s.begin(), s.end(), s.begin(), [](char c)
{
return toupper(c);
});
cout << s << endl;
}- std::transform은 C++ STL(표준 템플릿 라이브러리)에서 제공되는 알고리즘 중 하나로, 순차 컨테이너의 요소를 변환하는 함수입니다. 주로 범위 기반 알고리즘 중 하나로 사용됩니다.
- s.begin()과 s.end()는 문자열 s의 시작과 끝을 가리키는 반복자(iterator)입니다.
- 세 번째 인자인 s.begin()은 출력 대상 범위의 시작 지점을 나타냅니다. 여기서는 변환된 값이 다시 s에 저장되기 때문에 입력과 출력이 같은 범위입니다.
- 네 번째 인자는 변환을 수행하는 함수자(람다 함수)입니다. [](char c) { return toupper(c); }는 입력으로 받은 문자 c를 toupper 함수를 사용하여 대문자로 변환한 값을 반환합니다.
문자열에서 숫자만 추출
#include <iostream>
#include <string>
using namespace std;
int main() {
string str = "abc123def456ghi";
string numbers;
// 문자열에서 숫자만 추출하여 numbers에 저장
for (char c : str)
if (isdigit(c))
numbers += c;
// 추출된 숫자 출력
cout << "추출된 숫자: " << numbers << endl;
// string을 int로 변환
stoi(numbers);
return 0;
}- 주어진 문자열에서 숫자만 추출합니다.
- isdigit라는 함수를 이용할 수 있습니다.
#include <iostream>
#include <string>
using namespace std;
int main() {
string str = "abc123def456ghi";
string numbers;
// 문자열에서 숫자만 추출하여 numbers에 저장
for (char c : str)
if (c >= '0' && c <= '9')
numbers += c;
// 추출된 숫자 출력
cout << "추출된 숫자: " << numbers << endl;
// string을 int로 변환
stoi(numbers);
return 0;
}- c++ 버전으로 인해 함수를 사용할 수 없는경우, if (c >= '0' && c <= '9')를 이용하여 직접 구현할 수 있습니다.
vector에서 값을 찾아 제거
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<string> v = { "apple", "orange", "banana", "orange", "grape" };
string _s = "orange";
// 벡터에서 특정 값 찾기
auto it = find(v.begin(), v.end(), _s);
if (it != v.end()) {
// 값을 찾았으면 제거
v.erase(it);
}
// 제거 후 벡터 출력
for (const auto& element : v) {
cout << element << " ";
}
cout << endl;
return 0;
}- std::find 함수를 사용하여 벡터 v에서 _s라는 값을 찾습니다.
- 만약 해당 값이 벡터 안에 존재하면, std::erase 함수를 사용하여 해당 값을 제거합니다.
- std::vector<string>::iterator 타입을 직접 명시하지 않고 auto를 사용하면 더욱 편리하게 사용할 수 있습니다.
vector의 배열 회전
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v{ 0, 1, 2, 3, 4, 5 };
int depth = 1;
for (int n : v)
cout << n << " ";
cout << endl;
rotate(v.begin(), v.begin() + depth, v.end()); // 인덱스가 감소하는 방향으로 depth만큼 회전
for (int n : v)
cout << n << " ";
cout << endl;
rotate(v.rbegin(), v.rbegin() + depth, v.rend()); // 인덱스가 증가하는 방향으로 depth만큼 회전
for (int n : v)
cout << n << " ";
cout << endl;
return 0;
}- rotate 함수를 이용하여 배열을 회전시킬 수 있습니다.
- v.begin()을 시작으로 사용하면, 인덱스가 감소하는 방향으로 회전시킬 수 있습니다.
- {0 1 2 3 4 5} -> {1 2 3 4 5 0}
- v.rbegin()을 시작으로 사용하면, 인덱스가 증가하는 방향으로 회전시킬 수 있습니다.
- {1 2 3 4 5 0} -> {0 1 2 3 4 5}
이분탐색
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = { 1, 2, 3, 3, 3, 3, 5, 6, 7, 8, 9 };
bool found = binary_search(v.begin(), v.end(), 3);
cout << "기존 벡터 값: ";
for (int n : v)
cout << n << " ";
cout << endl;
if (found) {
cout << "3이 존재함" << endl;
}
else {
cout << "3이 존재하지 않음!" << endl;
}
auto it_lower = lower_bound(v.begin(), v.end(), 3);
if (it_lower != v.end()) {
printf("3 이상이 처음으로 나타나는 인덱스 위치: %d, 값: %d\n", distance(v.begin(), it_lower), *it_lower);
}
else {
cout << "3 이상이 나타나는 위치를 찾지 못함!" << endl;
}
auto it_upper = upper_bound(v.begin(), v.end(), 3);
if (it_upper != v.end()) {
printf("3보다 큰 값이 처음으로 나타나는 인덱스 위치: %d, 값: %d\n", distance(v.begin(), it_upper), *it_upper);
}
else {
cout << "3보다 큰 값이 나타나는 위치를 찾지 못함!" << endl;
}
return 0;
}기존 벡터 값: 1 2 3 3 3 3 5 6 7 8 9
3이 존재함
3 이상이 처음으로 나타나는 인덱스 위치: 2, 값: 3
3보다 큰 값이 처음으로 나타나는 인덱스 위치: 6, 값: 5- std::binary_search 함수: 주어진 값이 정렬된 범위에 존재하는지 확인합니다.
- std::lower_bound 함수: 주어진 값 이상이 처음으로 나타나는 위치를 찾습니다.
- std::upper_bound 함수: 주어진 값보다 큰 값이 처음으로 나타나는 위치를 찾습니다.
- 이분 탐색을 위해서는 아래의 조건을 따라야 합니다.
- 정렬된 데이터: 이분 탐색은 정렬된 데이터에서 사용됩니다. 데이터가 정렬되어 있지 않으면 이분 탐색을 적용할 수 없습니다.
- 가능한한 중복되지 않는 키 값: 중복된 값이 많을수록 이분 탐색의 성능이 저하될 수 있습니다. 중복을 줄이는 것이 유리합니다.
- 인덱스 기반 접근이 가능한 데이터 구조: 이분 탐색은 인덱스 기반으로 작동합니다. 배열 또는 벡터와 같이 인덱스로 원소에 접근할 수 있는 데이터 구조에서 사용됩니다.
- 순차적인 데이터: 이분 탐색은 일반적으로 순차적인 데이터에서 사용됩니다. 이는 특정 요소를 찾는 것이지 임의의 요소를 검색하는 것이 아닙니다.
- 탐색 대상의 크기가 충분히 크거나 탐색 빈도가 높을 때 유용: 데이터 크기가 작거나 탐색 빈도가 낮은 경우에는 선형 탐색과 비교해 별다른 이점을 얻을 수 없습니다.
우선순위 큐 오름차순
우선순위 큐는 기본으로 생성하면 내림차순으로 되어있습니다. { 9, 8, 7 .... }
생성을 할 때, 추가 매개변수를 통해 오름차순으로 설정할 수 있습니다.
// pair<int, int>를 오름차순
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqASC;
// int를 오름차순
priority_queue <int, vector<int>, greater<int>> pqIntASC;- pair<int, int>
- 우선순위 큐에 저장될 요소의 형식을 지정합니다. 여기서는 int형 두 개가 묶인 쌍(pair)으로 이루어진 요소입니다. 첫 번째 int는 거리를, 두 번째 int는 노드 번호를 나타냅니다.
- vector<pair<int, int>>
- priority_queue에서 내부적으로 사용되는 컨테이너 타입을 지정합니다. priority_queue는 내부적으로 이 컨테이너를 사용하여 요소를 저장합니다. 여기서는 pair<int, int>를 저장하는 vector가 사용됩니다.
- greater<pair<int, int>>
- 비교 함수 객체를 지정하는 부분입니다. greater는 STL 라이브러리에 내장된 비교 함수 객체로, 두 요소를 비교할 때 첫 번째 요소가 두 번째 요소보다 작은지 여부를 확인하여 우선순위를 정합니다.
- 이 경우에는 내림차순으로 정렬하도록 합니다.
- greater의 반대는 less입니다. (오름차순)
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pqASC;
for (int i = 0; i < 10; ++i)
{
pqASC.push({ rand() % 1000, rand() % 1000 });
}
for (int i = 0; i < 10; ++i)
{
pqASC.push({ 500, rand() % 1000 });
}
cout << "오름차순" << endl;
while (!pqASC.empty())
{
printf("%d %d\n", pqASC.top().first, pqASC.top().second);
pqASC.pop();
}
priority_queue <pair<int, int>> pqDESC;
for (int i = 0; i < 10; ++i)
{
pqDESC.push({ rand() % 1000, rand() % 1000 });
}
for (int i = 0; i < 10; ++i)
{
pqDESC.push({ 500, rand() % 1000 });
}
cout << "내림차순" << endl;
while (!pqDESC.empty())
{
printf("%d %d\n", pqDESC.top().first, pqDESC.top().second);
pqDESC.pop();
}
priority_queue <int, vector<int>, greater<int>> pqIntASC;
for (int i = 0; i < 10; ++i)
{
pqIntASC.push({ rand() % 1000 });
}
for (int i = 0; i < 10; ++i)
{
pqIntASC.push({ 500 });
}
cout << "내림차순" << endl;
while (!pqIntASC.empty())
{
printf("%d\n", pqIntASC.top());
pqIntASC.pop();
}
}
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
using namespace std;
int getNextPickaxe(vector<int>& picks)
{
if(picks[0]-- > 0)
return 0;
if(picks[1]-- > 0)
return 1;
if(picks[2]-- > 0)
return 2;
return 3;
}
int solution(vector<int> picks, vector<string> minerals) {
int answer = 0;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
int pickaxeCount = picks[0] + picks[1] + picks[2];
for(int i = 0; i < ceil(minerals.size() / 5.0f); ++i)
{
int arr[3] {0, 0, 0};
for(int j = 0; j < 5 && i * 5 + j < minerals.size() && pickaxeCount - i; ++j)
{
switch(minerals[i * 5 + j][0])
{
case 'd':
++arr[0];
break;
case 'i':
++arr[1];
break;
case 's':
++arr[2];
break;
}
}
pq.push({arr[0], {arr[1], arr[2]}});
}
while(!pq.empty())
{
int diamond = pq.top().first;
int iron = pq.top().second.first;
int stone = pq.top().second.second;
pq.pop();
printf("%d %d %d\n", diamond, iron, stone);
switch(getNextPickaxe(picks))
{
case 0:
answer += (diamond + iron + stone);
break;
case 1:
answer += (diamond * 5 + iron + stone);
break;
case 2:
answer += (diamond * 25 + iron * 5 + stone);
break;
default:
return answer;
break;
}
}
return answer;
}
int main()
{
solution({1, 3, 2}, {"diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"});
}- priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;와 같은 복잡한 형태의 우선순위 큐라 할지라도, 생성 규칙을 제대로 적용하면 내림차순의 우선순위 큐를 만들 수 있습니다.
2차원 벡터의 생성자
동적으로 크기를 할당할 때, 2차원 벡터를 사용할 수 있습니다.
vector<vector<int>> v = vector<vector<int>>(10, vector<int>(20, 30));- vector<vector<int>>: 2차원 벡터를 나타냅니다. 즉, 각 요소가 정수형 벡터인 벡터입니다.
- v = vector<vector<int>>(10, vector<int>(20, 30)): 10개의 요소를 가진 벡터를 생성합니다.
- 각 요소는 20개의 정수로 이루어진 벡터이며, 모든 요소는 30으로 초기화됩니다.
- 이 코드는 10x20 크기의 2차원 벡터를 만들고, 모든 요소를 30으로 초기화하는 데 사용됩니다.
- 만약 예를 들어, v[0][0]을 조회하면 30이 반환됩니다.
또는, 아래와 같이 선언과 동시에 초기화 할 수 있습니다.
vector<vector<int>> v(10, vector<int>(20, 30));
순열
[C++][DFS] 수의 조합 ⭐
#include int sel; int used[10]; int ch[10]; char arr[10]{ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j' }; /// /// 순서를 무시하고 가능한 모든 경우의 수를 조합 /// /// void DFS_ALL_Combinations(int s) { if (s == sel) { for (int i = 0;
bonnate.tistory.com
[C++][프로그래머스] 단체사진 찍기
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📄 문제
bonnate.tistory.com
- 주어진 문자열을 서로 다르게 나열하는 모든 경우의 수 순열을 DFS를 통해 직접 구현하지 않고, 알고리즘 함수를 이용하여 간편하게 사용할 수 있습니다.
- next_permutation 함수를 사용합니다.
do {
map<char, int> m;
for(int i = 0; i < cnt; ++i)
m[characters[i]] = i;
if(checkValid(data, m))
++answer;
} while(next_permutation(characters.begin(), characters.end()));- next_permutaion(characters.begin(), characters.end())를 사용하면 characters의 요소 자체의 값이 변경됩니다. 이를 통해 가능한 모든 조합을 얻어낼 수 있습니다.
- DFS를 이용하여 직접 구현하는 방식보다 성능이 좋습니다. DFS를 활용한 구현은 위 문제에서 4500ms가 나온 반면, 함수를 통해 구현한 방식은 4000ms로 약 10%의 성능 개선이 있습니다.
'algorithms (C++)' 카테고리의 다른 글
| [C++][프로그래머스] 배달 ⭐️ (0) | 2023.11.19 |
|---|---|
| [C++][프로그래머스] [1차] 프렌즈4블록 (1) | 2023.11.19 |
| [C++][프로그래머스] [1차] 캐시 (0) | 2023.11.19 |
| [C++][프로그래머스] 다리를 지나는 트럭 rotate(), q.back() (0) | 2023.11.18 |
| [C++][프로그래머스] 주식가격 (0) | 2023.11.17 |
