이것 저것 &

문제링크: https://www.acmicpc.net/problem/3197

접근방식

1. 간만에 어려웠던 문제... 동작 자체는 쉽지만 시간초과, 메모리 초과때문에 삽질을 너무 많이했슴니다

2. 일반적인 얼음 녹이기, bfs를 사용하게 되며 매번 1500X1500짜리 필드를 탐색해주어야 하기때문에

O(1500*1500*cnt)로 당연히 시간 초과...

3. 이미 탐색한 영역은 넘어가고 새로운 영역만 bfs를 통해서 탐색할 수 있도록 구현하는 것이 핵심

문제풀이 

1. 백조하나를 기준으로 bfs를 진행함. 이때 다음번에 녹을 얼음을 임시큐에 저장해두었다가 bfs에서 사용하는 큐에 저장한다.

이렇게 행동함으로서 매번 bfs에는 새로 녹은 지점에만 탐색을 할 수 있도록 만드는 것이다. 

2. bfs이후에는 얼음을 녹이는 작업을 진행함. 기존 물좌표들은 pop으로 큐에서 빼고 얼음에서 물로 변한 위치들만 다시 큐로 넣어주는 방식이다 

아래는 정답코드!

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

typedef struct a {
	int y, x;
}dir;

dir ar[4] = { {1,0},{0,1},{-1,0},{0,-1} };

int r, c;
string arr[1500]; // 0 base
vector <dir> swan; // swan
queue <dir> vec; //water

queue <dir> q;
bool visited[1500][1500] = { 0, };


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		cin >> arr[i];
		for (int j = 0; j < c; j++) {
			if (arr[i][j] == 'L') {
				arr[i][j] = '.';
				swan.push_back({ i, j });
			}
			if (arr[i][j] == '.')
				vec.push({ i,j });
		}
	}

	q.push({ swan[0].y,swan[0].x });
	visited[swan[0].y][swan[0].x] = 1;

	for (int cnt = 0;; cnt++) {
		queue <dir> nq; //다음 단계 큐에 포함되는 값 

		bool flag = 0;
		while (!q.empty()) {
			int y = q.front().y;
			int x = q.front().x;
			q.pop();

			if (y == swan[1].y && x == swan[1].x) {
				flag = 1;
				break;
			}

			for (int i = 0; i < 4; i++) {
				int ny = y + ar[i].y;
				int nx = x + ar[i].x;
				if (ny < 0 || ny >= r || nx < 0 || nx >= c || visited[ny][nx])
					continue;

				visited[ny][nx] = 1;
				if (arr[ny][nx] == 'X')
					nq.push({ ny,nx });
				else if (arr[ny][nx] == '.') {
					q.push({ ny , nx });
				}
			}
		}


		if (flag) {
			cout << cnt << endl;
			return 0;
		}

		q = nq;

		int ws = vec.size();
		while (ws--) {

			int y = vec.front().y;
			int x = vec.front().x;
			vec.pop();

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

				if (ny < 0 || ny >= r || nx < 0 || nx >= c )
					continue;
				if (arr[ny][nx] == 'X') {
					arr[ny][nx] = '.';
					vec.push({ ny,nx });
				}
			}



		}


	}

	return 0;
}

문제링크: https://www.acmicpc.net/problem/15591

접근방식

1. 문제를 이해하는게 힘들었던 문제..;;

3. 결국 탐색을 통해서 동영상마다 유사도를 저장해주고 문제를 해결하면 되는 문제

4. 우선순위 큐를 사용한 탐색을 고안(굳이 우선순위일 필요가 없을 것 같긴하다)

문제풀이 

1. 우선순위큐를 사용하여 동영상별로 유사도를 도출. dist배열에 저장

코드를 직접 확인하는게 더 빠를 것 같음

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, q;
int a, b, c;
int k, v;
vector <pair<int, int>> vec[5001];
int dist[5001][5001];

