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

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

int ans[20001], v, e, st;

struct Node {
	int n, d;

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

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

	fill(ans, ans + 20001, -1);

	cin >> v >> e;
	cin >> st;

	vector<pair<int, int> > m[20001];

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

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

	while (!Q.empty()) {
		int cur_node = Q.top().n;
		int cur_dist = Q.top().d;
		Q.pop();

		if (ans[cur_node] == -1) {
			ans[cur_node] = cur_dist;

			for (int i = 0; i < m[cur_node].size(); i++) {
				int nx = m[cur_node][i].first;
				if (ans[nx] == -1) {
					int nd = m[cur_node][i].second + cur_dist;
					Q.push({ nx,nd });
				}
			}
		}
	}


	for (int i = 1; i <= v; i++) {
		if (ans[i] == -1) cout << "INF\n";
		else cout << ans[i] << '\n';
	}


	return 0;
}

우선순위큐 최소힙을 이용해

다익스트라 알고리즘으로 풀 수 있다.

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

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

string a, t;

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

	cin >> a >> t;

	int l = 0, r = t.length() - 1, turn = 0;
	deque<char> left, right;

	while (l <= r) {
		if (turn % 2 == 0) {
			left.push_back(t[l++]);

			if (left.size() >= a.length()) {
				bool is_same = true;
				for (int i = 0; i < a.length(); i++) {
					if (a[a.length() - 1 - i] != left[left.size() - 1 - i]) {
						is_same = false;
						break;
					}
				}
				if (is_same) {
					for (int i = 0; i < a.length(); i++)
						left.pop_back();

					turn++;
				}
			}
			
		}
		else {

			right.push_front(t[r--]);
			if (right.size() >= a.length()) {

				bool is_same = true;
				for (int i = 0; i < a.length(); i++) {
					if (a[i] != right[i]) {
						is_same = false;
						break;
					}
				}
				if (is_same) {
					for (int i = 0; i < a.length(); i++)
						right.pop_front();

					turn++;
				}
			}
		}

	}

	while (!right.empty()) {
		left.push_back(right.front());
		right.pop_front();

		if (left.size() >= a.length() && left.back() == a[a.length() - 1]) {
			bool is_same = true;
			for (int i = 0; i < a.length(); i++) {
				if (a[a.length() - 1 - i] != left[left.size() - 1 - i]) {
					is_same = false;
					break;
				}
			}
			if (is_same) {
				for (int i = 0; i < a.length(); i++)
					left.pop_back();
			}
		}
	}

	while (!left.empty()) {
		cout << left.front();
		left.pop_front();
	}
	cout << '\n';

	return 0;
}

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

Segment Tree 공부하기

겉보기에는 구간합을 구하는 간단한 문제처럼보이지만

Segment Tree 자료구조를 이해해야 풀 수 있는 문제입니다.

하단 링크에 설명이 잘 되어 있습니다.

https://www.acmicpc.net/blog/view/9

하단의 영상은 제가 올린 건 아니고

유튜브에 개발자영맨님이 만든 Segment Tree 강의인데

설명이 잘 되어 있어서 같이 올려봅니다.

https://www.youtube.com/watch?v=075fcq7oCC8 

https://www.youtube.com/watch?v=ahFB9eCnI6c 

문제풀이코드 C++

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int n, m, k;
long long arr[1000003];

struct SegmentTree {
	int N;
	vector<long long> tree;

	long long merge(long long left, long long right) {
		return left + right;
	}

	long long buildRec(int node, int nodeLeft, int nodeRight) {
		if (nodeLeft == nodeRight) {
			return tree[node] = arr[nodeLeft];
		}

		int mid = (nodeLeft + nodeRight) / 2;

		long long LeftVal = buildRec(2 * node, nodeLeft, mid);
		long long RightVal = buildRec(2 * node + 1, mid + 1, nodeRight);

		return tree[node] = merge(LeftVal, RightVal);
	}

	void init(int Size) {
		N = Size;
		tree.resize(N * 4);
		buildRec(1, 0, N - 1);
	}

	long long queryRec(int left, int right, int node, int nodeLeft, int nodeRight) {
		// 노드 구간이 구하는 구간 밖일 경우 0 리턴
		if (nodeRight < left || right < nodeLeft) {
			return 0;
		}

		if (left <= nodeLeft && nodeRight <= right) {
			return tree[node];
		}

		int mid = (nodeLeft + nodeRight) / 2;
		long long leftVal = queryRec(left, right, 2 * node, nodeLeft, mid);
		long long rightVal = queryRec(left, right, 2 * node + 1, mid + 1, nodeRight);

		return merge(leftVal, rightVal);
	}


