이것 저것 &

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

굳이 따지면 브루트포스보다도 비트마스킹이 핵심인 문제!

접근방식

1. 일반적인 방식이라면, 알파벳 배열을 하나 만들고 입력되는 알파벳을 지원주거나 다시 채워주며 진행

2. 그리고 문자별로 string size만큼 반복하며 가능한지 확인하는 방식

3. 근데 이렇게 해결하면 시간복잡도가 O(10^4 * 10^4 * 10^3) 로 무조건 시간초과

4. 비트마스킹을 통해서 문자들을 한번에 확인하는 O(10^4 * 10^4)  방식으로 문제를 해결 

문제풀이 

1.  int remember에 비트에 알파벳(0~25)값들을 마킹한다.

ex) 'a'는 0000 0001 이렇게 마킹한거고, 'b'는 0000 0010 여기에 마킹한거!

for (int i = 0; i < 26; i++)
		remember |= (1 << i);

2.  각 문자 단어들을 1번과 같은 방식으로 포함된 알파벳을 마킹한다.

for (int j = 0; j < temp.size(); j++) 
			arr[i] |= (1 << (temp[j] - 'a'));

3. m번 반복하며, 명령어 별로 단어가 몇개 가능한지 확인

이때 아래구문을 호출하는데, 만약 비트 마킹이 1로 되어 있었으면 0으로 바뀌고 0이면 다시 1로 변환되게끔 움직인다.

remember ^= (1 << (b - 'a'));

&는 and 연산자라서 둘다 1이어야 1이 됨!

if ( (arr[i] & remember) == arr[i])
				result++;

아래는 전체 코드입니다.

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

int arr[10000] = { 0, };
int n = 0, m = 0;
int remember = 0;

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

	cin >> n >> m;
	
	for (int i = 0; i < 26; i++)
		remember |= (1 << i);

	string temp;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		for (int j = 0; j < temp.size(); j++) 
			arr[i] |= (1 << (temp[j] - 'a'));
		
	}

	int a;
	char b;
	while (m--) {
		int result = 0;
		cin >> a >> b;

		remember ^= (1 << (b - 'a'));

		for (int i = 0; i < n; i++)
			if ( (arr[i] & remember) == arr[i])
				result++;
		cout << result << "\n";

	}

	return 0;
}

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

접근방식

1.  정렬을 하고, 문제를 해결해야함을 인지

2.  정렬을 하고 최선의 선택을 하며 결과를 도출하는 그리디임을 인지 

3.  양수, 음수별로 진행 -> m개씩 전달하는 값을 도출 -> 가장 먼 값은 왕복이 아님

문제풀이 

1. 2. 예시에서는 -37 2 -6 -39 -29 11 -28 -> -39 -37 -29 -28 -6 2 11

3.  {-39} {-37 -29} {-28 -6} {2 11} 이렇게 4번 진행하되 -39를 마지막에 도달하면 131이 나옴

4. 즉,  음수 양수 따로 진행하며,  m개씩 선택하고 왕복값을 저장해준다. 그리고 가장 극단 값에 있는 값을 빼줌 (왕복x)

그리디 알고리즘 문제였습니다.

아래는 정답코드입니다.

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

int n, m;
int arr[10001] = { 0, };
int pindex = 0;
int result = 0;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (arr[i] < 0)
			pindex++;
	}

	sort(arr, arr + n);
	
	for (int i = n - 1; i >= pindex; i -= m) {
			result += (arr[i]*2);
	}

	for (int i = 0; i < pindex; i += m) {
			result += abs(arr[i] * 2);
	}

	result -= max(abs(arr[0]), abs(arr[n - 1]));

	cout << result << endl;
	return 0;
}

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

접근방식

1. 모든 경우를 판단해주어야 하는 것을 인지

2. 근데 n이 10000으로 크기 때문에 일반적인 bfs, dfs가 불가능함을 인지

3. 그러면 방문했던 값을 저장하는 dp(메모이제이션) 방식이 가능한가 확인

4. 10,000*10,000 = 100,000,000 X 4Byte = 대략 400Mb... 즉, dp방식도 불가능

