이것 저것 &

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

MST문제 

접근방식

1. 모든 노드를 잇는 최소비용을 출력하는 것이기 때문에 MST문제임을 인식

2. 우선순위 큐를 사용한 프림알고리즘을 사용하기로 함

문제풀이 

1. 일반적인 프림알고리즘과 거의 동일한 구조

2. 조심해야할 점은 결과값이 소수형태이기 때문에 그 부분에 유의하면서 자료형을 선택해야한다. 

3. dis에 거리를 다 넣어놓고 탐색하는 구조

코드를 보면 더 이해가 빠를 듯

정답 코드

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

int n, m;
bool visited[1001] = { 0, };
int arr[1001][2] = { 0, };	
double dis[1001][1001] = { 0, };
double result = 0;
vector<pair<int, int>> vec;


void prim() {

	priority_queue <pair<double, int>> que; // 비용이랑 몇번째 좌표인지 표기
	for (int i = 2; i <= n; i++) { // 1과 연결된 값을 저장 
		que.push(make_pair(dis[1][i] * -1, i));
	}
	visited[1] = 1;

	while (!que.empty()) {
		double cost = que.top().first * -1;
		int cur = que.top().second;
		que.pop();

		if (visited[cur] == 0) {
			visited[cur] = 1;
			result += cost;

			for (int i = 1; i <= n; i++) {
				if (i != cur && visited[i] == 0) {
					que.push(make_pair(dis[cur][i] * -1, i));
				}
			}
		}


	}

}

int main() {

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

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			dis[i][j] = sqrt(pow(abs(arr[i][0] - arr[j][0]), 2) + pow(abs(arr[i][1] - arr[j][1]), 2));
			dis[j][i] = dis[i][j];
		}
	//cout << dis[1][2] << endl;

	int t1, t2;
	for (int i = 0; i < m; i++) {
		cin >> t1 >> t2;
		dis[t1][t2] = 0, dis[t2][t1] = 0;
	}

	prim();
	printf("%.2f\n", result);
}

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

다익스트라 + 구현 문제 

접근방식

1. 최단 거리 탐색에서 다익스트라로 구현하면 되겠다 생각

2. 아래 문제와 비슷한 방식

https://gusdnr69.tistory.com/239?category=799066 

결국 s -> g -> h -> 목표 지점 또는 s -> h -> g -> 목표 지점으로 이동할 때의 최소값이 

s -> 목표지점으로 도달하는 값이 똑같은지 비교하는 문제 

3. 다익스트라를 3번 호출해서 구현하자 

문제풀이 

1. 다익스트라는 일반적인 형태와 똑같이 구현. 다만 매개변수에 배열을 넣어서 해당 배열을 채워 주는 구조로 

2. dist배열을 s에서 시작할 때, g에서 시작할 때, h에서 시작할 때 총 3개를 만들고 다익스트라 함수도 총 3번 호출

3.  min( s-g-h-목표 지점, s-h-g-목표지점)이  s-목표지점과 같은지 확인  

정답 코드

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

int T, n, m, t, s, g, h;
int a, b, d, temp;

vector <int> destin; //목적지 위치, 시작점에서 다이렉트로 도달할 때 거리를 저장할거
int dist_s[2001];
int dist_g[2001];
int dist_h[2001];
vector <pair<int,int>> arr[2001];

void dijkstra(int start, int dist[2001]) {
	priority_queue <pair<int,int>> que;
	que.push(make_pair(0, start));
	dist[start] = 0;

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


		for (int i = 0; i < arr[cur].size(); i++) {
			int before_v = dist[arr[cur][i].first];
			int current_v = cost + arr[cur][i].second;
			if (before_v > current_v) {
				dist[arr[cur][i].first] = current_v;
				que.push(make_pair(current_v*-1, arr[cur][i].first));
			}
		}

	}



}