	long long query(int left, int right) {
		return queryRec(left, right, 1, 0, N - 1);
	}

	long long updateRec(int index, long long newValue, int node, int nodeLeft, int nodeRight) {
		if (nodeRight < index || index < nodeLeft) return tree[node];
		
		if (nodeLeft == nodeRight) {
			return tree[node] = newValue;
		}

		int mid = (nodeLeft + nodeRight) / 2;
		long long leftVal = updateRec(index, newValue, 2 * node, nodeLeft, mid);
		long long rightVal = updateRec(index, newValue, 2 * node + 1, mid + 1, nodeRight);


		return tree[node] = merge(leftVal, rightVal);
	}


	void update(int index, long long newValue) {
		updateRec(index, newValue, 1, 0, N - 1);
	}

};


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

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	SegmentTree st;
	st.init(n);

	for (int i = n + 2; i <= n + m + k + 1; i++) {
		int a, b;
		long long c;
		cin >> a >> b >> c;

		if (a == 2) {
			cout << st.query(b - 1, c - 1) << '\n';
		}
		else {
			st.update(b - 1, c);
		}
	}

	
	return 0;
}

백준 2042 반례

5 1 1
1
2
3
4
5
1 2 300000000000
2 2 5

answer: 300000000012

a, b, c 를 입력 받을 때 c를 long long 형으로 입력받아야합니다.

업데이트를 해주는 과정에서도 long long 자료형을 유지해 업데이트를 진행해야합니다.

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

1.문제설명

INPUT

12ab112ab2ab
12ab

첫 째로 일반 문자열이 주어지고

두번째로 폭발하는 문자열이 주어진다.

1. 일반 문자열 내에 폭발 문자열이 있을 경우 폭발 문자열을 없애줘야한다.

2. 폭발 문자열을 없앤 결과 또 폭발문자열이 포함되어 있을 경우 다시 폭발문자열을 없애줘야한다.

1과 2를 문자열 내에 폭발문자열이 없을 때까지 반복한다.

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

그동안 습관적으로 STL을 사용하던 버릇에 긴장감을 주는 문제다.

스택을 직접 구현해야 가장 편하게 풀 수 있다.

입력받은 첫째 문자열을 돌면서 stack에 char 문자 하나씩 넣어주다가

stack의 가장 위 문자가 폭발 문자열의 마지막 문자와 동일하면

그 문자가 폭발 문자열을 이루고 있는지 확인하고,

폭발문자열이 발견되면 그만큼 pop 해주어야한다.

pop 해주는 건 p 변수를 폭발문자열의 크기 만큼 빼주면 쉽게 구현할 수 있다.

3.문제풀이코드 C++

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

char stack[1000001];
int p = 0;
string str;
string bomb;

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

	cin >> str;
	cin >> bomb;
	
	for (int i = 0; i < str.length(); i++) {
		stack[p++] = str[i];

		if (p >= bomb.length() && stack[p - 1] == bomb[bomb.length() - 1]) {
			bool is_same = true;
			for (int j = 0; j < bomb.length(); j++) {
				if (bomb[j] != stack[p - bomb.length() + j]) {
					is_same = false;
				}
			}
			if (is_same) {
				p -= bomb.length();
			}
		}
	}

	if (p == 0) {
		cout << "FRULA" << '\n';
	}
	else {
		for (int i = 0; i < p; i++) {
			cout << stack[i];
		}
		cout << '\n';
	}


	return 0;
}

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

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

int n, k;
string str;

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

	cin >> n >> k;
	cin >> str;

	deque<char> Q;

	for (int i = 0; i < str.length(); i++) {
		while (k && !Q.empty() && Q.back() < str[i]) {
			Q.pop_back();
			k--;
		}
		Q.push_back(str[i]);
	}

	for (int i = 0; Q.size() - k; i++) {
		cout << Q.front();
		Q.pop_front();
	}

	return 0;
}

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

1.문제설명

......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.

12 * 6 으로 Input이 주어질 때

같은 색깔인 칸이 상하좌우로 인접하여 4개 이상 있다면 모두 터트려줍니다.

......
......
......
......
......
......
......
......
.Y....
.YG...
..YG..
..YGG.

