코딩테스트 전에 빠르게 볼 내용 정리

 

0. 같이 읽으면 좋은 글

[C++] 삼성 SW 역량 테스트 보기 전 알고리즘 정리

 

1. 문제 접근 순서

기본적인 문제 접근 순서: 완전 탐색 → DP → 그리디

• 1초에 약 2000만번 연산 → 제한시간 내에 연산 몇 번 수행될지 확인하자
• 그리디는 거의 정렬 + 우선순위 큐로 풀이
  • 특정 기준에 따라 sort → 우선순위 큐에 넣기
• 입력값이 매우 크다? → 이분탐색 고려하기
• 0또는 1로 나뉘는 상황이 여러 개 중첩될 때 → 비트마스킹으로 표현하는거 고려하기

 

2. 정렬 함수 커스텀

• 사용자 정의 정렬 함수 cmp를 구현
• sort 함수의 세 번째 인자로 cmp를 준다

아래는 first가 같을 경우 second가 작은 순으로 정렬하는 예제

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(pair<int, int> u, pair<int, int> t){
	if(u.first == t.first) return u.second <= t.second;
	return u.first < t.first;
}

int main(){
	// 중략 ...
	sort(pos.begin(), pos.end(), cmp);
}

 

3. 이분 탐색 - lower bound, upper bound

🌟 이분 탐색을 사용하려면 오름차순으로 정렬되어 있어야 함 !!

 

• lower bound: 크거나 같은 값 중 가장 처음 나오는 값
• upper bound: 큰 값 중 가장 처음 나오는 값

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

	vector<int> arr = { 1,2,3,4,5,6 };
	// 결과: 5
	cout << "lower_bound(6) : " << lower_bound(v.begin(), v.end()) - v.begin();

	return 0;
}

• 기본적으로 iterator를 반환하므로 begin()을 빼서 인덱스를 찾을 수 있음

 

4. priority queue

priority queue는 기본적으로 큰 값 우선이므로 작은 값 우선으로 하려면 기본 연산자 greater를 사용한다.

priority_queue<int, vector<int>, greater<int>> pq;

 

정렬 순서를 커스텀하고 싶다면 정렬 함수처럼 cmp 함수를 만들어주어야 한다.

// 커스텀 정렬 함수
struct cmp {
  bool operator()(int a, int b) {
    return a > b;
  }
};

// 우선순위 큐 선언
priority_queue <int, vector<int>, cmp> pq;

 

5. tuple

3개 이상의 값을 한 쌍으로 들고 있고 싶을 경우 사용하면 좋다.

튜플을 만들 때는 make_tuple 함수를 사용하고, 튜플에서 값을 조회할 때는 get<>을 사용한다.

 

#include <iostream>
#include <tuple>
#include <vector>

using namespace std;

typedef tuple<int, int, int> tiii;

int main() {
	int a = 1;
    int b = 2;
    int c = 3;
    
    vector<tiii> tuples;
    
    // 튜플을 만들 때
    tuples.push_back(make_tuple(a, b, c));
    
    // 튜플에서 값을 꺼낼 때
    for (auto elem : tuples) {
    	cout << get<0>(elem) << ' ' << get<1>(elem) << ' ' << get<2>(elem) << endl;
     }
     
	return 0;
}