void dijkstra(int num) {
	queue <pair<int,int>> que;
	que.push(make_pair(num,2000000000));
	
	while (!que.empty()) {

		int cur = que.front().first;
		int cost = que.front().second;
		que.pop();

		for (int i = 0; i < vec[cur].size(); i++) {
			
			if (dist[num][vec[cur][i].first] != 2000000000)
				continue;
			if (vec[cur][i].second > cost) {
				dist[num][vec[cur][i].first] = cost;
				que.push(make_pair(vec[cur][i].first, cost));
			}
			else {
				dist[num][vec[cur][i].first] = vec[cur][i].second;
				que.push(make_pair(vec[cur][i].first, vec[cur][i].second));
			}

		}


	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> q;
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b >> c;
		vec[a].push_back(make_pair(b, c));
		vec[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			dist[i][j] = 2000000000;
		dijkstra(i);
	}

	for (int i = 0; i < q; i++) {
		cin >> k >> v;
		int cnt = 0;
	
		for (int j = 1; j <= n; j++) {
			if (j == v)
				continue;
			if (dist[v][j] >= k)
				cnt++;
		}
		cout << cnt << "\n";
	}

	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << dist[i][j] << ' ';
		}
		cout << endl;
	}*/

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1655

접근방식

1. 시간 제한이 0.1초인 것을 보고 일반적인 정렬 방식을 사용하면 안되는 것을 인지

2. 시간 제한상 nlogn번만에 도출해야 하는 것을 인지하였고 max 힙, min 힙 2개를 사용해서 구현하는 방법을 고안

문제풀이 

1. 음.. 설명하기 어려워서 잘 설명된 링크를 가져왔습니다! ㅋㅋㅋㅋㅋ

https://o-tantk.github.io/posts/finding-median/

너무 잘 정리하셨더라구요! 

2. 위에서 설명하는 방식처럼 max힙에는 기준점보다 작은 값, min힙에는 기준값보다 큰 값들로 구성

정답코드입니다.

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

int n = 0, temp = 0;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	priority_queue <int> mx; //기준보다 작은 값들을 넣을거 (기준포함)
	priority_queue <int> mn; //기준보다 큰 값들을 넣을거 -1곱하면서

	//초기작업
	cin >> n;

	cin >> temp;
	mx.push(temp);
	cout << temp << "\n";

	for (int i = 1; i < n; i++) {
		cin >> temp;
		int sta = mx.top();
		if (sta > temp) {
			if (mx.size() > mn.size()) {
				mx.pop();
				mn.push(sta*-1);
				mx.push(temp);
			}
			else {
				mx.push(temp);
			}

		}
		else if (sta < temp) {
			if (mx.size() == mn.size()) {
				mn.push(temp*-1);
				int mnn = mn.top()*-1;
				mn.pop();
				mx.push(mnn);
			}
			else {
				mn.push(temp*-1);
			}
		}
		else { //sta == temp
			if (mx.size() == mn.size()) {
				mx.push(temp);
			}
			else { //mx가 하나 더 많을 때
				mn.push(temp*-1);
			}
		}

		cout << mx.top() << "\n";

	}


	return 0;
}

문제링크: https://www.acmicpc.net/problem/16918

구현문제입니다.

접근방식

1. 단순구현으로 해결

3. 값이 짝수일때, 홀수일때로 나눠서 풀었다.

4. 짝수일때는 항상 모든 값이 O 

홀수일때는 값이 변화하는 것을 시뮬레이션으로 구현

문제풀이 

1. 짝수일때는 항상 모든 값이 O 

홀수일때는 값이 변화하는 것을 시뮬레이션으로 구현

2. 홀수일때, copyed배열을 만들어서 변화하는 값을 저장해놓는 형식으로 구현 

코드를 직접 확인하는게 더 빠를 것 같음

정답 코드

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

