이것 저것 &

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

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

기본적인 최소스패닝트리(MST)문제

접근방식

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

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

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

문제풀이 

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

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

 일반적인 bfs와 흡사한 방식

아래는 정답 코드입니다. 최소 스패닝 트리에 대해 알고 있는지 확인하는 문제였습니다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;
const int INF = 2000000000;
int n, m;
vector <pair<int, int>> vec[1001];
vector <pair<int, int>> selected;
bool visited[1001] = { 0, };

int result = 0;
void prim() {

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

	visited[1] = 1;
	while (!pq.empty()) {
		int co = pq.top().first * -1;
		int to = pq.top().second;
		pq.pop();

		if (visited[to] == false) {

			visited[to] = true;
			result += co;

			for (int i = 0; i < vec[to].size(); i++) {
				int nto = vec[to][i].first;
				int nco = vec[to][i].second;

				if(visited[nto] == false)
					pq.push(make_pair(-1 * nco, nto));
			}
		}



	}

}


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

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

	prim();
	
	cout << result << endl;

	return 0;
}

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

접근방식

1. 집들을 연결하는 최소값임으로  MST(최소 스패닝 트리) 문제임을 인지

문제풀이 

1. 일반적인 스패닝 트리를 구현

2. 두마을로 분리를 하는 것은 연결된 스패닝 트리 간선중에서 가장 값이 큰 것을 제거해줌으로 구현

3. 저는 우선순위를 사용한 prim 알고리즘으로 구현했습니다.

아래는 정답 코드

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

int n, m, result = 0;
int cut_val = 0;
vector <pair<int, int>> vec[100001];
bool visited[100001] = { 0, };

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

	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;
			
			cut_val = max(cut_val,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(-1 * ncost, npos));
				}
			}


		}

	}

}

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

	prim();
	cout << result - cut_val << endl;


	return 0;
}

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

최단거리를 도출하는 문제입니다. 

접근방식

1. 일반적인 bfs 방식과 다익스트라 방식 2가지를 생각함

3. 수의 범위가 125*125로 비교적 작기 때문에 둘다 가능할 것이라고 생각함

결과적으로 둘다 ok! 다익스트라가 4ms bfs가 8ms

4. 전형적인 방식으로 구현하자!

문제풀이 

1. 우선 bfs로 구현함

일반적인 bfs 방식으로 구현이 가능

2. 다익스트라 방식은 dist배열을 생성하고 가장 작은 cost값들을 pop하면서 진행

3. 코드가 간결하니 코드를 보고 이해하는게 빠를 듯

아래는 bfs 방식 정답 코드

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

int y_ar[4] = { 0,0,-1,1 };
int x_ar[4] = { 1,-1,0,0 };
int n;
int arr[130][130];
int dist[130][130];

void bfs() {

	queue <pair<int, int>> pq;

	pq.push(make_pair(0, 0));
	dist[0][0] = arr[0][0];
    
	while (!pq.empty()) {
		
		int y = pq.front().first;
		int x = pq.front().second;
		pq.pop();

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

			if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
				if ( dist[ny][nx] > dist[y][x] + arr[ny][nx]) {
					dist[ny][nx] = dist[y][x] + arr[ny][nx];
					pq.push(make_pair(ny, nx));
				}
			}
		}
	}

}

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

	int cnt = 1;

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

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
				dist[i][j] = 2000000000;
			}
		
		bfs();
		cout << "Problem " << cnt++ << ": " << dist[n - 1][n - 1] << "\n";
	}

	return 0;
}

아래는 다익스트라 알고리즘 방식

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

typedef struct {
	int y;
	int x;
}p;

int y_ar[4] = { 0,0,-1,1 };
int x_ar[4] = { 1,-1,0,0 };
int n;
int arr[125][125];
int dist[125][125];

void dijkstra() {

	priority_queue <pair<int, pair<int, int>>> pq;
	pq.push(make_pair(-1 * arr[0][0], make_pair(0, 0)));
	dist[0][0] = arr[0][0];

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

		for (int i = 0; i < 4; i++) {
			int ny = y + y_ar[i];
			int nx = x + x_ar[i];
			int ncost = arr[ny][nx];

			if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
				int before_v = dist[ny][nx];
				int current_v = dist[y][x] + ncost;
				if (before_v > current_v) {
					dist[ny][nx] = current_v;
					pq.push(make_pair(-1 * current_v, make_pair(ny, nx)));
				}
			}
		}
	}

}

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

	int cnt = 1;

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

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

		dijkstra();
		cout << "Problem " << cnt++ << ": " << dist[n - 1][n - 1] << "\n";
		
	}


	return 0;
}