굳건하게

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

최단경로 다익스트라

 시작지점 S에서 최단거리로 도착 후보 지점으로 갈 때, 최단 경로에 G-H 교차로가 포함되어있다면 우리가 원하는 정답이다. 어렵게 생각하지말고, S 에서 어떤 목적지 D로 가는 최단 거리가 S에서 G로가는 최단거리 + G에서 H로 가는 최단거리 + H에서 D로가는 최단거리와 같거나 반대로 S에서 H로 가는 최단거리 + H에서 G로 가는 최단 거리 + G 에서 D로가는 최단거리와 같은지 체크하면 된다.

 따라서, 다익스트라 알고리즘을 이용해 시작지점 S / G / H 에서 각각 다른 모든 정점과의 최단 거리를 구하면 된다.

#include<iostream>
#include<queue>
#include<algorithm>

#define INF 999999999
using namespace std;

vector<int> dijkstra(vector<pair<int, int>> graph[2001], int n , int s) {
	priority_queue<pair<int, int>> pq;
	vector<int> distance(n + 1, INF);
	distance[s] = 0;
	pq.push({ 0, s });
	while (!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if (distance[here] < cost) continue;
		for (int i = 0; i < graph[here].size(); i++) {
			int next = graph[here][i].first;
			int nextDist = graph[here][i].second + cost;
			if (distance[next] > nextDist) {
				distance[next] = nextDist;
				pq.push({ -nextDist, next });
			}
		}
	}
	return distance;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int T;
	cin >> T;
	while (T--) {
		int n, m, t, s, g, h;
		cin >> n >> m >> t >> s >> g >> h;

		vector<pair<int, int>> graph[2001];
		vector<int> destination(t);
		for (int i = 0, a, b, d; i < m; i++) {
			cin >> a >> b >> d;
			graph[a].push_back({ b, d });
			graph[b].push_back({ a, d });
		}
		for (int i = 0; i < t; i++)
			cin >> destination[i];

		vector<int> distanceS = dijkstra(graph, n, s);
		vector<int> distanceG = dijkstra(graph, n,g);
		vector<int> distanceH = dijkstra(graph, n,h);

		sort(destination.begin(), destination.end());
		for (int i = 0; i < t; i++) {
			if (distanceS[destination[i]] != INF && distanceS[g] + distanceG[h] + distanceH[destination[i]] == distanceS[destination[i]])
				cout << destination[i] << ' ';
			else if (distanceS[destination[i]] != INF && distanceS[h] + distanceH[g] + distanceG[destination[i]] == distanceS[destination[i]])
				cout << destination[i] << ' ';
		}
		cout << '\n';
	}
}

문제 : https://www.acmicpc.net/problem/1744

그리디 Greedy

그리디 기법을 이용해서 문제를 해결할 수 있습니다.

● 입력을 양수와 음수, 0 으로 구분합니다.

● 양수는 큰 수부터 차례대로 2개씩 묶어서 곱해서 더해주면 됩니다. 이때, 2개씩 묶는데 1이 포함되어있다면 곱하는 것보다 그냥 더하는게 최대값이므로 따로 처리해줍니다.

● 음수는 절대값이 큰 수부터 차례대로 2개씩 묶어서 곱해서 더해주면 양수를 만들 수 있습니다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(int a, int b) {
	if (a < b)
		return false;
	return true;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, x;
	vector<int> plus, minus;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> x;
		if (x > 0) plus.push_back(x);
		else minus.push_back(x);
	}
	sort(minus.begin(), minus.end(), cmp);
	sort(plus.begin(), plus.end());

	int ans = 0;
	while (!plus.empty()) {
		 if (plus.size() >= 2) {
			 if (plus[plus.size() - 1] == 1 || plus[plus.size() - 2] == 1)
				 ans += plus[plus.size() - 1] + plus[plus.size() - 2];
			 else
				 ans += plus[plus.size() - 1] * plus[plus.size() - 2];
			plus.pop_back();
		}
		else 
			ans += plus[plus.size() - 1];
		plus.pop_back();
	}
	while (!minus.empty()) {
		if (minus.size() >= 2) {
			ans += minus[minus.size() - 1] * minus[minus.size() - 2];
			minus.pop_back();
		}
		else
			ans += minus[minus.size() - 1];
		minus.pop_back();
	}
	cout << ans;
	return 0;
}

문제 : https://www.acmicpc.net/problem/5670

