하용권

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

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

int main(){
	int n, m;
	int arr[500000];
	int ans[500000] = {0};
	
	cin >> n;
	for(int i = 0 ; i < n; i++) scanf("%d", &arr[i]);
	sort(arr,arr+n);
	
	cin >> m;
	for(int i = 0; i < m; i++)scanf("%d", &ans[i]);
	

	
	for(int i = 0;  i < m; i++){
		bool chk = 0;
		int l_tmp = -1,r_tmp = n;
		int left = -1, right = n;

		while(left + 1 < right){
			int mid = (left+right)/2;
			
			if(arr[mid] > ans[i]) right = mid;
			else if(arr[mid] < ans[i])  left = mid;
			if(arr[mid] == ans[i]){
				l_tmp = mid;
				right = mid;
				left = -1;
				chk =true;
			}
		}
		
		left = -1, right = n;
		while(left + 1 < right){
			int mid = (left+right)/2;
			
			if(arr[mid] > ans[i]) right = mid;
			else if(arr[mid] < ans[i])  left = mid;
			if(arr[mid] == ans[i]){
				r_tmp = mid;
				left = mid;
				right = n;
				chk=true;
			}
		}
		if(chk)printf("%d ", r_tmp-l_tmp+1);
		else   printf("0 ");
	}
}

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

소수는 에라토스테네스의 채를 이용해서 구했습니다.

처음에 풀 때는 queue에 넣을 값을 찾기 위해 1000부터 9999까지 모두 뒤졌습니다. 당연하게도  시간초과가 뜨더군요.

그래서 1,10,100,1000 자리의 숫자만 변경하는 것으로 하니 잘 되네요.

#include <iostream>
#include <queue>
#include <cmath>
#include <string>
using namespace std;
bool num[10000] = { 0 };

void num_set() {

	for (int i = 2; i <= sqrt(9999); i++) {
		if (!num[i]) {
			for (int j = i + i; j <= 9999; j += i)
				num[j] = true;
		}
	}

}


int main() {
	ios_base::sync_with_stdio(false);
	num_set();
	int t;
	cin >> t;

	while (t--) {
		string x, y;
		int cnt = -1;
		bool chk = false;
		queue<string> q;
		bool visited[10000] = { 0 };

		cin >> x >> y;
		q.push(x); visited[atoi(x.c_str())] = true;

		while (!q.empty()) {
			cnt++;
			int size = q.size();
			
			for (int i = 0; i < size; i++) {
				string tmp = q.front(); q.pop();

				if (tmp == y) {
					chk = true; break;
				}

				for (int j = 0; j < 4; j++) {
					for (int k = 0; k <= 9; k++) {
						string dtmp = tmp;
						dtmp[j] = k + 48;
						if (visited[atoi(dtmp.c_str())]) continue;
						if (num[atoi(dtmp.c_str())]) continue;
						if (atoi(dtmp.c_str()) < 1000) continue;
						q.push(dtmp);
						visited[atoi(dtmp.c_str())] = true;
					}
				}

			}
			if (chk) break;
		}

		if (chk) cout << cnt << endl;
		else    cout << "Impossible" << endl;
	}

}

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

모든 정점을 돌아다니면서 bfs를 수행하면서, 시간을 증가시킵니다. 그리고 ret 변수를 최대 시간으로 계속 갱신합니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
	char map[51][51];
	int dx[4] = {0,0,1,-1};
	int dy[4] = {1,-1,0,0};
	int ret = 0;
	int l,w;
	
	cin >> l >> w;
	
	for(int i = 0; i  < l; i++){
		cin >> map[i];
	}
	
	for(int i = 0; i < l; i++){
		for(int j = 0; j < w; j++){
			if(map[i][j] == 'L'){
				int cnt = 0;
				int chk = false;
				queue<pair<int,int> > q;
				bool visited[50][50] = {0};
				q.push({i,j}); visited[i][j] =true;
				
				while(!q.empty()){
					if(chk){
						cnt+=1;
						ret = max(ret, cnt);
					}
					int size = q.size();
					for(int h = 0; h < size; h++){
						int x = q.front().second, y = q.front().first;
						q.pop();
						for(int k = 0; k < 4; k++){
							int xx = x+dx[k], yy = y + dy[k];
							
							if(xx < 0 || yy < 0 || xx >= w || yy >= l) continue;
							if(visited[yy][xx] || map[yy][xx] == 'W') continue;
							visited[yy][xx] = true;
							q.push({yy,xx});
						}
					}
					chk = true;
				}
				
				
			}
		}
	}
	cout << ret;
}

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

#include <iostream>
#include <vector>
using namespace std;
vector<int> v[100];
int ret[100][100] = {0};
int n;

void dfs(int start, int y){
	
	for(int i = 0; i < v[start].size(); i++){
		int tmp = v[start][i];
		if(ret[y][tmp]) continue;
		ret[y][tmp] = 1;
		dfs(tmp,y);
	}
}

int main(){
	int tmp;
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> tmp;
			if(tmp == 1)
				v[i].push_back(j);
		}	
	}
	
	
	for(int i = 0; i < n; i++){
		dfs(i,i);
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++)
			cout << ret[i][j] << ' ';
		cout << endl;
	}
}	

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

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

int main(){
	vector<int> arr[101];
	bool chk[101][101] = {0};
	int sum[101] = {0};
	int idx = 1;
	int n,m,t1,t2;
	
	cin >> n >> m;
	
	for(int i = 1; i <= m; i++){
		cin >> t1 >> t2;
		arr[t1].push_back(t2);
		arr[t2].push_back(t1);
	}
	
	for(int i = 1; i <= n; i++){
		queue<int> q;
		int cnt = 0;
		q.push(i);
		chk[i][i] = 1;
		
		while(!q.empty()){
			int q_size = q.size();
			cnt +=1;

			for(int k = 0; k < q_size; k++){
				int tmp = q.front(); q.pop();
				
				for(int j = 0; j < arr[tmp].size(); j++){
					if(chk[i][arr[tmp][j]]) continue;
					
					chk[i][arr[tmp][j]] = true;
					sum[i] += cnt;
					q.push(arr[tmp][j]);
				}
			}
		}
		
		if(sum[idx] > sum[i])
			idx = i;
	}
	
	cout << idx;

}

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

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

간단한 dfs문제입니다.

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

bfs

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

저에게 익숙한 bfs로 짠 코드 입니다.