알고리즘/고급알고리즘[2강 STL사용하여 문제풀이]

Posted Apr 28, 2025

By 김범수

22 min read

sort() 사용법

sort함수는 배열의 원소들을 정렬할 때 사용하며, 기본적으로 오름차순으로 정렬한다. sort()함수를 사용하기 위해서는 ** 헤더파일을 include** 시켜줘야 한다.

sort(배열의 시작 주소, 배열의 마지막 주소+1) ;

sort(배열의 시작 주소, 배열의 마지막 주소+1, desc) ;

이렇게 sort()내에서 호출해주면, 왼쪽의 요소가 오른쪽의 요소보다 더 클 수 있도록 정렬되면서 결과적으로 내림차순으로 정렬된다.

이를 참고하여 위의 오름차순 예시코드를 내림차순 버전으로 바꾸면 아래와 같다.

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

//내림차순으로 정렬하기
bool desc(int a, int b) {
    return a > b;
}

int main() {
    int arr[5] = { 3, 1, 2, 5, 4 };

    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }

    cout << "\n\n=====desc sort======\n";
    sort(arr, arr + 5, desc); //기본값은 오름차순!

    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
}

함수명	설명
`for_each`	모든 요소를 지정한 함수로 조작
`find`	요소 검색
`find_if`	지정한 조건을 만족하는 요소 검색
`min_element`	최소 요소 리턴
`max_element`	최대 요소 리턴
`sort`	요소 정렬
`count`	지정한 숫자와 일치하는 요소 수 리턴
`count_if`	지정한 조건을 만족하는 요소 수 리턴
`all_of`	모든 요소가 지정한 조건을 만족하면 `true` 리턴
`none_of`	모든 요소가 지정한 조건을 만족하지 않으면 `true` 리턴
`any_of`	모든 요소 중 어느 하나라도 조건을 만족하면 `true` 리턴
`fill`	모든 요소에 지정한 값을 대입
`copy`	모든 요소를 복사
`copy_if`	지정한 조건을 만족하는 요소만 복사
`generate`	모든 요소에 지정한 연산 결과를 대입
`transform`	모든 요소를 지정한 함수로 변환
`remove`	지정한 숫자에 일치하는 요소를 제거
`remove_if`	지정한 조건을 만족하는 요소를 제거
`replace`	지정한 숫자를 다른 숫자로 변경
`replace_if`	지정한 조건에 만족하는 요소를 다른 숫자로 변경
`random_shuffle`	모든 요소를 무작위 셔플
`accumulate`	모든 요소의 집계 계산

벡터의 배열형태 vector<자료형> 변수명[배열의 크기]

  
#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<algorithm> // 알고리즘 정렬 사용

struct Player {
	int score;
	string name;
};

bool compare(Player& a, Player& b) {
	return a.score > b.score;
} //-> a가 b보다 클때 true 아니면 false

bool compare2(Player& a, Player& b) {
	return a.name > b.name;
	//-> 사전 순 정렬;
} //-> 이 방법이 귀찮으면 임시적으로 만들 수 있는 함수가 있는데 그것을 람다식이라함.
//이것은 무명함수라고함. 42번 줄부터 확인!

using namespace std;
int main() {
			
	char str[256] = "ABCDEF";
	string str2 = "ABCDEF";

	//이제 삽입정렬 버블정렬 등 알고리즘의 구현이 가능할것임.
	//시간이 걸리긴 하겠지만 ?
	//이젠 단순 함수를 사용해서 구현을 해보자.
	vector<int> vec = { 5,6,7,83,2,56,1,24,5,23,62,5232 };
	sort(vec.begin(), vec.end()); //-> 단순 정렬 알고리즘 내림차순
	sort(vec.begin(), vec.end(), greater<int>()); //-> 오름차순 정렬 알고리즘
	sort(vec.begin(), vec.end(), less<int>()); //-> 내림차순 알고리즘

	vector<Player> players = { {100, "Alice"}, {200, "Bob"}, {150, "Charlie"} };

	sort(players.begin(), players.end(), compare); //-> 사용자 정의 정렬법

	//람다식 사용법
	sort(players.begin(), players.end(), [](const Player& a, const Player& b) {
		return a.name < b.name;
		}
	); //-> 람다식 사용법 --> [] 뒤 전달인자와 함수내부의 값들이 들어감 (임시함수,무명함수)라고 많이함.
	//필요한  정보만 사용하니 퍼포먼스가 향상된다.
	// 어떤 방법으로 작성해도 모든 원소를 전부 순회하는경우는 람다식이 느릴수밖에 없다.
	// 익명함수의 특성상 외부의 캡쳐를 위해 캡처를 하는 시간제약이 있다.

	//for문을 돌지 않아도 내가 찾을수 있는 문법 find_if
	//find_if사용법
	find_if(players.begin(), players.end(), 
		[](const Player& a) {
		return a.name == "Alice";
		}); //-> 반환값이 std vector의 iterator형태로 반환된다.

	vector<Player>::iterator iter = find_if(players.begin(), players.end(),
		[](const Player& a) {
			return a.name == "Alice";
		});

	//-> 최대값의 인자를 찾고싶다?
	vector<int> :: iterator iter2 = max_element(vec.begin(), vec.end());
	return 0;
}

