0. 같이 읽으면 좋은 글
[C++] 삼성 SW 역량 테스트 보기 전 알고리즘 정리
1. 입출력 시간 단축ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);C++ 표준 스트림과 C 표준 스트림의 동기화를 끈다endl 대신 "\n"을 사용하기 2. 순열 (next_permutation)서로 다른 n개의 원소에서 r개를 뽑
leeeeeyeon-dev.tistory.com
1. 문제 접근 순서
기본적인 문제 접근 순서: 완전 탐색 → DP → 그리디
- 1초에 약 2000만번 연산 → 제한시간 내에 연산 몇 번 수행될지 확인하자
- 그리디는 거의 정렬 + 우선순위 큐로 풀이
- 특정 기준에 따라 sort → 우선순위 큐에 넣기
- 입력값이 매우 크다? → 이분탐색 고려하기
- 0또는 1로 나뉘는 상황이 여러 개 중첩될 때 → 비트마스킹으로 표현하는거 고려하기
2. 정렬 함수 커스텀
- 사용자 정의 정렬 함수 cmp를 구현
- sort 함수의 세 번째 인자로 cmp를 준다
(+) 만약 동일한 값에 대하여 순서를 유지해야 할 경우 stable_sort를 사용하자. 대신 실행 시간은 sort()보다 약간 더 길게 나올 수 있다.
ex) [프로그래머스] 파일명 정렬
아래는 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(), 6) - 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));
// 튜플에서 값을 꺼낼 때 1
for (auto elem : tuples) {
cout << get<0>(elem) << ' ' << get<1>(elem) << ' ' << get<2>(elem) << endl;
}
// 튜플에서 값을 꺼낼 때 2
int x, y, z;
for (auto elem : tuples) {
tie(x, y, z) = elem;
}
return 0;
}
6. 소수 판별 알고리즘
2~n까지 모두 비교하지 않고, 2~n의 제곱근까지만 비교해도 된다.
만약 n이 소수가 아니라면, 그 숫자의 약수들의 곱셈은 대칭적으로 일어나게 된다. 그러므로 소수인지 판별할 때는 n의 제곱근 이하의 수까지만 검사하여 시간 복잡도를 줄이자.
ex) 24의 약수들의 곱셈
2 * 12 | 3 * 8 | 4 * 6 | √24 * √24 | 6 * 4 | 8 * 3 | 12 * 2
bool isPrime(long n) {
if (n == 1) return false;
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
7. 문자열 split
C++에는 문자열을 나누는 split 함수가 존재하지 않아 직접 구현해야 한다.
#include <vector>
#include <string>
#include <sstream>
vector<string> split(string input, char delimiter) {
vector<string> answer;
stringstream ss(input);
string temp;
while(getline(ss, temp, delimiter)) {
answer.push_back(temp);
}
return answer;
}
8. 사이클 탐지
- 무방향 그래프 → Union-find
- 방향 그래프 → DFS (back edge의 존재 여부 확인)
9. 모르겠으면 예외 케이스를 반환하도록 구현
'1번 노드에서 이동할 수 있는 노드가 없다면 -1을 return합니다.' 처럼 예외 케이스일 경우 반환할 값을 주는 문제들이 있다. 코테에서 이런 문제를 도저히 못 풀 때는 ... return -1처럼 예외 케이스라도 반환하도록 코드를 작성하자. 부분 점수가 있다면 정말 작은 점수라도 부분 점수를 조금이라도 가져갈 수 있을 것이다.