string arr[201];
int r, c, n;
int y_ar[4] = { -1,0,1,0 };
int x_ar[4] = { 0,1,0,-1 };

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

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

	if (n % 2 == 0) {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++)
				cout << 'O';
			cout << "\n";
		}
		return 0;
	}

	string copyed[201];
	for (int i = 0; i < r; i++)
		copyed[i] = arr[i];

	for (int i = 1; i < n; i += 2) {
		for (int j = 0; j < r; j++)
			copyed[j] = arr[j];


		for (int j = 0; j < r; j++)
			for (int k = 0; k < c; k++) 
				if (arr[j][k] == 'O') {
					for (int u = 0; u < 4; u++) {
						int ny = j + y_ar[u];
						int nx = k + x_ar[u];

						if (ny >= 0 && ny < r && nx >= 0 && nx < c)
							copyed[ny][nx] = 'O';
					}
				}

		for (int j = 0; j < r; j++)
			for (int k = 0; k < c; k++) {
				if (copyed[j][k] == 'O')
					arr[j][k] = '.';
				else {
					arr[j][k] = 'O';
				}
			}
	}

	for (int i = 0; i < r; i++)
		cout << arr[i] << "\n";
	

	return 0;
}

문제링크: https://www.acmicpc.net/problem/11779

다익스트라 문제이고, 추가 사항은 최소 경로를 구해야 하는 것이었습니다.

다익스트라는 일반적인 우선순위 큐 방식을 사용하였고, 경로를 저장하기 위해서는 자신의 출발지 값을 저장하게끔 구성을 해주었습니다.

접근방식

1. 일반적인 다익스트라 방식을 생각함

2. 최소 경로를 구하기 위해서 배열을 생성하고 출력

문제풀이 

1. 일반적인 다익스트라 구현

2. 최소 경로를 구하기 위해서 배열을 생성함

해당배열에는 자신의 부모정점을 저장함.

ex) 1->3이면 arr[3] = 1 

3. 해당 배열에서 while문을 사용하여 결과를 도출함 

일부 예외처리를 신경써주어야 했음.

아래 처럼 탐색할 필요없는 정점이라면 가지치기를 해주어야 통과할 수 있는 문제.

		if (cost > dist[cur])
			continue;

가지치기를 해주어야 하는점이 꽤나 까다로운 문제였습니다.

정답코드입니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int cnt = 0;


int dist[1001];
int before_val[1001] = { 0, };
vector <pair<int, int>> vec[1001];
int n, m, s, e; // 도시 개수, 버스의 개수, 출발지, 도착지 