int main() {
	

	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d", &n, &m, &t);
		scanf("%d %d %d", &s, &g, &h);
		
		
		//초기화 
		destin.clear();
		for (int i = 1; i <= 2000; i++) {
			arr[i].clear();
			dist_s[i] = 2000000000;
			dist_g[i] = 2000000000;
			dist_h[i] = 2000000000;
		}
		
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &a, &b, &d);
			arr[a].push_back(make_pair(b, d));
			arr[b].push_back(make_pair(a, d));
		}

		for (int i = 0; i < t; i++) {
			scanf("%d", &temp);
			destin.push_back(temp);
		}

		sort(destin.begin(), destin.end()); // 오름차순으로 미리 정렬해둠	

		dijkstra(s, dist_s);
		dijkstra(g, dist_g);
		dijkstra(h, dist_h);

		

		for (int i = 0; i < destin.size(); i++) {

			if (dist_s[destin[i]] == (dist_s[g] + dist_g[h] + dist_h[destin[i]]))
				cout << destin[i] << ' ';
			else if(dist_s[destin[i]] == (dist_s[h] + dist_h[g] + dist_g[destin[i]]))
				cout << destin[i] << ' ';
		}
		cout << endl;


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

	}

	return 0;
}

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

bfs문제입니다.

접근방식

1. 일반적인 공식이나 규칙을 통해서 풀 수 있는 문제가 아님

132 3

이라는 입력값일때, 결과는 321이 아닌 312

312 -> 321 -> 312 이기 때문에

즉, 특정 규칙을 통해서가 아닌 모든 경우를 판단해서 최대값을 도출하는 방향으로 접근함

2. bfs를 통해서 매번 k번만큼 모든경우를 판단해줌 

visited는 k번마다 초기화를 시켜주어야함.

왜냐하면 앞선 예시에서 312라는 값이 앞에서 사용되어졌는데, 결과값이기도 함 

즉, 매번 방문여부를 초기화하며 진행해주어야함 

문제풀이 

1. 우선 -1인 경우를 생각해봄

• 한자리 수일때: 스왑할 수가 없으니 불가
• 두자리 수이고 일의 자리수가 0일때: 스압하게 되면 0이 앞으로 나옴으로 조건에 부합하지 않음 ex) 10, 20, 50

2. BFS를 통해서 구현함

이때, K번만큼 반복하도록 구획을 나눠주면서 진행해야함. 이유는 접근방식 2번 참고

3. BFS에서 문자열에서 한 문자씩 바꿔보면서 visited집합에 값이 있는지 없는지 판단하며 진행

정답 코드

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

string arr;
int k;
int maxed = 0;
bool jud() {
	int cnt = 0;
	for (int i = 0; i < arr.size(); i++)
		if (arr[i] > '0')
			cnt++;
	if (cnt > 1)
		return true;
	return false;
}

void bfs() {
	queue <string> que;
	que.push(arr);

	for (int u = 0; u < k; u++) { // k번 반복 
		int sized = que.size();
		set <string> visitied;

		for (int s = 0; s < sized; s++) {
			string temp = que.front();
			que.pop();

			for (int i = 0; i < temp.size() - 1; i++) {
				for (int j = i + 1; j < temp.size(); j++) {
					if (i == 0 && temp[j] == '0') continue;

					swap(temp[i], temp[j]); // #include algo
					if (visitied.find(temp) == visitied.end()) {
						if (u == k - 1) { //마지막 턴
							int val = stoi(temp);
							maxed = max(maxed, val);
						}
						que.push(temp);
						visitied.insert(temp);
					}
					swap(temp[i], temp[j]);
				}
			}


		}



	}


}

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

	cin >> arr >> k;
	if (arr.size() == 1) { // 한자리 수
		cout << -1 << endl;
		return 0;
	}
	else if (arr.size() == 2 && jud() == false) { // 두자리 수이지만 수가 하나라 swap을 못할 때
		cout << -1 << endl;
		return 0;
	}

	bfs();

	cout << maxed << endl;

	return 0;
}

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

dp문제입니다.

접근방식

1. 당연히 일반적인 방법으로 매번 검사하는건 불가능하다. 

O(n x m) => 2000 X  1,000,000 으로 가뿐히 10초를 넘기기 때문에

2. dp방식을 통해서 이미 검사해준 값이라면 또 탐색하지 말고 바로 값을 얻어오자

문제풀이 

1. top-down방식으로 dp[시작점][끝점]마다 가능한지 불가능한지 체크해주면서 넘어가자

2. 양 옆으로 한칸씩 줄이면서 탐색하는 구조 자세한 설명은 코드로

정답 코드

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

int n = 0, m = 0, st = 0, en = 0;
int arr[2000] = { 0, };
int dp[2000][2000];

