이것 저것 &

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

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