더이상 터질 수 있는 뿌요가 없다면

중력에 의해 공중에 있는 뿌요는 밑으로 떨어지게 됩니다.

......
......
......
......
......
......
......
......
......
..G...
.YYG..
.YYGG.

다시 터트리고 채워주고 반복하면서

터트리는 과정을 몇번 할 수 있는지 세면 되는 문제입니다.

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

이 문제는 시뮬레이션 문제로 두가지 과정을 구현해주면 됩니다.

1. 뿌요 터트리기

2. 뿌요 떨어트리기

뿌요 터트리기는 BFS를 돌면서 같은 뿌요가 있다면 몇개있는지 세주고 4개 이상 있다면

같은 뿌요들을 저장해준뒤 char '.'로 바꿔주면 쉽게 구현할 수 있습니다.

뿌요 떨어트리기는 for문을 돌면서 맨 아래칸부터 시작하여 위칸을 돌면서

뿌요가 있다면 뿌요가 없는 맨 아래칸과 바꿔주면 됩니다.

처음 주어지는 INPUT이 중력에 의해 떨어진 상태가 아닐수도 있기 때문에

맨 처음 뿌요를 일단 다 떨어트리고 시작해야합니다.

3.문제풀이코드 C++

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

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

void fall() {
	for (int i = 0; i < 6; i++) {
		for (int j = 11; j >= 0; j--) {
			if (arr[j][i] == '.') {
				for (int k = j - 1; k >= 0; k--) {
					if (arr[k][i] != '.') {
						swap(arr[j][i], arr[k][i]);
						break;
					}
				}
			}
		}
	}
}


bool bomb() {
	bool ch[12][6];
	memset(ch, 0, sizeof(ch));
	queue<pair<int, int> > Q;
	bool bombed = false;

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

			if (ch[i][j] == 0 && arr[i][j] != '.') {

				vector<pair<int, int> > v;
				char color = arr[i][j];
				int cnt = 1;
				ch[i][j] = 1;
				v.push_back({ i,j });
				Q.push({ i,j });

				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();


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

						if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6 || ch[nx][ny] == 1) continue;
						if (arr[nx][ny] == color) {
							cnt++;
							ch[nx][ny] = 1;
							Q.push({ nx,ny });
							v.push_back({ nx,ny });
						}
					}
				}

				if (cnt >= 4) {
					bombed = true;
					for (int k = 0; k < v.size(); k++) {
						arr[v[k].first][v[k].second] = '.';
					}
				}
			}
		}
	}

	return bombed;
}



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


	for (int i = 0; i < 12; i++) {
		cin >> arr[i];
	}
	// 필드에 뿌요를 모두 두고 일단 떨어트린다. 
	fall();

	//1.터트린다 - 개수 0이면 끝
	//2. 내린다
	//1.2 반복
	int ans = 0;

	while (1) {
		if (bomb()) {
			ans++;
			fall();
		}
		else {
			break;
		}
	}

	cout << ans << '\n';

	return 0;
}

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

1.문제설명

폭탄은 3초가 지나야 터진다.

폭탄이 터지면 폭탄이 있던 자리와 인접한 상하좌우칸이 .이 된다.

폭탄이 터지는 인접 상하좌우에 폭탄이 있을 경우 상하좌우에 있던 폭탄은 그냥 사라진다.

2.접근방법

3초가 되는 폭탄을 따로 배열이나 벡터에 저장했다가

각각 터트려야 쉽게 구현할 수 있다.

만약 3초가 지난 폭탄을 따로 저장하지 않고 순차적으로 터트릴 경우

인접한 3초 폭탄이 사라져 다른 결과를 얻게 된다.

다음 표에서 3이 써있는 폭탄은 이제 터지는 폭탄이라고 두고

O는 아직 터지지 않는 폭탄이라 생각하자.

그냥 무지성으로 3인 폭탄을 for문으로 돌며 터트리면 다음과 같은 결과를 얻는다

오른쪽에 있던 3폭탄이 터지지 못하고 그냥 묻혀버리고 만다.

다른 벡터에 3인 폭탄의 좌표를 모두 저장한 후 벡터에서 for문을 돌면서 터트리면 

이런 옳은 결과를 얻을 수 있다.

많은 시뮬레이션 문제에서 이렇게 정보를 저장한 후 실행하는 방법이 유용하게 쓰인다.