연습 문제 1번

문제 1번 숫자와 문자가 한 쌍인 n개 Set을 구조체배열에 입력받으세요. (1 <= n <= 100) 우선순위에 맞춰 삽입정렬로 정렬 후 출력하면 됩니다. [우선순위]

작은 숫자가 더 앞에 있어야 하며 (오름차순)
같은 숫자인 경우, 더 작은 문자가 앞에 배치되어야 합니다.

  
struct Player {
	int score;
	string name;
};

int main() {
	
		vector<Player> players = { {4,"A"},{4,"F"},{5,"E"},{5,"F"},{4,"A"},{1,"C"} };
		sort(players.begin(), players.end(), [](const Player& a, const Player& b){
			return a.score < b.score; }); //-> 사용자 정의 정렬법);

	return 0;
}

1번문제는 사용자정의 함수 [람다함수]를 사용해서 문제풀이를 하였다. 사용자 정의함수를 사용하니 따로 반환형 함수를 만들지 않아도 되었고, 구조를 한번더 확인할 수 있는 기회가 되었다.

연습문제 2번

사격 대회에서 N명의 선수가 점수를 냈습니다. (최대 1,000명) 선수들의 정보를 입력받고 금,은,동메달 선수의 기록만을 출력하고자 합니다. 그런데 사격대회 컴퓨터는 보안 문제로 인해, 네 칸의 배열만을 사용할 수 있습니다. 배열 네 칸만을 사용해서 금, 은, 동메달의 점수를 출력해주세요. (삽입정렬로 풀어주세요.)

  
struct Player{
	int score;
};

int main() {

	vector<Player> players = { {6},{35},{69},{73},{83},{95},{99} };

	sort(players.begin(), players.end(), greater<int>());

	for (int i = 0; i < 3; i++) {
		cout << players[i].score << endl;
	}
	return 0;
}

이번문제는 금 은 동 을 순서대로 출력하는것이 포인트였다. 내림차순으로 정렬 후 0번,1번,2번을 출력하자.

참고 -1번은 empty()상태이다.

연습문제 3번

숫자 폭탄의 개수 N을 입력 받고, N개의 폭탄을 입력 받습니다. 이 폭탄을 일렬로 쌓아 주세요. 그러다 같은 숫자 폭탄이 3개가 연속으로 쌓인다면, 한꺼번에 터집니다. 폭탄이 모두 쌓이고 난 뒤에, 남아 있는 숫자폭탄들을 오름차순으로 정렬해 주세요. 만약 17개의 폭탄을 아래와 같이 입력받았다면, 5 4 5 1 1 1 1 1 2 2 2 3 3 3 3 8 1 남은 폭탄은 5 4 5 1 1 3 8 1 입니다. 이제 정렬 후 출력하면 됩니다. 출력결과 : 1 1 1 3 4 5 5 8

이번문제부터가 벌써 고비였던것 같다.

  
struct Bomb {
	int num;
};
bool compare(Bomb& a, Bomb& b) {
	return a.num < b.num;
}
int main() {
	vector<Bomb> bombs;
	int n;
	cout << "폭탄의 개수 N을 입력하세요: " << endl;
	cin >> n;
	Bomb temp;

 	for (int i = 0; i < n; i++) {
		cout << "폭탄울 입력해주세요." << endl;
		cin >> temp.num;
		bombs.push_back(temp);
		int sz = bombs.size();

			if (sz >= 3) {
				if (bombs[sz - 1].num == bombs[sz - 2].num && bombs[sz - 2].num == bombs[0].num) {
					bombs.pop_back();
					bombs.pop_back();
					bombs.pop_back();

					sort(bombs.begin(), bombs.end(), compare);
			}
		}
	}
	return 0;
}

