완전 탐색

• DFS/BFS로 그래프 문제 풀듯이 진행한다.
• input 값의 범위가 작다고 생각하면 “완전탐색” 이다! 모든 값을 분석해야하기 때문에 체크해야하는 범위는 당연히 작을 것!

Hash-Map

• key-value로 쌍으로 지을 수 있다면 한번쯤 고려해볼만 하다!
• C++라면 map 헤더를 꺼내서 접근해보자! 특히, key로 O(1) 접근이 가능하다는 것을 기억하고 이 특징을 잘 살릴 수 있는 코드를 짜보자!

힙

• priority_queue를 사용한다.
• 이진 트리문제기도 하지만, 넣을때마다 정렬이 된 배열을 원한다면 우선순위 큐를 써서 풀기도 한다.
• 사용법은 다음과 같다.

#include <queue>

int main() {
...(중략)
	priority_queue<int, vector<int>> Q;	//또는 다음과 같이도 쓴다.
// prioritu_queue<pair<int,int>, vector<pair<int,int>>, compare> Q;
// 이때 compare는 struct 상태로 만들고 그 안에 operator라는 함수를 만들어줘야한다.

/*
struct compare{
    bool operator() (pair<int,int> a, pair<int,int> b){
        if(a.second == b.second) return a.first > b.first;
        return a.second > b.second;
    }
};
*/
//나머지는 큐 함수 호출과 같다.

Sort

• 그냥 algorithm header의 sort를 쓰자….
• compare 함수는 이렇게 쓰자.

bool sorting(pair <int,int> p, pair <int,int> p2) { // compare 함수
    if (p.first == p2.first) { // x 좌표가 같다면
        return p.second < p2.second; // y 좌표를 오름차순으로
    }
    
    return p.first < p2.first; // x 좌표가 같지 않다면 x 좌표를 오름차순으로
}

Greedy

• 필자가 가장 싫어하는 풀이법이다. 야발련아 이딴거 왜 내는거야
• 이름 뜻대로 가장 탐욕스럽게 풀어야한다. 최소한의 자원을 들여서 최대한의 이득을 내는 거라 생각하자.
• 특히, 규칙이 있다. 한번 발견하면 바로 풀이법이 보일 것이다. → 노가다 해라 걍 ㅇㅇ