알고리즘에 유용한 팁들

난이도가 높은 알고리즘 문제일수록 구조체활용등의 개념적인 부분을 원활하게 사용할 필요가 있다.

구조체(struct)

구조체를 만들고, 구조체 포인터형 함수를 만들면, 다른 함수와 연동시 쉽게 관리 및 처리할 수 있다.

struct Post {
	int pID;
	int likeCnt;
	int timeStamp;
	int uID;

	Post* alloc(int _pID, int _timeStamp, int _uID) {
		pID = _pID;
		timeStamp = _timeStamp;
		uID = _uID;
		likeCnt = 0;

		return this;
	}
} postPool[MAX_POST];

Post의 포인터형 함수인 alloc을 구조체 안에 넣었다.

void makePost(int uID, int pID, int timestamp)
{
	Post* p = postPool[postPoolCnt++].alloc(pID, timestamp, uID);
	posts.insert({ pID, p });
}

앞서 구조체 내에 return this;를 넣었고, 그 리턴값을 postPool[postPoolCnt]가 받았으며, 이의 주소를 받는 부분이 "Post *p"이다.

Proirity Queue활용

priority_queue 선언 방식은 크게 두 가지로 알고 있으면 된다.

priority_queue <int> pq;

위 경우 int형에 내림차순 우선순위 큐가 만들어진다.
int형이 아닌 내가 만든 구조체를 쓰고, 내가 원하는 방식으로 정렬을 원한다면 다음과 같이 선언해야 한다.

priority_queue<Post*, vector<Post*>, compare> pq;

앞서 만든 Post 구조체의 포인터타입을 넣고싶은 경우 위의 코드처럼 쓰면 된다.
그리고 해당 선언 전에는 내가 만든 compare이 미리 만들어져 있어야 한다.

struct compare {
	bool operator()(Post*& p1, Post*& p2) {
		int p1Time = timestamp - p1->timeStamp;
		int p2Time = timestamp - p2->timeStamp;

		if (p2Time <= 1000 && p1Time <= 1000) {
			if (p2->likeCnt != p1->likeCnt) return p2->likeCnt > p1->likeCnt;
			else return p1Time > p2Time;
		}
		else if (p1Time <= 1000 && p2Time > 1000) {
			return false;
		}
		else if (p2Time <= 1000 && p1Time > 1000) {
			return true;
		}
		else {
			return p1Time> p2Time ;
		}
	}
};

compare라는 구조체 안에 연산자 오버로딩을 구현하면 내가 원하는 방식으로 priority_queue를 사용할 수 있게 된다. operator의 parameter에서 &를 붙이는 것을 잊지말자!