int solved(int s, int e) {
	if (s >= e) return 1;
	if ((s + 1) == e) {
		if (arr[s] == arr[e])
			return 1;
		else
			return 0;
	}

	int& ret = dp[s][e];
	if (ret != -1) return ret;

	if (arr[s] == arr[e])
		ret = solved(s + 1, e - 1);
	else
		ret = 0;

	return ret;
}

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

	scanf("%d", &n);
	for (int i = 0; i < n; i++) 
		scanf("%d", &arr[i]);
	
	for (int i = 0; i < 2000; i++)
		for(int j=0; j < 2000; j++)
			dp[i][j] = -1;

	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &st,&en);
		printf("%d\n", solved(st - 1, en - 1));
	}


	return 0;
}

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

bfs문제입니다.

접근방식

1. 결국 몇번 꺾여서 목표에 도달할 수 있는지 묻는 문제

2. bfs를 통해서 구현하기로 결정. 일반적인 형태라는 다르게 큐를 구현해야함

문제풀이 

1. 큐에는 현재 좌표, 거울의 개수, 도달한 방향순으로 저장

2. 만약 거울의 갯수가 같거나 작다면 큐에 넣어주면서 거울 갯수를 탐색

이때, visited함수에 최소 거울의 갯수를 저장

정답 코드

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

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
char arr[100][100];

vector <pair<int, int>> laser;
int visited[100][100] = { 0, };
int w, h;

int val, temp;

void bfs() {

	queue <pair<pair<int, int>, pair<int, int>>> que; //좌표, 거울 갯수, 방향순으로 넣을거
	que.push(make_pair(make_pair(laser[0].first, laser[0].second), make_pair(0, -1)));

	while (!que.empty()) {
		int y = que.front().first.first;
		int x = que.front().first.second;
		int mirror = que.front().second.first;
		int dir = que.front().second.second;
		que.pop();
		int temp;
		for (int i = 0; i < 4; i++) {
			int ny = y + y_ar[i];
			int nx = x + x_ar[i];
			if (ny < 0 || ny >= h || nx < 0 || nx >= w || arr[ny][nx] == '*' )
				continue;
			temp = mirror;
			if (dir != i)
				temp++;
			if (visited[ny][nx] >= temp) {
				visited[ny][nx] = temp;
				que.push(make_pair(make_pair(ny, nx), make_pair(temp, i)));
			}



		}

		
	}



}

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

	
	cin >> w >> h;
	for (int i = 0; i < h; i++) {
		cin >> arr[i];
		for (int j = 0; j < w; j++) {
			if (arr[i][j] == 'C')
				arr[i][j] = '.', laser.push_back(make_pair(i, j));
			visited[i][j] = 1000000000;
			
		}
	}

	bfs();
	/*
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cout << visited[i][j] << ' ';
		}
		cout << endl;
	}
	*/

	cout << visited[laser[1].first][laser[1].second] - 1 << endl;

	return 0;
}

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

dp문제입니다.

접근방식

1. 모든 경우의 수를 고려하는 브루트 포스방식은 불가

2. 배낭 알고리즘처럼 n = 1 일때 부터 하나씩 경우의 수를 추가해주는 방식으로 구현 

3. 경우의 수에 대한 갯수가 아니라 단순히 가능, 불가능 여부이기 때문에 직관적으로 구현

문제풀이 

1. n개만큼 반복하며 i개까지 가지고 있을 때 분배가 가능한지 탐색

j를 top-down방식으로 사용하는 이유는 if문에서 이전 인덱스의 dp값을 참조하며 진행하기 때문이다. 

정답 코드

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

int dp[50001] = { 0, }, n = 0;
int won, cnt;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int t = 3;
	
	while (t--) {
		int sum = 0;
		vector <pair<int, int>> vec;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> won >> cnt;
			vec.push_back(make_pair(won, cnt));
			sum += won * cnt;
		}
		if (sum % 2 == 1) {
			cout << 0 << endl;
			continue;
		}
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		for(int i=0;i<n;i++)
			for (int j = 50000; j >= vec[i].first; j--) {
				if (dp[j - vec[i].first] == 1) {
					for (int k = 0; k < vec[i].second && (j + k*vec[i].first) <= 50000; k++) {
						dp[j + k*vec[i].first] = 1;
					}
				}
			}

		if (dp[sum / 2] == 1) {
			cout << 1 << endl;
		}
		else
			cout << 0 << endl;

	}


	return 0;
}

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