5. 이분탐색을 통해서 방문하는 범위를 줄여볼까? 생각하게 됨

문제풀이 

1. 결과값은 다리의 비용중에 하나이다.2. 최소 비용(0), 최대비용(다리 비용중 최대값)을 low, high값으로 지정하고 mid값일때, 이동가능한지 확인3. 간단한 bfs를 통해서 이동이 가능한지 확인 4. 이동이 불가하면 high값을 낮춰주고, 이동이 가능하면 low값을 올려주며 진행

이분탐색 + bfs로 해결하는 문제입니다. 아래는 정답코드입니다.

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

int n, m;
int a, b, c;
vector <pair<int, int>> vec[10001];
bool visited[10001];
int s, e;
int bfs(int cost) {
	queue <int> que;
	que.push(s);
	visited[s] = 1;

	while (!que.empty()) {

		int cur = que.front();
		que.pop();
		if (cur == e)
			return true;
		for (int i = 0; i < vec[cur].size(); i++) {
			int ncur = vec[cur][i].first;
			int ncos = vec[cur][i].second;

			if (!visited[ncur] && ncos >= cost) {
				visited[ncur] = 1;
				que.push(ncur);

			}

		}



	}

	return false;

}

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

	cin >> n >> m;
	int from, to, cost;
	int maxcost = 0;
	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));
		if (cost > maxcost)
			maxcost = cost;
	}
	
	cin >> s >> e;
	
	int low = 0, high = maxcost;
	while (low <= high) {
		
		memset(visited, 0, sizeof(visited));
		int mid = (low + high)/2;

		if (bfs(mid)) {
			low = mid  + 1;
		}
		else {
			high = mid  - 1;
		}
		
	}
	cout << high << endl;

	return 0;
}

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

다익스트라 문제입니다.

차이점은 v1과 v2를 들렸다가 n으로 도달해야한다는 점입니다.

그렇다면, 경우는 2가지 입니다.

1->v1->v2->n

1->v2->v1->n

각각의 경우에 맞춰서 다익스트라 함수를 사용해주면 됩니다.

주의할 점은 v1,v2,n 모두 도달이 가능해야 한다는 점입니다. 

아래는 정답 코드입니다.

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define INF 2000000000

int n, e, v1, v2;
vector <pair<int, int>> vec[801];
int dist[801];

int dijkstra(int sn, int en) {
	priority_queue <pair<int, int>> pq;
	pq.push(make_pair(0, sn));

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

		for (int i = 0; i < vec[node].size(); i++) {
			int current_val = dist[node] + vec[node][i].second;
			int before_val = dist[vec[node][i].first];

			if (current_val < before_val) {
				dist[vec[node][i].first] = current_val;
				pq.push(make_pair(current_val*-1, vec[node][i].first));
			}

		}
	}

	return dist[en];

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

	cin >> n >> e;
	for (int i = 1; i <= e; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
		vec[to].push_back(make_pair(from, cost));
	}
	cin >> v1 >> v2;

	for (int i = 1; i <= n; i++)
		dist[i] = INF; 
	dist[1] = 0;
	dijkstra(1, n);

	if (dist[v1] == INF || dist[v2] == INF || dist[n] == INF) {
		cout << -1 << endl;
		return 0;
	}


	long long result1 = 0;
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[1] = 0;
	result1 += dijkstra(1,v1);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v1] = 0;
	result1 += dijkstra(v1, v2);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v2] = 0;
	result1 += dijkstra(v2, n);

	long long result2 = 0;
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[1] = 0;
	result2 += dijkstra(1, v2);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v2] = 0;
	result2 += dijkstra(v2, v1);
	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[v1] = 0;
	result2 += dijkstra(v1, n);


	cout << min(result1, result2) << endl;
	return 0;
}

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

리프노드의 갯수를 구하는 문제입니다.

dfs 탐색을 통해서 제거된 노드의 자식노드들도 함께 제거를 하면 진행해주었습니다.

만약, 자식 노드를 가지고 있지 않다면 leaf 노드로 간주했습니다.