중요했던 포인트는 Bomb temp를 만들어서, temp.num에다가 cin으로 입력을 받는 것이었고, bombs.push_back으로 temp의 값을 하나씩 밀어 넣는것 이었다. 또한 매번 sz(size)의 크기를 매번 갱신해줘서 sz가 3보다 클때마다 검사를 해주는것이 해답이었다. 개인적으로 고민을 많이 해봐야하는 문제였던것 같다. 문해력보다는 코드를 어떻게 구성할지가 중요했었던것 같고, 배열로 풀자면 어느정도 쉽게 풀수 있지만 벡터를 고집했기에 더 어려웠던 것 같다.

연습문제 4번

창고에 여러 종류의 음료를 보관 하다보면, 음료수들이 섞이기 마련입니다. 쌓아둔 음료수들을 보기 좋게 정렬하려고 합니다. 음료수를 쌓을 수 있는 Line은 총 5개 입니다. 정렬이 필요한 Line의 숫자를 입력 받고, 그 Line에 해당하는 음료수들만 정렬 해야 합니다. (오름차순 정 렬)정렬 할 Line은 2개입니다. 만약 0 3을 입력받는다면, 0번과 3번 Line을 각각 정렬하면 됩니다

  
int main() {
	vector<int> line[5]; // 음료수 5개를 담을 수 있는 벡터 배열
	for (int i = 0; i < 5; i++) {
		int drink; // Line의 음료수의 개수
		cout << i << "번 Line에 음료수의 개수를 입력하세요: ";
		cin >> drink;
		for (int j = 0; j < drink; j++) {
			int drink;
			cin >> drink;
			line[i].push_back(drink); // 음료수의 개수 만큼 음료수를 입력받아 Line에 저장
		}
	}
		int line1, line2; // 정렬할 Line의 번호
		cout << "정렬할 LINE의 번호를 입력하세요.";
		cin >> line1 >> line2; // 정렬할 Line의 번호를 입력받음
		sort(line[line1].begin(), line[line1].end()); //Line1정렬
		sort(line[line2].begin(), line[line2].end()); //Line2정렬
		for (int i = 0; i < 5; i++) {
			cout << i << "번 Line: ";
			for (int drink : line[i]) {
				cout << drink << " ";
			}
			cout << endl;
		}

	return 0;
}

해당 문제에서 배울수 있었던 점은 vector를 **배열 형태로** 선언하여 vector line[int]형으로 선언할 수 있다는것을 알았다. vector형태로 선언해서 받으면 벡터로 선언된 line에 push_back 기능을 사용할 수 있다는것이고, 배열처럼 하나씩 쌓인다는것 이다. 솔직히 다른방법이 없을까를 너무 많이 고민했던것 같다.

~~~ 만약에 있다면 추가하겠다…~~~

연습문제 5번

  
using namespace std;
struct name {
	string name;
};

int main() {
	int n;
	vector<name> names;
	cin >> n;

	names.resize(n);

	for (int i = 0; i < n; i++) {
		cin >> names[i].name;
	}

	sort(names.begin(), names.end(), 
		[](const name& a, const name& b) {
			if (a.name.length() != b.name.length())
				return a.name.length() < b.name.length();
		return a.name < b.name;
		});

	cout << "Sorted names:" << endl;
	for (int i = 0; i < n; i++) {
		cout << names[i].name << endl;
	}

	return 0;
}

솔직히 int n을 선언하고 입력을 받고 **vector names[n]** 이런식으로 수식을 받으면 문제가 없어야될거같았는데, 안된다더라, 구글링해서 방법을 찾아보고 해당방식으로 resize()시켜서 공간을 만들어 주었다.

문제에서 처음에 sort(names.begin(),names.end(),compare) 혹은 람다식으로 구분시켜 오름차순으로 정렬해주는줄 알았는데 아무리해봐도 testcase에서 요구하는거랑 결과 값이 다르게 나오더라.

