최소 스패닝 트리 문제이다.

일단 시간제한부터 보면 2초의 제한을 가지고 있다. 그 후 입력값의 범위를 보면 100000 개 이하의 노드와 1000000(백만개) 이하의 edge 가 있는 것을 볼 수 있다.

이 문제를 크루스칼을 통해 구하게 되면 nlog(n) 의 복잡도를 가지게 되어 널널하게 통과할 수 있다. (크루스칼 → 사실상 정렬알고리즘과 union-find 알고리즘의 복잡도와 비슷하다.)

여튼 크루스칼 알고리즘으로 최소 weight 를 가지는 edge 부터 차근차근 cycle 이 있는지 확인해가며 처리해주면 쉽게 풀리는 문제이다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;

int n, m;
int root[100001];
struct Node {
	int to, from, weight;
	Node(int a, int b, int c) : to(a), from(b), weight(c) {};
};

struct compare {
	bool operator()(Node a, Node b) {
		return a.weight > b.weight;
	}
};
int get_union(int a) {
	if (root[a] == a) return a;
	else {
		return get_union(root[a]);
	}
}

void set_union(int a, int b) {
	int ta = get_union(a);
	int tb = get_union(b);

	if (ta < tb) root[tb] = ta;
	else root[ta] = tb;
}
priority_queue<Node, vector<Node>, compare> pq;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	
	int ta, tb, tc;
	for (int i = 0; i < m; i++) {
		cin >> ta >> tb >> tc;
		Node tp(ta, tb, tc);
		pq.push(tp);
	}
	for (int i = 1; i <= n; i++) 
		root[i] = i;
	

	int _to, _from, _weight, res = 0;
	int _max = 0;
	while (!pq.empty()) {
		_to = pq.top().to;
		_from = pq.top().from;
		_weight = pq.top().weight;
		pq.pop();

		if (get_union(_to) == get_union(_from)) continue;
		else {
			set_union(_to, _from);
			res += _weight;
			_max = max(_max, _weight);
		}
	}
	cout << res - _max;
	return 0;
}

1021번: 회전하는 큐

단순한 구현문제이다.

시간제한은 2초임에 불구하고 입력값의 크기가 50이므로 n^2 의 복잡도를 가질 시 2500 밖에 걸리지 않아 매우 널널한 문제이다.

index 를 가지고 0일때 왼쪽으로 돌리면 다시 오른쪽 끝으로, 반대로 n일 때 오른쪽으로 돌리면 0으로.. 의 로직을 기준으로 코드를 짜면 끝나는 코드이다.

밑의 코드는 단순 무지성으로 코드만 짠거긴 한데 중간중간 왼쪽으로 돌릴지, 오른쪽으로 돌릴지에 대해 그리디 방식으로 구하게 되면 코드가 더 깔끔하게 나오게 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>


using namespace std;

int num[100];
int check[100];
int arr[100];
int n, m;

int get_right_num(int a) {
	return (a >= n) ? 1 : a + 1;
}
int get_left_num(int a) {
	return (a == 1) ? n : a - 1;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) num[i] = i;
	for (int i = 1; i <= m; i++) cin >> arr[i];
	
	int idx = 1;
	int res = 0, left_idx, right_idx, left_cnt, right_cnt;
	for (int i = 1; i <= m; i++) {
		left_idx = idx, left_cnt = 0;
		right_idx = idx, right_cnt = 0;

		while (num[left_idx] != arr[i]) {
			left_idx = get_left_num(left_idx);
			if (check[left_idx] == 0) left_cnt += 1;
		}

		while (num[right_idx] != arr[i]) {
			right_idx = get_right_num(right_idx);
			if (check[right_idx] == 0) right_cnt += 1;
		}
		
		idx = get_right_num(right_idx);
		while (check[idx] != 0) {
			idx = get_right_num(idx);
		}
		check[right_idx] = 1;
		res += min(left_cnt, right_cnt);
	}
	cout << res;
	return 0;
}

2346번: 풍선 터뜨리기

풍선을 터뜨리고 각 index 별로 터지는 순서를 적어야하는 줄 알고 삽질한 문제이다.

일단 시간제한이 2초에 입력값의 범위가 1000까지라 n^2 의 복잡도로는 널널하게 패스하기 때문에 넉넉잡아 풀어도 상관 없을거라고 생각한다.

