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

 

0. 같이 읽으면 좋은 글

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

 

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
  • Union-Find 및 MST 참고
• 방향 그래프 → DFS (back edge의 존재 여부 확인)

 

9. 모르겠으면 예외 케이스를 반환하도록 구현

'1번 노드에서 이동할 수 있는 노드가 없다면 -1을 return합니다.' 처럼 예외 케이스일 경우 반환할 값을 주는 문제들이 있다. 코테에서 이런 문제를 도저히 못 풀 때는 ... return -1처럼 예외 케이스라도 반환하도록 코드를 작성하자. 부분 점수가 있다면 정말 작은 점수라도 부분 점수를 조금이라도 가져갈 수 있을 것이다.