이때, 주의할 점은 제거된 노드의 부모노드가 leaf 노드가 될 수 있다는 점입니다.

아래는 정답 코드입니다.

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

vector <int> vec[50];
int n = 0, root;

void dfs(int n) {

	if (vec[n].size() == 0) {
		vec[n].push_back(-2);
		return;
	}
	for (int i = 0; i < vec[n].size(); i++) {
		dfs(vec[n][i]);
	}

}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		if (temp == -1) 
			root = i;
		else
			vec[temp].push_back(i);
	}
	int m;
	cin >> m;

	dfs(m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < vec[i].size(); j++) {
			if (vec[i][j] == m)
				vec[i].erase(vec[i].begin() + j);
		}
	}
	int result = 0;
	for (int i = 0; i < n; i++)
		if (vec[i].size() == 0)
			result++;
	cout << result << endl;

	return 0;
}

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

서브트리들의 정점 갯수를 구하는 문제

부모 노드의 경우 탐색을 해주면 안되는데,

이러한 문제를 메모이제이션을 통해서 문제를 해결할 수 있습니다.

아래는 정답 코드입니다.

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

vector <int> vec[100001];
int n, r, q;
int dp[100001];

int dfs(int n) {
	if (dp[n] != -1)
		return dp[n];
	
	int& ret = dp[n];	
	ret = 1;
	for (int i = 0; i < vec[n].size(); i++) {
		int next = vec[n][i];
		if (dp[next]!= -1)
			continue;
		ret += dfs(next);
	}
	
	return ret;
}

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

	cin >> n >> r >> q;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
		dp[i] = -1;
	dp[r] = dfs(r);
	for (int i = 0; i < q; i++) {
		int c;
		cin >> c;
		cout << dp[c] << "\n";
	}


	return 0;
}

문제링크: www.acmicpc.net/problem/17822

개인적으로 많이 예외를 못찾아서 고민한 문제....

이런 문제일수록 구현을 간단하게 설계해야 한다.

구현해야할 것은 크게 

• 0. 입력
• 1. 원판 돌리기
• 2. 인접한 수 탐색
• 2-1. 인접한 수 지우기
• 2-2.  평균값에서 감산, 가감하기
• 3. 결과 도출

깨알팁 tip)

1. 원판 돌리기 같은경우에 시계 반대 방향은 m - k 번 시계방향으로 돌리는 것과 같다.

2. 인접한 수를 탐색하는 bfs 구현시 배열을 통해서 구현 범위를 줄일 수 있다.

아래는 정답 코드입니다.

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

int n, m, t;
int arr[51][51] = { 0, };
int result = 0;
int temp[51] = { 0, };
int visited[51][51];

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

//2. search
bool bfs(int y, int x) {

	memset(visited, 0, sizeof(visited));

	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1;

	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 == n) continue;

			if (nx == m) nx = 0;
			else if (nx == -1) nx = m - 1;

			if (visited[ny][nx] == 0 && arr[ny][nx] == arr[cy][cx]) {
				que.push(make_pair(ny, nx));
				visited[ny][nx] = visited[cy][cx] + 1;
			}

		}
	}

	//erase
	bool jud = false;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (visited[i][j] > 1)
				jud = true;
	if (jud == true) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				if (visited[i][j] != 0)
					arr[i][j] = 0;
	}
	return jud;
}

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

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

	while (t--) {
		int x, d, k;
		cin >> x >> d >> k;
		if (d == 1)
			k = m - k;
		//1. 회전
		for (int i = x - 1; i < n; i += x) {
			
			for (int l = 0; l < k; l++) {
				for (int j = 0; j < m; j++)
					temp[j] = arr[i][j];

				for (int j = 1; j < m; j++)
					arr[i][j] = temp[j - 1];
				arr[i][0] = temp[m - 1];
			}
		}



		
		bool jud = false;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				if (visited[i][j] == 0 && arr[i][j] != 0) {
					
					bool temp = bfs(i, j);
					if (temp == true)
						jud = true;
				}
			}

		//평균값 구해서 +1, -1  해주기
		if (jud == false) { 
			double sum = 0;
			double cnt = 0;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < m; j++)
					if (arr[i][j] != 0 ) {
						sum += arr[i][j];
						cnt += 1;
					}
			if (cnt > 0) {
				sum = sum / cnt;
				for (int i = 0; i < n; i++)
					for (int j = 0; j < m; j++)
						if (arr[i][j] != 0) {
							if (sum > arr[i][j])
								arr[i][j] ++;
							else if (sum < arr[i][j])
								arr[i][j] --;
						}
			}
		}


	}


	//result
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			result += arr[i][j];
	cout << result << endl;

	
}