왜? 일까 생각을 해봤는데, 길이순으로 정렬 후 사전순으로 정렬하는것이 문제였는데, 처음에 예제문은 aaleh amily arszs java john을 주었고 java john aaleh였나? 이런순으로 정렬됐었는데 문제가 생겼었다. john java부터 순서가 맞지 않았던것, 일단 공간을 아껴주기 위해서 const name& a로 받아왔었다. 구글링을 해보니까 많이 이렇게 쓰는데, 공간을 아끼기 위해서라는것, 요즘은 램의 공간 자체가 워낙 넓어졌다보니 이정도는 안써도 될줄 알았는데, 몸에 베여야 할것 같다. 후에 뒤에 if문으로 조건을 주었다. a.name.length() ≠ b.name.length() 즉 a의 길이와 b의 같이가 같지 않다면 길이순으로 오름차순, 만약 같다면 이름순으로 오름차순인데 java와 john의 차이는 뭔지 아직도 잘 모르겠다 ..

연습문제 6번

어느 국가에서, 실명제 국회의원 투표가 시작되었습니다. 여러 사람들이 N명의 국회의원들에게 투표를 합니다. (1 <= N <= 100) 가장 투표를 많이 받은 국회의원을 찾아주세요. (같은 표를 받았다면, 번호가 더 빠른 사람이 당선됩니다.) 국회의원들은 숫자로 나타내고, 사람들은 투표할 숫자와 이름으로 입력됩니다. 당선된 국회의원이 누구에게 투표를 받았는지를 출력해주세요.

  
struct Human {
	int voteNum; //국회의원 번호
	string votername; // 투표한사람 이름
};

int main() {
	vector<Human> humans;
	vector<int> votes; //투표수
	
	
	int n;  //국회의원수
	cin >> n;   
	int m; // 투표인 수
	cin >> m; 
	
	
	votes.resize(n); // 국회의원 수 만큼 크기 조정
	humans.resize(m); // 투표인 수 만큼 크기 조정
	vector<string> votedby; // 투표한 사람 이름 저장

	for (int i = 0; i < m; i++) {
		cin >> humans[i].voteNum >> humans[i].votername; // 투표인 정보 입력
		votes[humans[i].voteNum]++; // 투표수 증가
		votedby.push_back(humans[i].votername); // 투표한 사람 이름 저장
	}
	
	
	int maxVotes = 0; // 최대 투표수
	int winner = 0; // 당선자 번호

	for (int i = 0; i < n; i++) {
		if (votes[i] > maxVotes) {
			maxVotes = votes[i];// 최대 투표수 갱신
			winner = i;
		}
	}
	cout << "가장 많이 투표받은 국회의원 : " << winner << endl;
	cout << "투표한 사람들" << endl;
	for (int i = 0; i < m; i++) {
		if (humans[i].voteNum == winner) {
			cout << humans[i].votername << endl;
		}
	}

	return 0;
}

솔직히 이문제는 처음에 국회의원,투표번호,사람이름으로 받고? 1~5번 배열에서 제일 나온 빈도수가 높은것을 찾고, 만약 찾은 후 그 벡터에 있는 값들을 출력하면 될줄알고 순수히 했었는데, 솔직히 실패했다. 음.. 더 좋은 방법을 없을까 싶어서? 고민을 한시간정도 했다. 사실 이것저것 찾아도보고 GPT도움은 받기 싫어서 해봤는데, .. 생각나는게 없음 …

그래서 ㄱ결국 도움을 받았다. 답을 받았던건 아니고 구조도를 힌트로 받았다.

일단 먼저 국회의원 수 , 투표인수를 입력에서 요구를 했으니 순서대로 받아두고 고민을 했었고, 일단 최대 투표번호를 받아야 할것 같아서 mAXvotes를 했었고? 당선자를 뽑았어야했다.

일단 투표인수 M명만큼 반복문으로 돌려서 voteNum 국회의원번호 votername 투표인 이름을 적는것이 중요할것이다. 또한 voteby의 벡터를 하나 선언해서 이름을 같이 저장해주는것이 좋을것이다. 배웠다 챗 gpt 다음엔 내가 이기도록 하지.

7번부턴 시간이부족해 풀지 못했다. 다음 업로드에 이어서 풀어보도록 하겠다.

매일 나에게 한마디 하기 - 늦장부리다가 탈난다.

C/C++ 이론, 고급알고리즘/STL

This post is licensed under CC BY 4.0 by the author.