트라이 Trie

  자료구조 트라이를 이용하는 문제입니다.

 1) 들어오는 모든 문자열을 insert 해서 트라이를 만듭니다.

 2) 문자열을 하나씩 트라이에서 탐색을 수행합니다.

   2-1) 현재 첫 번째 글자라면 무조건 버튼을 눌러야 하므로 다음 글자로 넘어가며 카운트를 증가합니다.

   2-2) 현재 글자에서 다음 글자로 가는 길이 2가지 이상이거나 혹은 현재 글자에서 끝난 문자열이 있다면 버튼을 눌러야 하므로 다음 글자로 넘어가며 카운트를 증가합니다.

   2-3) 위의 경우가 아니라면 자동으로 입력되므로 카운트를 증가시키지 않고 다음 글자로 탐색을 진행합니다.

 알고리즘은 위와 같이 간단합니다. 하지만, EOF가 입력될 때까지 매번 트라이를 구현해야하는 문제로, delete 를 하지 않는다면 메모리 초과가 발생합니다.

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>

using namespace std;

struct Trie {
	bool finish;    //끝나는 지점을 표시해줌
	Trie* next[26];    //26가지 알파벳에 대한 트라이
	Trie() {
		finish = false;
		memset(next, 0, sizeof(next));
	}
	~Trie() {
		for (int i = 0; i < 26; i++)
			if (next[i])
				delete next[i];
	}

	void insert(const char* key) {
		if (*key == '\0')
			finish = true;    //문자열이 끝나는 지점일 경우 표시
		else {
			int curr = *key - 'a';
			if (next[curr] == NULL)
				next[curr] = new Trie();    //탐색이 처음되는 지점일 경우 동적할당
			next[curr]->insert(key + 1);    //다음 문자 삽입
		}
	}

	int find(const char* key, int cnt) {
		if (*key == '\0')
			return cnt;
		if (cnt == 0)
			return next[*key - 'a']->find(key + 1, cnt + 1);

		int check = 0;
		for (int i = 0; i < 26; i++)
			if (next[i] != NULL)
				check++;


		if (check > 1 || finish) // 가는 길이 2가지 이상
        		cnt++;
        return next[*key - 'a']->find(key + 1, cnt);
	}
};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	while (1) {
		int N;
		cin >> N;
		if (cin.eof())
			break;
		Trie* trie = new Trie();

		vector<string> list(N);
		for (int i = 0; i < N; i++){
			cin >> list[i];
			trie->insert(list[i].c_str());
		}
        
		int total = 0;
		for (int i = 0; i < N; i++)
			total += trie->find(list[i].c_str(), 0);

		cout << fixed;
		cout.precision(2);
		cout << double(total) / double(N) << '\n';
        
        delete trie;
	}
	return 0;
}

문제 : https://www.acmicpc.net/problem/5052

트라이 trie 문자열

 자료구조 트라이를 이용해서 문자열을 다 insert 해놓은 후, 모든 Input 문자열에 대해서 find를 진행하며, 해당 문자열 탐색이 끝나기 전에 terminal 이 true인 상황이 발생하면 다른 완성된 문자열이 탐색된 것이므로 NO를 출력하고 아니라면 YES를 출력한다.

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

struct TrieNode {
	TrieNode* child[10];
	bool terminal;

	TrieNode() : terminal(false) {
		memset(child, 0, sizeof(child));
	}
	~TrieNode() {
		for (int i = 0; i < 10; i++)
			if (child[i])
				delete child[i];
	}

	void insert(const char* key) {
		if (*key == 0)
			terminal = true;
		else {
			int next = (*key - '0');
			if (child[next] == NULL)
				child[next] = new TrieNode();
			child[next]->insert(key + 1);
		}
	}

	bool find(const char* key) {
		if (*key == 0)
			return false;
		if (terminal)
			return true;
		int next = (*key - '0');
		if (child[next] == NULL)
			return false;
		return child[next]->find(key + 1);
	}
};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while (t--) {
		int n;
		TrieNode* trie = new TrieNode();
		vector<string> input;
		cin >> n;
		for (int i = 0; i < n; i++) {
			string temp;
			cin >> temp;
			input.push_back(temp);
			trie->insert(temp.c_str());
		}
		bool flag = false;
		for (int i = 0; i < n; i++) {
			if (trie->find(input[i].c_str()) == true) {
				flag = true;
				break;
			}
		}
		if (flag) cout << "NO\n";
		else cout << "YES\n";
	}
}