https://www.acmicpc.net/problem/1707

#include <bits/stdc++.h>
using namespace std;

int color[20001];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int k;
	cin >> k;
	for (int T = 0; T < k; T++) {
		int v, e;
		cin >> v >> e;

		memset(color, 0, sizeof(color));

		vector<int> adj[20001];
		for (int i = 0; i < e; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		queue<int> Q;

		bool flag = true;

		for (int i = 1; i <= v; i++) {
			if (color[i] == 0) {
				color[i] = 1;
				Q.push(i);
	
				while (!Q.empty()) {
					int x = Q.front();
					int cc = color[x];
					Q.pop();

					for (auto nx : adj[x]) {
						if (color[nx] == cc) {
							flag = false;
							cout << "NO\n";
							break;
						}
						else if (color[nx] == 0) {
							color[nx] = cc == 1 ? 2 : 1;
							Q.push(nx);
						}
					}

					if (!flag) break;
				}

				if (!flag) break;
			}
		}


		if (flag) {
			cout << "YES\n";;
		}


	}

	return 0;
}

https://www.acmicpc.net/problem/1738

1. 문제설명

간선의 cost를 뺏기는 양으로 두면

금을 땅에서 주울 경우에는 마이너스

뺏길 경우는 플러스로 두게 되어 이동하는데 필요한 cost를 설정할 수 있다.

이후 벨만포드 알고리즘을 적용해서 풀면 된다.

단 이 문제의 경우 음의 사이클이 존재한다고 무조건 -1이 될 수 없다.

왜냐하면 음의 사이클이 존재해도 시작점에서 도착점까지 가는데 경유하지 않을 수 있기 때문이다

즉 음의사이클이 존재는 하나 따로 동떨어진 경우가 테스트케이스로 들어올 수도 있다.

그래서 음의사이클이 존재하고 음의사이클에서 도착점으로 가는지 판단해야한다.

또한 출발점 1에서 도착점 n까지 도달할 수 있는지 확인해야한다.

이를 위해 역방향 간선을 저장해두고 n으로부터 시작하여 BFS를 돌면

1과 음의 사이클에서 도착점까지 갈 수 있는지 확인할 수 있다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;

const long long INF = 1e18;
long long dist[101];
int pre[101];

int n, m;
vector<pi> adj[101];
vector<pi> rev_adj[101];

bool goal[101];

void check_goal() {
	queue<int> Q;

	Q.push(n);
	goal[n] = 1;

	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		for (auto &i : rev_adj[x]) {
			int nx = i.first;
			if (goal[nx] == 0) {
				Q.push(nx);
				goal[nx] = 1;
			}
		}
	}
}

void print(int n) {

	if (n == 0) return;
	print(pre[n]);
	cout << n << ' ';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ v,-w });
		rev_adj[v].push_back({ u,-w });
	}
	
	check_goal();

	//시작점에서 도착점 가는 길이 없는 경우
	if (goal[1] == 0) {
		cout << -1 << '\n';
		return 0;
	}

	fill(dist, dist + 101, INF);

	dist[1] = 0;



	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= n; j++) {

			for (auto& a : adj[j]) {
				int nx = a.first;
				int d = a.second;

				if (dist[j] != INF && dist[nx] > dist[j] + d) {
					pre[nx] = j;
					dist[nx] = dist[j] + d;

					if ((i == n-1) && (goal[j])) {
						cout << -1 << '\n';
						return 0;
					}
				}
			}
		}
	}


	print(n);


	return 0;
}

https://www.acmicpc.net/problem/11997

#include <bits/stdc++.h>
using namespace std;

int arr[1001][1001];
int psum[1001][1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;


	//좌표 압축 
	vector<pair<int, int> > v;
	set<int> s_x;
	set<int> s_y;
	map<int, int> m_x;
	map<int, int> m_y;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v.push_back({ x,y });
		s_x.insert(x);
		s_y.insert(y);
	}

	int idx = 1;

	for (auto i : s_x) {
		m_x[i] = idx++;
	}

	idx = 1;

	for (auto i : s_y) {
		m_y[i] = idx++;
	}


	for (int i = 0; i < n; i++) {
		arr[m_x[v[i].first]][m_y[v[i].second]] = 1;
	}



	//사분면 누적합 구하기 
	int ans = INT_MAX;


	for (int i = 0; i < 1000; i++) {
		for (int j = 0; j < 1000; j++) {
			psum[i + 1][j + 1] = psum[i + 1][j] + psum[i][j + 1] - psum[i][j] + arr[i+1][j+1];
		}
	}


	for (int i = 0; i < 1000; i++) {
		for (int j = 0; j < 1000; j++) {

			int a = psum[i][j];
			int b = psum[i][1000] - a;
			int c = psum[1000][j] - a;
			int d = psum[1000][1000] - a - b - c;

			ans = min(ans, max({ a, b, c, d }));
		}
	}
	cout << ans << '\n';

	return 0;
}