수학적인 개념을 파악하는게 어려웠던 문제... 

접근방식

1. 당연히 일반적인 dp로는 불가능

2. 찾아보니 피사노 주기라는 것이 존재했다. 간단하게 말하면 피보나치수를 n으로 나눈 나머지로 처리할때 m이라는 주기가 생긴다는 것이다. 자세한 설명은 아래 문제를 참고

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

3. 피사노 주기를 구하고 해당 값까지 단순 피보나치를 구현하여 문제를 해결

문제풀이 

1. 피사노 주기 함수를 구현. 단순하게 계속 반복하며 원소값이 0, 1일때를 찾는다. 

2. 피사노 주기만큼 n을 나눈 나머지값 만큼만 탐색해주며 결과를 도출.

정답코드입니다.

#include <iostream>
using namespace std;
//1000000로 나눈 값은 1500000개 만큼의 단위로 반복한다.  feat 피사노 주기 
long long n;

long long get_pisano(long long num) {

	int a = 0, b = 1, result = 0;
	
	for (long long cnt = 1;; cnt++) {
		result = a + b;
		result %= num;
		a = b, b = result;

		if (a == 0 && b == 1) {
			return cnt;
		}	
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	long long temp = get_pisano(1000000);
	n %= temp;

	int a = 0;
	int b = 1;
	int result = 0;

	if (n == 0)
		cout << 0 << endl;
	else if (n == 1)
		cout << a + b << endl;
	else{
		for (int i = 2; i <= n; i++) {
			result = a + b;
			result %= 1000000;
			a = b, b = result;
		}

		cout << result << endl;
	}

	return 0;
}

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

접근방식

1. B가 100,000,000,000 이므로 매번 곱해주는 형식으로는 무조건 시간초과

2. 행렬을 1번 곱하고 그값들로 또 1번 곱하게 되면 기존 행렬을 4번 곱한 것과 같은 형태이다.

즉 행렬곱셉은 제곱연산이 가능한 형태!! 

그러면 dp나 분할정복을 통해서 제곱으로 계산해주는 형태를 생각하게 됨.

3. 제곱값들을 한번씩만 사용해주면 되기 때문에 분할정복을 선택함 

문제풀이 

1. 아래처럼 분할정복 호출을 구현하는데, 직관적인 코드이다.

ex) b 가 10일 때, (행x행) 하나 생성하고 b는 5로

     b 가 5일 때, (행x행) 을 결과값으로 넣고 그리고 (행x행)X(행x행) 을 생성

     b 가 2일 때,  ((행x행)X(행x행)) X ((행x행)X(행x행)) 생성

     b 가 1일 때,  (행x행) 인 결과값에 ((행x행)X(행x행)) X ((행x행)X(행x행)) 를 곱해줌으로써 (행x행) X ((행x행)X(행x행)) X ((행x행)X(행x행)) 으로 10번 행이 곱해지게끔 만들어주는 방식이다. 

이러한 식 도출은 딱히 방식이 있다기 보다는 문제를 많이 풀어보면서 노하우를 습득하는 방법밖에 없는 것 같다.... 

while (b) {
		if (b % 2 == 1) {
			solved(result, arr);
		}
		solved(arr, arr);
		b /= 2;

	}

2. 행렬 곱셈은 원래 아는 방식 그대로 구현

다만, result 초기값을 단위행렬로 구성하는 것을 주의 

정답코드입니다.

#include <iostream>
using namespace std;

long long n, b;
int arr[5][5];
int result[5][5];
int temp[5][5];

void solved(int v1[5][5], int v2[5][5]) {
	

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			temp[i][j] = 0;
			for (int k = 0; k < n; k++)
				temp[i][j] += (v1[i][k] * v2[k][j]);
			temp[i][j] %= 1000;
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) 
			v1[i][j] = temp[i][j];
		
			
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> b;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
		result[i][i] = 1;
	}
	while (b) {
		if (b % 2 == 1) {
			solved(result, arr);
		}
		solved(arr, arr);
		b /= 2;

	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++)
			cout << result[i][j] << ' ';
		cout << endl;
	}

	return 0;
}