로직은 단순하게 index 를 돌려가면서 0이 되었을 때, n-1 이 되었을 때 나누어서 풀면 된다. 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, input;
	deque<int> dq;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		dq.push_back(input);
	}
	
	int check[1001] = { 0, };
	int cnt = 2, cx, cidx = 0;
	check[0] = 1;
	cout << 1 << " ";
	for(int i=2 ; i<=n ; i++){
		cx = dq[cidx];
		// cidx 풍선 터뜨림

		int ct = 0;
		if (cx < 0) {
			while (ct < -1 * cx) {
				cidx = (cidx == 0) ? n - 1 : cidx - 1;
				if (check[cidx] != 0) continue;
				else ct++;
			}
		}
		else {
			while (ct < cx) {
				cidx = (cidx == n - 1) ? 0 : cidx + 1;
				if (check[cidx] != 0) continue;
				else ct++;
			}
		}
		check[cidx] = i;
		cout << cidx+1 << " ";
	}

	return 0;
}

1629번: 곱셈

 

시간복잡도를 먼저 봐야하는 문제이다.

0.5초의 시간제한에 2147483647 이하의 입력값에 직접 모든 계산을 돌린다면 엄청난 차이로 시간이 터지게 된다. 때문에 log(n) 이하의 알고리즘을 생각해야 한다.

log 를 보자마자 절반으로 나눠볼까? 라는 생각을 한 뒤 분할하여 값을 구하면 되지 않을까 생각이 든다. 즉 다음과 같은 로직으로 코드를 짤 수 있다.

1. 제곱수를 절반으로 쪼개 분할정복

2. 틀 만든 뒤 return (?!)

생각보다 간단하게 끝난다. 다만 계산 중간 곱한 뒤 나누는 과정에서 int 의 범위를 벗어날 수 있기 때문에 long long 으로 처리해주어야 한다.

#include <iostream>

using namespace std;
typedef long long LL