https://www.acmicpc.net/problem/7662

#include <bits/stdc++.h>
using namespace std;

struct Node_max {
	int idx, value;
	bool operator<(const Node_max& b) const {
		return value < b.value;
	}
};

struct Node_min {
	int idx, value;
	bool operator<(const Node_min &b) const {
		return value > b.value;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	for (int T = 0; T < t; T++) {
		int k;
		cin >> k;

		priority_queue<Node_max> max_q;
		priority_queue<Node_min> min_q;


		vector<bool> ch(k + 1, 0);
		int idx = 1;
		int q_size = 0;

		for (int i = 0; i < k; i++) {
			char c;
			int val;

			cin >> c >> val;

			if (c == 'I') {

				max_q.push({ idx,val });
				min_q.push({ idx,val });
				idx++;
			}
			else {
				if (val == -1) {
					
					while (!min_q.empty() && ch[min_q.top().idx]) {
						min_q.pop();
					}

					if (!min_q.empty()) {
						ch[min_q.top().idx] = 1;
						min_q.pop();
					}

				}
				else {
					while (!max_q.empty() && ch[max_q.top().idx]) {
						max_q.pop();
					}

					if (!max_q.empty()) {
						ch[max_q.top().idx] = 1;
						max_q.pop();
					}



				}
			}


		}

		int ans = 0;
		for (int i = 1; i < idx; i++) {
			if (ch[i] == 0) {
				ans++;
			}
		}
		if (ans == 0) {
			cout << "EMPTY\n";
		}
		else {
			
			while (!min_q.empty() && ch[min_q.top().idx]) {
				min_q.pop();
			}


			while (!max_q.empty() && ch[max_q.top().idx]) {
				max_q.pop();
			}


			cout << max_q.top().value << ' ' << min_q.top().value << '\n';



		}
	}

	return 0;
}

https://www.acmicpc.net/problem/16139

#include <bits/stdc++.h>
using namespace std;


int psum[200001][26];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string s;
	cin >> s;
	s = "_" + s;

	for (int i = 1; i < s.length(); i++) {

		for (int j = 0; j < 26; j++) {
			psum[i][j] = psum[i - 1][j];
		}
		psum[i][s[i]-'a']++;
	}


	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char c;
		int l, r;
		cin >> c >> l >> r;
		cout << psum[r+1][c - 'a'] - psum[l][c - 'a'] <<'\n';
	}



	return 0;
}

https://www.acmicpc.net/problem/10986

#include <bits/stdc++.h>
using namespace std;

int n, m;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	long long ans = 0;

	int tmp = 0;

	vector<long long> map(m, 0);
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		tmp = (tmp + a)%m;

		map[tmp]++;
		if (tmp == 0) {
			ans++;
		}
	}

	for (int i = 0; i < m; i++) {
		ans += map[i] * (map[i] - 1) / 2;
	}

	cout << ans << '\n';


	return 0;
}

https://www.acmicpc.net/problem/16236

#include <bits/stdc++.h>
using namespace std;

int n, arr[21][21];
struct Shark {
	int x, y, size=2, cnt =0;
	void sizeUp() {
		if (cnt >= size) {
			cnt -= size;
			size++;
		}
	}
};

struct Node {
	int x, y , dist;

	bool operator<(const Node& b) const {
		if (dist == b.dist) {
			if (x == b.x) {
				return y > b.y;
			}
			return x > b.x;
		}
		else return dist > b.dist;
	}
};

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool ch[21][21];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	Shark sk;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				arr[i][j] = 0;
				sk.x = i;
				sk.y = j;
			}
		}
	}

	priority_queue<Node> Q;
	Q.push({ sk.x, sk.y, 0 });
	ch[sk.x][sk.y] = 1;

	int ans = 0;

	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int d = Q.top().dist;
		Q.pop();

		if (arr[x][y]!=0 && arr[x][y] < sk.size) {
			arr[x][y] = 0;
			sk.cnt++;
			sk.sizeUp();

			memset(ch, 0, sizeof(ch));
			ans += d;

			while (!Q.empty()) {
				Q.pop();
			}
			Q.push({ x,y,0 });
			ch[x][y] = 1;
			continue;
		}


		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= n || ch[nx][ny]) continue;
			if (arr[nx][ny] <= sk.size) {
				ch[nx][ny] = 1;
				Q.push({ nx,ny,d + 1 });
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

https://www.acmicpc.net/problem/11660

#include <bits/stdc++.h>
using namespace std;


int n, m;
int psum[1025][1025];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int a;
			cin >> a;
			psum[i + 1][j + 1] = psum[i + 1][j] + psum[i][j + 1] - psum[i][j] + a;
		}
	}

	for (int i = 0; i < m; i++) {
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << psum[x2][y2] - psum[x2][y1 - 1] - psum[x1 - 1][y2] + psum[x1-1][y1-1] << '\n';
	}



	return 0;
}