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

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

vector<int> gun;


bool distance(int x, int y, int L) {

	bool ans = false;
	if (y > L) return false;

	int s = 0;
	int e = gun.size() - 1;

	while (s <= e) {

		int mid = (s + e) / 2;

		if (abs(gun[mid] - x) + y <=L) {
			ans = true;
			break;
		}
		else if (gun[mid] > x) {
			e = mid - 1;
		}
		else {
			s = mid + 1;
		}
	}


	return ans;
}


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

	int m, n, l;
	cin >> m >> n >> l;
	

	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		gun.push_back(tmp);
	}

	sort(gun.begin(), gun.end());

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		if (distance(x, y ,l)) cnt++;
	}

	cout << cnt << '\n';


	

	return 0;
}

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

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

int w, h;
int stx, sty, enx, eny;
int arr[101][101];
int dis[101][101];

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

struct Node {
	int x, y, dist, direction;

	bool operator<(const Node& b) const {
		return dist > b.dist;
	}
};



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(dis, 0x3f, sizeof(dis));

	cin >> w >> h;
	bool st = false;

	for (int i = 0; i < h; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < w; j++) {
			if (s[j] == '*') {
				arr[i][j] = -1;
			}
			else if (s[j] == 'C' && st == false) {
				stx = i;
				sty = j;
				st = true;
			}
			else if (s[j] == 'C' && st == true) {
				enx = i;
				eny = j;
			}
		}
	}


	priority_queue<Node> Q;

	dis[stx][sty] = 0;

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

		if (nx < 0 || nx >= h || ny < 0 || ny >= w || arr[nx][ny]==-1 ) continue;

		Q.push({ nx,ny,0,i });
	}


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


		if (dis[x][y] < dist) continue;
		dis[x][y] = dist;

		if (x == enx && y == eny) {
			cout << dist << '\n';
			return 0;
		}

		for (int i = 0; i < 4; i++) {
			if (abs(i - direction) == 2) continue;

			int nx = x + dx[i];
			int ny = y + dy[i];
			int nd = dist;
			if (i != direction) {
				nd++;
			}
			if (nx < 0 || nx >= h || ny < 0 || ny >= w || arr[nx][ny] == -1) continue;
			if (dis[nx][ny] < nd) continue;
			Q.push({ nx,ny,nd,i });
		}
	}



	//for (int i = 0; i < h; i++) {
	//	for (int j = 0; j < w; j++) {
	//		if (dis[i][j] > 10) cout << '*';
	//		else cout << dis[i][j];
	//	}
	//	cout << '\n';
	//}


	return 0;
}

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

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

struct Count {
	int x, cnt;

	bool operator<(const Count& b) const {
		if (cnt == b.cnt) {
			return x < b.x;
		}
		return cnt > b.cnt;
	}
};

int arr[9000];

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

	int n;
	vector<int> v;

	cin >> n;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		sum += tmp;

		arr[tmp + 4000]++;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	vector<Count> freq;

	for (int i = 0; i < 9000; i++) {
		if (arr[i] > 0) {
			freq.push_back({ i,arr[i] });
		}
	}

	sort(freq.begin(), freq.end());

	int freq_ans = freq[0].x - 4000;
	if (freq.size() >= 2 && freq[0].cnt == freq[1].cnt) {
		freq_ans = freq[1].x - 4000;
	}
	

	double mean = sum / (double)n;

	int mm;
	if (mean >= 0) {
		mm = int(mean + 0.5);
	}
	else {
		mm = int(mean - 0.5);
	}

	cout << mm << '\n';
	cout << v[n / 2] << '\n';

	cout << freq_ans << '\n';

	cout << v[v.size() - 1] - v[0] << '\n';
	
	return 0;
}

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

1.문제설명

문제가 꽤 복잡하다.

단순하게 정리하면

시작점과 꼭 경유해야하는 간선이 주어졌을 때 해당하는 노드가

문제에서 원하는 도착점이 될 수 있는지

판단해야한다.

2.접근방법[알고리즘]

https://www.acmicpc.net/board/view/47684

도착점 후보가 진짜로 도착점인지 확인하려면

시작점으로부터 경유지를 경유하고 도착점 후보에 도착한 거리와

시작점으로부터 도착점 후보까지의 최단 거리가 같아야한다.

이를 바탕으로 최단거리에 도달 했을 때 g와 h의 간선을 지났다면

해당 도착점후보가 도착점이 될 수 있음을 알 수 있다.

그래서 g-h 간선을 지났는지 여부를 따로 저장해주면서 확인하면 이 문제를 해결 할 수 있다.

다만 핵심은 priority_queue를 이용할 때

거리와 노드가 동일하다면 g-h간선이 지난 여부가 true인 상태가

우선으로 pop 되도록 설계해야 한다.

3.문제풀이코드 C++

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

struct Node {
	int x, d;
	bool ispassing;

	bool operator<(const Node& b) const {
		if (x == b.x && d == b.d) {
			return ispassing < b.ispassing;
		}
		return d > b.d;
	}

};