단순히 순차적으로 돌다보면 문제가 생기는 경우가 많다.

3.문제풀이코드 C++

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

int r, c, n, T;

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


void print() {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (a[i][j] == -1) {
				cout << '.';
			}
			else cout << 'O';
		}
		cout << '\n';
	}
}

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

	cin >> r >> c >> n;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			char tmp;
			cin >> tmp;
			if (tmp == 'O') {
				a[i][j] = 0;
			}
			else {
				a[i][j] = -1;
			}
		}
	}
	
	if (T == n) {
		print();
		return 0;
	}


	T++;
	// 첫 1초 아무것도 안함 
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (a[i][j] == 0) {
				a[i][j]++;
			}
		}
	}
	if (T == n) {
		print();
		return 0;
	}

	
	T++;
	//2초 모든칸 폭탄 설치 
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			a[i][j]++;
		}
	}
	if (T == n) {
		print();
		return 0;
	}



	while(T<n) {

		T++;
		vector<pair<int, int> > v;
		
	
		// 아무것도 안함 
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (a[i][j] >= 0) a[i][j]++;
				if (a[i][j] == 3) {
					v.push_back({ i,j });
				}
			}
		}


		for (int i = 0; i < v.size(); i++) {
			a[v[i].first][v[i].second] = -1;
			for (int k = 0; k < 4; k++) {
				int nx = v[i].first + dx[k];
				int ny = v[i].second + dy[k];
				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				a[nx][ny] = -1;
			}
		}

		v.clear();
		if (T == n) break;


		T++;


		// 폭탄 설치 
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				a[i][j]++;
				if (a[i][j] == 3) v.push_back({ i,j });
			}
		}
		for (int i = 0; i < v.size(); i++) {
			a[v[i].first][v[i].second] = -1;
			for (int k = 0; k < 4; k++) {
				int nx = v[i].first + dx[k];
				int ny = v[i].second + dy[k];
				if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
				a[nx][ny] = -1;

			}
		}


	}

	
	print();

	return 0;
}

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

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

int r, c, t, arr[51][51], cleaner;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


struct Dust {
	int x, y, q;
};


int ans() {
	int cnt = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (arr[i][j] > 0) {
				cnt += arr[i][j];
			}
		}
	}
	return cnt;
}


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

	cin >> r >> c >> t;


	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == -1) {
				cleaner = i;
			}
		}
	}

	int clean_up = cleaner - 1;
	int clean_down = cleaner;

	//1.미세먼지 확산
	//2. 공기 청정기 이동 
	for (int T = 1; T <= t; T++) {

		vector<Dust> d;

		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (arr[i][j] >= 5) {
					d.push_back({ i,j,arr[i][j] });
				}
			}
		}

		//확산 
		for (int i = 0; i < d.size(); i++) {
			int spread = 0;
			if (d[i].q >= 5) {
				for (int k = 0; k < 4; k++) {
					int nx = d[i].x + dx[k];
					int ny = d[i].y + dy[k];

					if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
					if (arr[nx][ny] == -1)continue;
					arr[nx][ny] += (d[i].q / 5);
					spread++;

				}
				arr[d[i].x][d[i].y] -= (d[i].q / 5) * spread;
			}
		}

		// 공기청정기 작동 
		for (int i = clean_up - 1; i >= 0; i--) {
			arr[i + 1][0] = arr[i][0];
		}

		for (int i = clean_down; i < r; i++) {
			arr[i][0] = arr[i + 1][0];

		}

		for (int i = 0; i < c-1; i++) {
			arr[0][i] = arr[0][i + 1];
			arr[r - 1][i] = arr[r - 1][i + 1];
		}

		for (int i = 0; i < clean_up ; i++) {
			arr[i][c - 1] = arr[i + 1][c - 1];
		}

		for (int i = r-1; i > clean_down; i--) {
			arr[i][c - 1] = arr[i - 1][c - 1];
		}

		for (int i = c - 1; i > 1; i--) {
			arr[clean_up][i] = arr[clean_up][i - 1];
			arr[clean_down][i] = arr[clean_down][i - 1];
		}
		arr[clean_up][1] = 0;
		arr[clean_down][1] = 0;


		arr[clean_up][0] = -1;
		arr[clean_down][0] = -1;


	}

	int ans = 0;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (arr[i][j] > 0) ans += arr[i][j];
		}
	}

	cout << ans << '\n';

	return 0;
}