알고리즘 관련 함수 2 + 코테 Tip

1. 최대값 & 최소값 탐색

---

주어진 컨테이너(주로 벡터나 string)에서 최대 혹은 최소를 구해주는 함수

• algorithm 헤더 include 필요
• min_element와 max_element 모두 리턴값은 해당 위치를 가리키는 iterator이다.
• string에서도 사용할 수 있다!
  • 숫자가 문자보다 우선순위가 빠르고, 대문자가 소문자보다 우선순위가 빠르다. (숫자 -> 대문자 -> 소문자)

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

int main()
{
	vector<int> vec = { 5,4,1,2,10 };

	vector<int>::iterator min_it = min_element(vec.begin(), vec.end());
	cout << "최소값 : " << *min_it << "\n"; //1

	vector<int>::iterator max_it = max_element(vec.begin(), vec.end());
	cout << "최대값 : " << *max_it << "\n"; //10

	auto [min_iter, max_iter] = minmax_element(vec.begin(), vec.end());
	cout << "최소 최대 : " << *min_iter << " " << *max_iter << "\n"; // 1 10
    
	{
	string str = "czzA9be";
	auto it = min_element(str.begin(), str.end());
	cout << *it << "\n"; //9
    }

    {
        string str = "Aa9";
        auto it = max_element(str.begin(), str.end());
        cout << *it << "\n"; // a
    }
}

 

 

2. 특정 조건을 만족하는 원소 개수 구하기

---

특정 조건을 만족하는 원소의 개수를 구해주는 함수

• algorithm 헤더 include 필요
• count 함수 : 세번째 파라메터로 넣은 값을 찾아주는 함수
• count_if 함수 : 세번째 람다식이나 다른 조건을 통해 특정 조건을 만족하는 값을 찾아주는 함수

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

int main()
{
	vector<int> vec = { 1,2,3,3,2,1,10,9 };

	int cnt = count(vec.begin(), vec.end(), 3); 
	cout << cnt << "\n"; // 2 (2개)

	int even_cnt = count_if(vec.begin(), vec.end(), [](int x) {return x % 2 == 0; });
	cout << even_cnt << "\n"; //3 (3개)
}

 

 

3. 어떤 STL 을 언제 쓸 것인가

---

삽입 삭제가 빈번한 경우

• map, set
• unordered_map, unordered_set

가장 큰(작은) 값을 추출하는 경우

• priority_queue

값을 넣고 빼고하는 동작이 많을 때 (특정 값과 비교를 하면서)

• stack
• queue

정렬이 필요한 경우

• 벡터와 같은 컨테이너를 sort 하거나
• map, set, priority_queue를 쓰면 알아서 계속 정렬이 된다.

중복 제거를 해야하는 경우

• 벡터를 unique + erase 
• set이나 map

 

 

4. 실전 팁

---

4 - 1. 제한 사항과 입력 크기

• N이 10^5 정도인 경우 O(NlgN) 은 여유로운 복잡도
• N이 10^6 이상인 경우 O(NlgN)이 마지노선, O(N) 정도의 복잡도 필요
• 참고할 사진

 

 

4 - 2. 예외 케이스

• 입력값이 1개일때(없을때)나 동일 원소만 존재할 때
• 음수, 0, 최대 혹은 최소(경계값)