문제풀이: www.acmicpc.net/problem/19238

구현 순서는 

• 0. 입력값 받기
• 1. bfs로 이동거리 재기
• 2. 가장 가까운 사람에게 이동
• 3. 목적지까지 거리 도출
• 4. 목적지로 이동

주의할 점은

• 1. 이동과 동시에 도착할때, 즉 택시위치와 사람위치가 같은 경우에는 거리가 0이다.
• 2. 벽으로 막혀있어 택시가 목적지나 사람에게 도달하지 못해도 결과값은 -1이다.
• 3. 목적지에 도착하면서 연료가 바닥나는 것은 괜찮다.

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

typedef struct a {
	int y;
	int x;
}pos;

int n, m, f;
int arr[21][21] = { 0, };
int visited[21][21];
pos taxi;
vector <pos> people;
vector <pos> destination;

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

void bfs(int y, int x) {
	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1; // -1 해야함 

	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 >= 1 && ny <= n && nx >= 1 && nx <= n) {
				if (arr[ny][nx] == 0 && visited[ny][nx] == 0) {
					que.push(make_pair(ny, nx));
					visited[ny][nx] = visited[cy][cx] + 1;
				}
			}
		}
	}
}

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

	cin >> n >> m >> f;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> arr[i][j];
	cin >> taxi.y >> taxi.x;
	for (int i = 0; i < m; i++) {
		int t1, t2, t3, t4;
		cin >> t1 >> t2 >> t3 >> t4;
		people.push_back({ t1,t2 });
		destination.push_back({ t3,t4 });
	}

	for (int k = 0; k < m; k++) {
		//1. 이동 거리 측정
		memset(visited, 0, sizeof(visited));
		bfs(taxi.y, taxi.x);
		/*
		for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
		cout << visited[i][j] << ' ';
		cout << endl;
		}*/

		//2. 가장 가까운 사람 선택
		int dis = 1000000000;
		int ny = 0, nx = 0, index = -1;
		for (int i = 0; i < people.size(); i++) {
			int y = people[i].y;
			int x = people[i].x;
			if (visited[y][x] < dis) {
				ny = y;
				nx = x;
				index = i;
				dis = visited[y][x];
			}
			else if (visited[y][x] == dis) {
				if (ny > y) {
					ny = y;
					nx = x;
					index = i;
				}
				else if (nx > x && ny == y) {
					ny = y;
					nx = x;
					index = i;
				}
			}
		}
		people.erase(people.begin() + index);
		taxi.y = ny, taxi.x = nx;
		f -= (visited[ny][nx] - 1);
		if (visited[ny][nx] == 0) {
			f = -1;
			break;
		}
		if (f <= 0)
			break;
		//cout << "y " << ny << "x " << nx << "i " << index << endl;

		//3. 목적지까지 거리 도출
		memset(visited, 0, sizeof(visited));
		bfs(taxi.y, taxi.x);
		//4. 목적지로 이동 
		int dy = destination[index].y;
		int dx = destination[index].x;
		if (visited[dy][dx] == 0) {
			f = -1;
			break;
		}
		taxi.y = dy, taxi.x = dx;
		destination.erase(destination.begin() + index);
		f -= (visited[dy][dx] - 1);
		if (f < 0)
			break;
		f += ((visited[dy][dx] - 1) * 2);
	}


	if (f <= 0)
		cout << -1 << endl;
	else
		cout << f << endl;
	return 0;
}