void dijkstra() {

	priority_queue <pair<int, int>> pq;
	pq.push(make_pair(0, s));
	dist[s] = 0; 
	while (!pq.empty()) {

		int cost = - pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		if (cost > dist[cur])
			continue;

		for (int i = 0; i < vec[cur].size(); i++) {
			int ncost = vec[cur][i].second;
			int ncur = vec[cur][i].first;

		
			if (dist[ncur] > cost + ncost) {
				dist[ncur] = ncost + cost;
				pq.push(make_pair(-dist[ncur], ncur));
				before_val[ncur] = cur;
			}
		}



	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		dist[i] = 2000000000;

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

	cin >> s >> e;
	dijkstra();

	vector <int> arr;
	arr.push_back(e);
	int val = before_val[e];
	while (val) {
		arr.push_back(val);
		val = before_val[val];
	}
	

	cout << dist[e] << endl;
	cout << arr.size() << endl;
	for (int i = arr.size() - 1; i >= 0; i--) {
		cout << arr[i] << " ";
	}
	cout << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/2073

전형적인 dp문제

접근방식

1. dp를 사용해서 문제를 해결

dp[n] = max(dp[n], cost)

만약 이전 dp값과 합칠 수 있다면  --- temp = min(dp2[j - arr[i][0]], arr[i][1])

dp[j] = max(dp[j], temp); 

2. 메모리가 생각보다 크다. 이차원 배열로 풀지 말고 before dp 배열을 하나 만들어서 이전 값과 비교해주면서 진행!

문제풀이 

1. dp!

2. 두 점화식을 구현!

아래는 정답코드입니다.

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

int d, p;

int dp[100001];
int dp2[100001];
int arr[351][2];
int temp = 0;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> d >> p;
	for (int i = 1; i <= p; i++) 
		cin >> arr[i][0] >> arr[i][1];
	
	for (int i = 1; i <= p; i++) {
		for (int j = 1; j <= d; j++) {
			if (j == arr[i][0])
				dp[j] = max(dp[j], arr[i][1]);
			
			if (j > arr[i][0]) {
				if (dp2[j - arr[i][0]] != 0) {
					temp = min(dp2[j - arr[i][0]], arr[i][1]);
					dp[j] = max(dp[j], temp);
				}
			}
		}

		for (int j = 1; j <= d; j++) {
			//cout << dp[j] << ' ';
			dp2[j] = dp[j];
		}
		//cout << endl;
	}

	cout << dp[d] << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1976

골드4인걸 보면 어려운 부분이 있는것 같지만.. 그냥 일반적인 BFS로 해결할 수 있는 문제 

접근방식

1. 일반적인 BFS를 통해서 도달이 가능한지 확인할 수 있다.

문제풀이 

1. vector에 좌표를 표시

2. bfs!

아래는 정답코드입니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
bool visited[201] = { 0, };
vector <int> vec[201];
int arr[1001] = { 0, };

void bfs() {
	queue <int> que;
	que.push(arr[0]);
	visited[arr[0]] = 1;

	while (!que.empty()) {
		int pos = que.front();
		que.pop();

		for (int i = 0; i < vec[pos].size(); i++) {
			int npos = vec[pos][i];
			if (visited[npos] == false) {
				visited[npos] = 1;
				que.push(npos);
			}

		}

	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			int temp;
			cin >> temp;
			if (temp) {
				vec[i].push_back(j);
				vec[j].push_back(i);
			}
		}

	for (int i = 0; i < m; i++)
		cin >> arr[i];

	bfs();

	for (int i = 0; i < m; i++)
		if (visited[arr[i]] == false) {
			cout << "NO" << endl;
			return 0;
		}

	cout << "YES" << endl;
	return 0;
}

문제링크: https://www.acmicpc.net/problem/1918

접근방식

1. 후위 표기식으로 변환하는 문제

2. 자료구조중 에서 스택을 사용하면 쉽게 구할 수 있다.

3. 연산자를 스택에 넣어놓으며 진행 

문제풀이 

1. 연산자는 스택에 있는 값과 값을 비교하며 진행

2. *,/ 이 나온 경우

스택에서 *,/ 가 나오면 스택에서 POP하고 결과에 추가

3. +,-가 나온 경우

스택에서 *,/,+,- 가 나오면 스택에서 POP하고 결과에 추가

4. )가 나온 경우

(가 나올때 까지 POP하고 결과에 추가

즉 연산자들의 우선 순위는 *,/ > +,- > ( 순 입니다.

아래는 정답 코드입니다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;

string input;
string result;
stack <char> stk;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> input;

	for (int i = 0; i < input.size(); i++) {
		if (input[i] >= 'A' && input[i] <= 'Z')
			result += input[i];
		else {
			if (stk.empty())
				stk.push(input[i]);
			else {
				if (input[i] == '(')
					stk.push(input[i]);
				else if (input[i] == ')') {
					while (1) {
						char temp = stk.top();
						stk.pop();
						if (temp == '(')
							break;
						result += temp;
					}
				}
				else if (input[i] == '+' || input[i] == '-') {
					while (!stk.empty() && stk.top() != '(') {
						result += stk.top();
						stk.pop();
					}
					stk.push(input[i]);
								
				}
				else if (input[i] == '*' || input[i] == '/') {
					while (!stk.empty() && (stk.top() == '*' || stk.top() == '/')) {
						result += stk.top();
						stk.pop();
					}
					stk.push(input[i]);
					
				}


			}

		}

	}

	while (!stk.empty()) {
		result += stk.top();
		stk.pop();
	}

	cout << result << endl;
	return 0;
}