LL _get(LL x, LL y, LL z) {
	if (y == 1) return x % z;
	else {
		LL half = _get(x, y / 2, z);
		if (y % 2 == 0) {
			return (half * half) % z;
		}
		else {
			return (x * ((half * half) % z)) % z;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	LL a, b, c;
	cin >> a >> b >> c;

	cout << _get(a, b, c);
	return 0;
}

1918번: 후위 표기식

경우의 수 나눠서 처리하면 된다.

입력받은 string 을 돌면서

1. 숫자인 경우 answer 에 push

2. 연산자인 경우
   1. +, - 인 경우
      1. 이미 들어있는게 *, / 인 경우: 우선 순위가 높은 *, / 를 stack 에서 뺀 후 answer 에 push → 그리고 기존 거 stack 에 push
      2. 이미 들어있는게 +, - 인 경우: 먼저 들어있는 +, - 를 stack 에서 뺀 후 answer 에 push → 그리고 기존 거 stack 에 push
   2. *, / 인 경우
      1. 이미 들어있는게 *, / 인 경우: 먼저 들어있는 *, / 를 stack 에서 뺀 후 answer 에 push → 그리고 기존 거 stack 에 push
      2. 이미 들어있는게 +, - 인 경우: 기존의 *, / 가 우선순위 높으니 stack 에 바로 push
   3. (, ) 인 경우
      1. ( 인 경우 : answer 에 일단 push
      2. ) 인 경우 : ( 가 나올때까지 "pop → answer 에 push" 반복

이 로직을 직접 구현하면 처리 된다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef tuple<int, int, string> tii;
int root[500001];

bool check_oper(char c) {
	return (c == '*' || c == '+' || c == '-' || c == '/' || c == '(' || c == ')');
}
bool div_mul(char c) {
	return c == '*' || c == '/';
}
bool plu_min(char c) {
	return c == '+' || c == '-';
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string n;
	cin >> n;

	stack<char> st;
	string answer;
	for (int i = 0; i < n.size(); i++) {
		if (check_oper(n.at(i))) {
			if (st.empty()) 
				st.push(n.at(i));
			else {
				if (div_mul(st.top())){
					if (plu_min(n.at(i))) {
						while (1) {
							answer.push_back(st.top());
							st.pop();
							if (st.empty()) break;
							if (plu_min(st.top())) continue;
							else break;
						}
						st.push(n.at(i));
					}
					else if (div_mul(n.at(i))) {
						answer.push_back(st.top());
						st.pop();
						st.push(n.at(i));
					}
					else {
						if (n.at(i) == '(') st.push(n.at(i));
						else if (n.at(i) == ')') {
							while (st.top() != '(') {
								answer.push_back(st.top());
								st.pop();
							}
							st.pop(); // ( 제거
						}
					}
				}
				else if (plu_min(st.top())) {
					if (n.at(i) == ')') {
						while (st.top() != '(') {
							answer.push_back(st.top());
							st.pop();
						}
						if (st.top() == '(') st.pop(); // ( 제거
					}
					else if (plu_min(n.at(i))) {
						answer.push_back(st.top());
						st.pop();
						st.push(n.at(i));
					}
					else {
						st.push(n.at(i));
					}
				}
				else if(st.top() == '(' || st.top() == ')'){
					if (n.at(i) == ')') {
						while (st.top() != '(') {
							answer.push_back(st.top());
							st.pop();
						}
						if(st.top() == '(') st.pop(); // ( 제거
					}
					else st.push(n.at(i));
				}
			}
		}
		// 숫자인 경우
		else {
			answer.push_back(n.at(i));
		}
	}
	while (!st.empty()) {
		answer.push_back(st.top());
		st.pop();
	}
	cout << answer;

	return 0;
}

11000번: 강의실 배정

그리디 "활동 선택 문제" 방식의 문제이다.

먼저 시간복잡도부터 살펴보면 1초의 제한시간에 input 의 길이가 20만이다. 따라서 제곱의 복잡도를 가지게 되면 터진다는 걸 알 수 있다.

이 점에 착안해 각 프로세스를 돌면서 log(n) 의 탐색 복잡도 로직으로 같이 이어서 들을 강의를 체킹하여 문제를 풀기로 하였다.

로직은 다음과 같다.

1. 각 프로세스를 "시간 순 → 짧게 끝나는 순" 으로 정렬한다.
2. 정렬한 프로세스를 하나씩 돌면서 나머지 프로세스 중 바로 시작할 수 있는 프로세스를 이분탐색을 통해 찾는다. (반복)

2. 찾은 프로세스들을 모두 checking 해주고 다시 2번으로 돌아간다.

이에 대한 코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int window_size = number.size() - k;

    int max_idx = -1;
    char max_val;
    for(int i=0 ; i< window_size ; i++) {
        max_val = '0';
        for(int j = max_idx + 1 ; j<i+k+1 ; j++) {
            if(max_val < number.at(j)) {
                max_val = number.at(j);
                max_idx = j;
            }
        }
        answer.push_back(max_val);
    }    
    return answer;
}

i번째의 수를 고를 때, k 개를 뽑아야 되니까 최소 i부터 k+1 범위에 있는 수중에서 큰 수만을 고르게 되면 결국 전체적으로 봤을 때 최대 값이 생기게 된다.

그리디한 방법 하에, answer 는 앞자리 수가 크면 클수록 가중치가 크기 때문에 앞에서부터 뽑힐 수 있는 모든 후보군 중에서 큰 값을 뽑게 되면 결국 제일 큰 값이 처리되기 때문에 답이 나온다.

쉽게 설명하자면 각 자리수의 수를 확인할 수 있는 윈도우를 설정하고, 해당 윈도우에서 가장 큰 값을 체킹하고 answer 에 넣어준다. 그렇게 되면 확실하게 k 개를 뺀 개수가 나오게 되고 가장 큰 값이 답으로 나오게 된다.

1028번: 다이아몬드 광산

dp 문제였다.

dp 배열에 문자열을 넣고 drop up 방식으로 단순하게 탐색하는 식으로 문제를 풀 수 있었다.

로직은 다음과 같다.

dp[1] 부터 차례대로 값을 비교하되 하나의 dp 마다 n개의 수를 넣기 전의 dp 값과 비교하여 해당 수를 추가한 뒤 값이 더 큰 값을 dp 값으로 갱신하는 로직.

말이 좀 어려울 수 있겠지만 dp[i - (수의값)] 에서 해당 수를 첨가하여 커지나 안커지나만 확인하면 되는 문제였다.

dp 라 푸는데 좀 오래 걸렸지만.. 다음에는 더 잘 기억하자

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef tuple<int, int, string> tii;
string dp[200];

string convert(string a) {
	string res;
	if (a == "") return "";
	for (int i = 0; i < a.size(); i++) {
		if (a.at(i) == '0') continue;
		else {
			res = a.substr(i);
			break;
		}
	}
	if (res == "") return "0";
	else return res;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, input, money;
	vector<int> v;
	int _min = 50;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		v.push_back(input);
		_min = min(_min, input);
	}
	cin >> money;

	for (int i = _min; i <= money; i++) {
		for (int j = 0; j < n; j++) {
			if (i - v[j] < 0) continue;
			for (int k = 0; k < dp[i - v[j]].size(); k++) {
				if (dp[i - v[j]][k] - '0' >= j) continue;
				string new_str = convert(dp[i - v[j]].substr(0, k) + to_string(j) + dp[i - v[j]].substr(k + 1));
				// cout << new_str << endl;
				if (dp[i].size() < new_str.size()) {
					dp[i] = new_str;
				}
				else if (dp[i].size() == new_str.size()) {
					dp[i] = max(dp[i], new_str);
				}
			}
			if (dp[i - v[j]].empty() && j == 0)
				continue;

			string t = dp[i - v[j]] + to_string(j);
			if (dp[i].length() < t.length())
				dp[i] = t;
			else if (dp[i].length() == t.length())
				dp[i] = max(dp[i], t);
		}
	}

	if (dp[money].empty()) cout << 0;
	else {
		cout << dp[money];
	}
	return 0;
}