bool dijkstra(vector<pair<int, int> >* v, int st, int en, int g, int h) {
	bool passed = false;

	int dist[2001];
	memset(dist, 0x3f, sizeof(dist));

	priority_queue<Node> Q;
	Q.push({ st,0,0 });

	while (!Q.empty()) {
		int x = Q.top().x;
		int d = Q.top().d;
		bool p = Q.top().ispassing;

		Q.pop();

		if (dist[x] <= d) continue;
		dist[x] = d;

		if (x == en) {
			if (p) {
				passed = true;
			}

			break;
		}

		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int nd = d + v[x][i].second;

			if (dist[nx] > nd) {
				if (p) {
					Q.push({ nx,nd,p });
				}
				else {
					if ((x == g && nx == h) || (x == h && nx == g)) {
						Q.push({ nx,nd,1 });
					}
					else {
						Q.push({ nx,nd,0 });
					}
				}
			}

		}

	}
	return passed;
}

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

	int tt;
	cin >> tt;

	for (int T = 0; T < tt; T++) {

		vector<pair<int, int> > v[2001];

		int n, m, t;
		int s, g, h;
		cin >> n >> m >> t;
		cin >> s >> g >> h;

		for (int i = 0; i < m; i++) {
			int a, b, d;
			cin >> a >> b >> d;

			v[a].push_back({ b,d });
			v[b].push_back({ a,d });
		}

		vector<int> ans;
		for (int i = 0; i < t; i++) {
			int x;
			cin >> x;


			if (dijkstra(v, s, x, g, h)) {
				ans.push_back(x);
			}

		}

		sort(ans.begin(), ans.end());

		for (int i = 0; i < ans.size(); i++) {
			cout << ans[i] << ' ';
		}

		cout << '\n';

	}


	return 0;
}

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

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

int n, m, st, en;

pair<int, int> dist[1001]; //거리 , 이전노드 저장 

vector<pair<int, int> > v[1001];

struct Node {
	int x, ex ,d;
	bool operator<(const Node& b)const {
		return d > b.d;
	}
};

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


	memset(dist, 0x3f, sizeof(dist));

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b, c });
	}

	cin >> st >> en;
	priority_queue<Node> Q;
	Q.push({ st,-1,0 });

	vector<int> ans;


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

		if (dist[x].first <= d) continue;

		dist[x].first = d;
		dist[x].second = ex;


		if (x == en) {
			int a = en;

			while (a != -1) {
				ans.push_back(a);
				a = dist[a].second;
			}

			cout << d << '\n';
			cout << ans.size() << '\n';

			for (int i = ans.size() - 1; i >= 0; i--) {
				cout << ans[i] << ' ';
			}
			return 0;
		}


		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int nd = d + v[x][i].second;

			if (dist[nx].first > nd) {
				Q.push({ nx,x,nd });
			}
		}
	}



	return 0;
}

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

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


int res[1001];

struct Node {
	int x, dist;

	bool operator<(const Node& b) const{
		return dist > b.dist;
	}
};

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

	memset(res, 0x3f, sizeof(res));

	int n, m, st, end;
	vector<Node> map[1001];

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		map[a].push_back({ b,c });
	}
	cin >> st >> end;

	priority_queue<Node> Q;

	Q.push({ st,0 });
	res[st] = 0;

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

		
		if (res[x] < d) continue;
		
		res[x] = d;
		if (x == end) {
			cout << d << '\n';
			return 0;
		}

		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i].x;
			int nd = map[x][i].dist;

			if (res[nx] > nd + d) {
				Q.push({ nx,nd + d });
			}

		}
	}

	return 0;
}

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

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

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

struct Ball {
	int idx, color, size;

	bool operator<(const Ball& b) const {
		if (size == b.size) return idx < b.idx;
		else return size < b.size;
	}
};

int color[200001], sum;
int ans[200001];

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

	cin >> n;
	vector<Ball> v;
	v.push_back({ 0,0,0 });

	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ i,a,b });
	}
	sort(v.begin(), v.end());

	for (int i = 1, j = 1; i <= n; i++) {
		while (v[i].size > v[j].size) {
			sum += v[j].size;
			color[v[j].color] += v[j].size;
			j++;
		}
		ans[v[i].idx] = sum - color[v[i].color];
	}



	for (int i = 1; i <= n; i++) {
		cout << ans[i] << '\n';
	}

	return 0;
}

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

접근방법[알고리즘]

2차원 배열로 분수 형태를 나타낼 수 있다.

분수를 기약분수로 나타내기 위해 최대공약수를 이용해야 한다.

문제풀이코드 C++

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

int GCD(int a, int b) {
	if (a < b) swap(a, b);
	if (a % b == 0) {
		return b;
	}
	else {
		return GCD(b, a % b);
	}
}

bool ch[2001][2001];

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


	int a, b;
	cin >> a >> b;
	int ans = 1;

	for (int i = a; i <= b; i++) {
		for (int j = 1; j < i; j++) {
			int mod = GCD(i, j);
			int a = j / mod;
			int b = i / mod;
			if (ch[a][b] == 0) {
				ans++;
				ch[a][b] = 1;
			}
		}
	}


	cout << ans <<'\n';

	return 0;
}