이것 저것 &

문제링크: 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;
}

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

접근방식

1. 두 가지 순회방법을 통해서 남은 한가지 순회방법을 찾을 수 있다.

전위는 root노드 - root기준 왼쪽 자식노드 - root기준 오른쪽 자식노드 순으로 표시되고

중위는 root기준 왼쪽 자식노드 - root노드 - root기준 오른쪽 자식노드 순으로 표시된다.

-> 그렇다면 후위순회 함수를 구현하며 노드 값을 출력하며 결과를 도출할 수 있다. 

2. 전위 순회함수로 탐색을 하며 root값에 해당하는 중위순회값을 매개변수로 전달하며 진행

3. 재귀함수, 분할정복으로 구현하였다.

문제풀이 

1. 분할정복으로 구현 

2. 전위순회를 기준으로 root 노드를 출력하는 형태

아래는 정답 코드입니다.

#include <iostream>
using namespace std;

int t;
int n;
int pre[1000] = { 0, };
int ino[1000] = { 0, };

void solved(int pl, int pr, int il, int ir) {
	if ((pr - pl) == 0) {
		cout << pre[pl] << ' ';
		return;
	}

	for (int i = 0; i <= pr - pl; i++) {
		if (pre[pl] == ino[il + i]) {
			solved(pl + 1, pl + i, il, il + i - 1);
			solved(pl + i + 1, pr, il + i + 1, ir);
			cout << pre[pl] << ' ';
			return;
		}

	}

}

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

	cin >> t;

	while (t--) {
		cin >> n;

		for (int i = 0; i < n; i++)
			cin >> pre[i];
		for (int i = 0; i < n; i++)
			cin >> ino[i];

		solved(0, n - 1, 0, n - 1);
		cout << "\n";
	}

	cout << "\n";
	return 0;
}

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

최소 스패닝 트리를 만드는 문제입니다.

접근방식

1. 최소 스패닝 트리 알고리즘에 대해서 인지하고 있어야 한다.

2. MST는 크게 크루스칼 알고리즘, 프림 알고리즘이 존재한다. 

3. 나는 그 중에서 우선순위 큐를 사용한 프림알고리즘으로 문제를 해결했다. 

문제풀이 

1. 우선순위 큐에 1과 인접한 그래프 삽입 

2. visited로 방문 여부를 판단하며, 정점 - 1 개까지 반복 

 일반적인 bfs와 흡사한 방식

3. 전체 비용의 합 - 최소 경로의 합

아래는 정답코드입니다.

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

vector <pair<int, int>> vec[200000];
bool visited[200000];
int m, n;
int result = 0;

void prim() {

	priority_queue <pair<int, int>> pq;
	visited[0] = true;
	for (int i = 0; i < vec[0].size(); i++) {
		pq.push(make_pair(-1 * vec[0][i].second, vec[0][i].first));
	}

	while (!pq.empty()) {
		int cost = pq.top().first * -1;
		int pos = pq.top().second;
		pq.pop();

		if (visited[pos] == false) {
			visited[pos] = true;
			result -= cost;
			
			for (int i = 0; i < vec[pos].size(); i++) {
				int ncost = vec[pos][i].second;
				int npos = vec[pos][i].first;
				if (visited[npos] == false)
					pq.push(make_pair(ncost*-1, npos));
			}

		}


	}

}

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

	while (1) {
		cin >> m >> n;
		if (m == 0 && n == 0)
			break;

		for (int i = 0; i < m; i++)
			vec[i].clear();

		result = 0;
		int from, to, cost;
		for (int i = 0; i < n; i++) {
			cin >> from >> to >> cost;
			vec[from].push_back(make_pair(to, cost));
			vec[to].push_back(make_pair(from, cost));
			result += cost;
		}

		memset(visited, 0, sizeof(visited));
		
		prim();
		cout << result << endl;
	}

	
	return 0;
}