[C++] 코딩테스트 유용한 함수 및 표현 정리 📖

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] 수의 조합 ⭐

[C++][프로그래머스] 단체사진 찍기

• 주어진 문자열을 서로 다르게 나열하는 모든 경우의 수 순열을 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%의 성능 개선이 있습니다.