이것 저것 &

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

수학적인 관점에서 생각해봐야 하는 그리디 문제였습니다. 

접근방식

1. 처음에는 단순히 arr[0], arr[1]만 비교해주고 값을 지워가면 되는 것으로 이해함

2. 근데 예외가 분명히 존재함

7 3

7654321

결과값은 7654

3. 뒤에 있는 값들도 함께 고려해야한다는 것을 알게됨

4. dequeue에 값들을 저장하고  뒤에 있는 값보다 작은 경우에는 dequeue에서 제외해주는 형태로 구현하자!

문제풀이 

1. 문자열의 이전 값(deque에 저장된) 들이 더 작다면 pop을 계속 시행, k값 감소

2. deque에 해당 문자열 삽입 

3. 출력할 때는 deq.size() - k만큼 출력

아래는 정답 코드

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

int n, k;
string val;
deque <char> deq;
int main() {
	iostream::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	cin >> val;

	for (int i = 0; i < val.length(); i++) {

		while (k && !deq.empty() && deq.back() < val[i]) {
			deq.pop_back();
			k--;
		}
		deq.push_back(val[i]);
	}


	for (int i = 0; i < deq.size() - k; i++) 
		cout << deq[i];
	
	cout << "\n";

	return 0;
}

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

자료구조중에서 스택을 사용해야 하는 문제였습니다.

접근방식

1. 일반적인 방식을 생각한다면 최악의 경우에는 O(n^2)이 될수 있기 때문에 시간초과가 일어나는 것을 인지 

2. 항상 자신의 왼쪽에서 가까운 값들 부터 확인해야 한다는 아이디어를 통해서 스택을 사용하면 검색을 줄일 수있다는 것을 인지 

문제풀이 

1. 스택이 비어있다면 0을 출력

2. 스택에 값이 있다면, 스택의 top값이 현재 값보다 클때까지 pop!

3. 다시 1번을 수행한다.

아래는 정답코드입니다.

#include <iostream>
#include <stack>
using namespace std;
int n;
int arr[500000];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;

	stack <pair<int, int>> stk;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];

		if (stk.empty()) {
			stk.push(make_pair(i, arr[i]));
			cout << 0 << ' ';
		}
		else {
			
			while (!stk.empty()) {
				if (stk.top().second > arr[i]) {
					cout << stk.top().first << ' ';
					break;
				}
				else
					stk.pop();
				
			}

			if (stk.empty())
				cout << 0 << ' ';
			stk.push(make_pair(i, arr[i]));
		}

		
	}
	cout << "\n";


	return 0;
}

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