이것 저것 &

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

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

우선순위 큐를 사용하는 문제입니다. 

접근방식

1. n이 200,000까지 이기 때문에 일반적인 브루트 포스는 불가

2. 우선순위큐에 데이터를 담고 합치며 진행하는 구조를 생각

3. 우선순위큐 2개를 사용해서 구현 

문제풀이 

1. 입력값을을 min-heap(우선순위 큐)에 삽입

이때, 시작시간이 작은 순으로 배치

2. 시작시간이 작은 순으로 하나씩 heap에서 꺼냄

3. 두번째 min-heap2에 넣을건데,  min-heap2 top에 값의 e와 현재 데이터의 s값을 확인하고,

합칠 수 있으면 합친후 min-heap2에 삽입하는 것을 반복

4. 결과값은 min-heap2의 사이즈

아래는 정답코드입니다. 

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

int n;
priority_queue <pair<int, int>> ique;
priority_queue <pair<int, int>> oque;

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

	cin >> n;
	int a, b;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		ique.push(make_pair(-a, -b));
	}

	for (int i = 0; i < n; i++) {
		int s = ique.top().first * -1;
		int e = ique.top().second * -1;
		ique.pop();
	
		if (oque.empty()) { //처음에 비어 있다면,
			oque.push(make_pair(-e, -s));
			continue;
		}

		int ne = oque.top().first*-1;
		int ns = oque.top().second*-1;

		if (ne <= s) {
			oque.pop();
			oque.push(make_pair(-e, -ns));
		}
		else {
			oque.push(make_pair(-e, -s));
		}



	}

	cout << oque.size() << endl;

	return 0;
}

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

투포인터 알고리즘을 사용한 문제였습니다.

접근방식

1. 일반적인 방식으로 모든값을 비교해준다면 o(N^2)로 시간초과

2. 양쪽에 포인터를 생성하고 필요한 만큼씩만 비교하며 진행하기로 함

문제풀이 

1. 왼쪽부터 오른쪽으로 진행

2. 왼쪽의 절대값이 오른쪽 절대값보다 클경우 더 비교할 필요가 없으니 break

 ex) -10 2 3 5 에서 -10 + 5가 0번 인덱스에선 최선

3.  두값이 같은경우에는 비교할 수 없기 때문에 break

4. 그 외에 right값이 감소해야 하는 경우에는 right--

아래는 정답코드입니다. 예외처리를 할 케이스들이 많은 문제였습니다. 화이팅

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

int n;
int arr[100001] = { 0, };
int index = 0;
int result = 2000000000;
int r1, r2;

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] < 0)
			index++;
	}
	sort(arr, arr + n);
	//cout << index << endl;
	if (index == 0) {
		cout << arr[0]<< ' '<< arr[1] << endl;
		return 0;
	}
	if (index == n) {
		cout << arr[n - 2]<< ' '<< arr[n - 1] << endl;
		return 0;
	}

	
	int right = n - 1;

	for (int i = 0; i < n; i++) { // 모든 수를 검사 
		while (1) {
			if (i < right &&  abs(arr[i] + arr[right]) < result) { // ex) -999 -998 1
				result = abs(arr[i] + arr[right]);
				r1 = arr[i], r2 = arr[right];
			}

			if (abs(arr[i]) > abs(arr[right]))
				break;
			if (right == index)
				break;
			right--;
		}
	}


	cout << r1 << ' ' << r2 << endl;

	return 0;
}

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

비트마스킹문제입니다.

접근방식

1. 입력값이 1,2,4,8의 합으로 들어오기 때문에 비트마스킹을 사용하기로 생각

2. 성에 있는 방의 개수는 bfs를 통해 구현

3. 가장 넓은 방의 넓이도 bfs과정에서 함께 도출

4. 하나의 벽을 제거하는 과정은 반복문을 사용한 브루트포스로 구현

문제풀이 

1. bfs를 통해서 1,2번 결과 도출

   비트마스킹값을 보며 진행! if (visited[ny][nx] == 0 && (((1 << i) & arr[cy][cx]) == 0)) 일때만 탐색!

for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny >= 0 && ny < m && nx >= 0 && nx < n)
				if (visited[ny][nx] == 0 && (((1 << i) & arr[cy][cx]) == 0)) {
					visited[ny][nx] = one;
					two_count++;
					que.push(make_pair(ny, nx));
				}
		}

2. 3번은 모든 점에서 4방향을 다 체크해주며 진행!

n,m둘다 <= 50 이라서 시간 괜찮다.

아래는 정답 코드

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

int arr[51][51] = { 0, };
int visited[51][51] = { 0, };
int two_arr[2600] = { 0, };
int n, m;
int one = 0, two = 0, three = 0;
int y_ar[4] = { 0,-1,0,1 };
int x_ar[4] = { -1,0,1,0 };
int bfs(int y, int x) {
	int two_count = 1;
	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = one;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny >= 0 && ny < m && nx >= 0 && nx < n)
				if (visited[ny][nx] == 0 && (((1 << i) & arr[cy][cx]) == 0)) {
					visited[ny][nx] = one;
					two_count++;
					que.push(make_pair(ny, nx));
				}
		}
	}
	return two_count;

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

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

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++)
			if (visited[i][j] == 0) {
				one++;
				two_arr[one] = bfs(i, j);
				if (two_arr[one] > two)
					two = two_arr[one];
			}
	}


	//3. 
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++) {
			
			for (int k = 0; k < 4; k++) {
				
				if (((1 << k) & arr[i][j]) != 0){
					
					int ny = i + y_ar[k];
					int nx = j + x_ar[k];
					if (ny >= 0 && ny < m && nx >= 0 && nx < n) {
						
						if(visited[i][j] != visited[ny][nx])
							three = max(three, two_arr[visited[i][j]] + two_arr[visited[ny][nx]]);
						
					}
					
				}
			}
			
		}
	
	cout << one << endl;
	cout << two << endl;
	cout << three << endl;
	return 0;
}