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

#include <bits/stdc++.h>
using namespace std;

struct Node_max {
	int idx, value;
	bool operator<(const Node_max& b) const {
		return value < b.value;
	}
};

struct Node_min {
	int idx, value;
	bool operator<(const Node_min &b) const {
		return value > b.value;
	}
};

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

	int t;
	cin >> t;
	for (int T = 0; T < t; T++) {
		int k;
		cin >> k;

		priority_queue<Node_max> max_q;
		priority_queue<Node_min> min_q;


		vector<bool> ch(k + 1, 0);
		int idx = 1;
		int q_size = 0;

		for (int i = 0; i < k; i++) {
			char c;
			int val;

			cin >> c >> val;

			if (c == 'I') {

				max_q.push({ idx,val });
				min_q.push({ idx,val });
				idx++;
			}
			else {
				if (val == -1) {
					
					while (!min_q.empty() && ch[min_q.top().idx]) {
						min_q.pop();
					}

					if (!min_q.empty()) {
						ch[min_q.top().idx] = 1;
						min_q.pop();
					}

				}
				else {
					while (!max_q.empty() && ch[max_q.top().idx]) {
						max_q.pop();
					}

					if (!max_q.empty()) {
						ch[max_q.top().idx] = 1;
						max_q.pop();
					}



				}
			}


		}

		int ans = 0;
		for (int i = 1; i < idx; i++) {
			if (ch[i] == 0) {
				ans++;
			}
		}
		if (ans == 0) {
			cout << "EMPTY\n";
		}
		else {
			
			while (!min_q.empty() && ch[min_q.top().idx]) {
				min_q.pop();
			}


			while (!max_q.empty() && ch[max_q.top().idx]) {
				max_q.pop();
			}


			cout << max_q.top().value << ' ' << min_q.top().value << '\n';



		}
	}

	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n;
vector<pair<int, int> > v;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		v.push_back({ a,b });
	}

	sort(v.begin(), v.end());

	priority_queue<int> Q;

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			Q.push(-v[i].second);
			continue;
		}

		if (v[i].first >= -Q.top()) {
			Q.pop();
			Q.push(-v[i].second);
		}
		else {
			Q.push(-v[i].second);
		}
	}

	cout << Q.size() << '\n';


	return 0;
}

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

1.문제설명

1. 서로 다른 사탕이 있으면 바꾼다.

2. 모든 행과 열에서 연속되는 최대 사탕의 수를 구해본다.

3. 1과 2를 모든 영역에 대해 반복해야한다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, ans;
char arr[51][51];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void Count() {
	for (int i = 0; i < n; i++) {
		int comp = arr[i][0];
		int cnt = 1;
		for (int j = 1; j < n; j++) {
			if (comp == arr[i][j]) {
				cnt++;
			}
			else {
				comp = arr[i][j];
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
		ans = max(ans, cnt);
	}

	for (int i = 0; i < n; i++) {
		int comp = arr[0][i];
		int cnt = 1;
		for (int j = 1; j < n; j++) {
			if (comp == arr[j][i]) {
				cnt++;
			}
			else {
				comp = arr[j][i];
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
		ans = max(ans, cnt);
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			arr[i][j] = s[j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {

			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];

				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (arr[i][j] != arr[nx][ny]) {
					swap(arr[i][j], arr[nx][ny]);
					Count();
					swap(arr[i][j], arr[nx][ny]);
				}
			}
		}
	}
	
	cout << ans << '\n';


	return 0;
}

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

1.문제설명

처음 봤을 때 이게 왜 다이나믹 프로그래밍 문제일까 의문이 드는 문제입니다.

어떻게 다이나믹 프로그래밍으로 구현해야할지 고민이 필요합니다.

다이나믹 프로그래밍의 핵심은

주어진 문제를 여러개의 부분 문제로 나누어 풀고

그 결과를 이용해서 주어진 문제를 해결 하는 것입니다.

주어진 S 문자열의 0번 char부터 A 집합의 문자열들과 서로 비교하면서

A의 문자열이 S문자열의 부분과 일치하는지 확인합니다.

이 과정을 반복해서 S문자열의 몇번째 char 까지 만들 수 있는지

bool자료형의 dp 배열에 저장해두면서 그 이후의 부분을 만들 수 있는지 판단하면 됩니다.

그림을 보면 이해하기 쉬울겁니다.

softwarecontest와 software이 7번째 까지 일치하니까

dp[8] = true로 만들어줍니다

7이 아니라 8에 두는 건 인덱스 관리가 7에두는 것보다 다음 숫자인 8에 두는게 쉽기 때문입니다.

그 후 dp배열을 확인하면서 dp[i] == 1 인 지점부터 다시 A의 문자열들과 비교해줍니다

software은 다르니까 넘어가게 되고 contest가 8번부터 일치하므로 다시 dp[15] == 1로 만들어줍니다.

결과상 dp[S.length()] == 1 이라면 문자열 S를 만들 수 있다는 뜻입니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n;
bool dp[101];
string s;
vector<string> A;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		A.push_back(tmp);
	}

	for (int i = 0; i < s.length(); i++) {
		if (dp[i] || i==0) {
			int st = i;
			
			for (int j = 0; j < n; j++) {
				//부분문자열을 합칠 때 원래 문자열보다 더 길어지는 경우는 제외
				if (st + A[j].length() > s.length()) continue;

				bool flag = true;
				for (int k = 0; k < A[j].length(); k++) {
					if (A[j][k] != s[st + k]) {
						flag = false;
						break;
					}
				}

				if (flag) {
					dp[st + A[j].length()] = 1;
				}
			}
		}
	}

	cout << dp[s.length()];


	return 0;
}

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

1. 문제설명

노드를 이어주는 간선을 제거했을 때

컴포넌트의 수가 증가한다면 각 컴포넌트의 노드 개수를 곱해서 결괏값에 더해야합니다.

이 문제는 이 방법대로 해결하기보다 역으로 생각해야 쉽게 풀 수 있습니다.

2.접근방법[알고리즘]

Union & Find 알고리즘을 응용합니다.

분할의 반대는 병합입니다. 

간선을 제거할 때 나눠지는 컴포넌트 노드의 수를 곱하는 대신

병합하기전 컴포넌트의 노드의 수를 곱하고 병합하면 더 쉽게 해결할 수 있습니다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, q;
vector<pair<int, int> > v(1);
bool ch[100003];
vector<int> del;
int unf[100003];

int Find(int x) {
	if(unf[x] < 0) return x;

	return unf[x] = Find(unf[x]);
}

//루트에 하위 노드의 개수를 저장합니다
void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if (a == b) return;

	if (unf[a] <= unf[b]) {
		unf[a] += unf[b];
		unf[b] = a;
	}
	else {
		unf[b] += unf[a];
		unf[a] = b;
	}
}

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

	memset(unf, -1, sizeof(unf));

	cin >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}

	for (int i = 0; i < q; i++) {
		int a;
		cin >> a;
		ch[a] = 1;
		del.push_back(a);
	}

	for (int i = 1; i <= m; i++) {
		if (ch[i] == 0) {
			Union(v[i].first, v[i].second);
		}
	}

	long long ans = 0;
	for (int i = del.size() - 1; i >= 0; i--) {
		int a = v[del[i]].first;
		int b = v[del[i]].second;

		if (Find(a) != Find(b)) {
			ans += (unf[Find(a)] * unf[Find(b)]);
		}
		Union(a, b);
	}

	cout << ans << '\n';


	return 0;
}

주의할점 : 정답이 INT_MAX를 넘어갑니다.

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

1. 문제설명

영어로 된 문제여서 구글 번역을 한번 돌리면 좀 더 쉽게 이해가 가능합니다.

Union & Find 알고리즘을 이용하여 문제를 해결했습니다.

N개의 Haybale을 spiceness에 대해 오름차순으로 정렬합니다.

spiceness가 작은 Haybale 부터 확인하면서 그 Haybale의 위 아래에 있는 Haybale 중

자신보다 spiceness가 작은 게 있으면 Union 해줍니다.

이 과정을 반복하다가

자신이 속한 집단의 flavor 값 합이 M 이상이 된다면

자신의 spiceness를 출력해주면 됩니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
int n;
long long m;
long long unf[100001];

pair<int, int> arr[100001];

struct Haybale {
	int node, flavor, spicy;
	bool operator<(const Haybale& b)const {
		return spicy < b.spicy;
	}
};

int Find(int x) {
	if (unf[x] < 0) return x;
	return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a == b) return;

	if (unf[a] >= unf[b]) {
		unf[b] += unf[a];
		unf[a] = b;
	}
	else {
		unf[a] += unf[b];
		unf[b] = a;
	}
}

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

	cin >> n >> m;
	vector<Haybale> v;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		arr[i] = { a,b };
		v.push_back({ i,a,b });
	}

	for (int i = 1; i <= n; i++) {
		unf[i] = -arr[i].first;
	}


	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		int node = v[i].node;

		if (node - 1 >= 1 && arr[node - 1].second <= arr[node].second) {
			Union(node - 1, node);
		}
		if (node + 1 <= n && arr[node].second >= arr[node + 1].second) {
			Union(node + 1, node);
		}

		if (-unf[Find(node)] >= m) {
			cout << arr[node].second;
			return 0;
		}
	}


	return 0;
}

m의 범위에 유의해야 메모리초과와 런타임에러를 방지할 수 있습니다.

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

#include <bits/stdc++.h>
using namespace std;

int n;
int cost[10003];
vector<int> adj[10003];
int degree[10003];
int res[10003];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];

        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int pre;
            cin >> pre;
            adj[pre].push_back(i);
            degree[i]++;
        }
    }

    int ans = 0;
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            res[i] = cost[i];
            Q.push(i);
            ans = max(res[i], ans);
        }
    }

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto nx : adj[x]) {
            res[nx] = max(res[nx], res[x] + cost[nx]);
            ans = max(ans, res[nx]);
            if (--degree[nx] == 0) {
                Q.push(nx);
            }
        }
    }


    cout << ans << '\n';
   
    return 0;
}

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

백트래킹을 이용한 풀이는

코드가 직관적이므로 별도로 설명하진 않겠습니다.

백트래킹 코드

#include <bits/stdc++.h>
using namespace std;

int n;
char arr[20];
bool ch[10];
int path[20];

long long minn = LLONG_MAX, maxx = LLONG_MIN;

void DFS(int L) {
    if (L == n + 1) {
        for (int i = 1; i <= n; i++) {
            if (arr[i] == '<') {
                if (path[i - 1] > path[i]) {
                    return;
                }
            }
            else {
                if (path[i - 1] < path[i]) {
                    return;
                }

            }
        }


        long long x = 0;

		for (int i = 0; i < L; i++) {
			x = x * 10 + path[i];
		}

        minn = min(minn, x);
        maxx = max(maxx, x);

    }
    else {
        for (int i = 0; i <= 9; i++) {
            if (ch[i] == 0) {
				ch[i] = 1;
				path[L] = i;
				DFS(L + 1);
				ch[i] = 0;
			}
        }
    }
}


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

    cin >> n;

    long long comp = pow(10, n);

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }


    DFS(0);

    cout << maxx << '\n';

    if (minn < comp) {
        cout << 0;
    }

    cout << minn << '\n';



    return 0;
}

백준 2529 부등호 위상정렬로 푸는 법

위상정렬을 공부하다 다른 블로그의 설명을 많이 봤는데 이해가 잘 되지 않았어서

한참 헤맸습니다.

노드 번호와 해당 노드의 숫자를 별개로 생각해야합니다.

A노드와 B 노드가 있다고 가정합니다.

부등호를 기준으로

A > B 라면 A -> B 를 향하는 간선을 주고

위상정렬을 수행합니다.

예제에서 먼저 최댓값을 생각해보면

2
< >

A < B > C 이면

B -> A

B -> C 가 간선이 되고

위상정렬을 수행하면 순서가

B A C 이거나

B C A 가 됩니다.

이 뜻은 B가 가장 커야하고 A와 C는 따로 정해주어야 한다는 뜻입니다.

그래서 B는 9가 되고 A C 가 8 7이 되어야 하는데

최댓값을 구할 때 먼저 나온게 커야하므로 A에 8을 주고 C에 7을주면

B : 9 ,

A : 8,

C : 7,

이 되고 원래 숫자는 ABC 순서이므로

897이 최대가 됩니다.

최솟값을 구할 땐

가장 큰 수인 B에 숫자를 넣을 때 9부터 넣는게 아닌 K(2)부터 넣어야 최솟값이 구해집니다.

그리고 A 와 C를 정할 때 앞에 있는 숫자가 작은 숫자여야 최솟값이 되므로 A에 0 C에 1을 넣으면 됩니다.

그러면

B : 2

A : 0

C : 1

이므로 정답은 ABC 021이 됩니다.

간선 정보는 동일하게 이용하고 degree(차수)를 줄여주면서 큐를 돌 때

노드번호를 각각 최소힙, 최대힙으로 주면서 뽑아주면서

노드에 숫자를 하나씩 넣으면 됩니다.

위상정렬 코드

#include <bits/stdc++.h>
using namespace std;

int k;
char arr[20];

int node[11]; // 최댓값 구하는데 사용
int degree[11]; 
int node2[11]; // 최솟값 구하는데 사용
int degree2[11]; 
bool ch[11][11];


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

    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> arr[i];

        if (arr[i] == '<') {
            ch[i + 1][i] = 1;
            degree[i]++;
            degree2[i]++;
        }
        else{
            ch[i][i + 1] = 1;
            degree[i + 1]++;
            degree2[i + 1]++;
        }
    }

    priority_queue<int> Q;

    //최댓값 구하기 

    for (int i = 1; i <= k + 1; i++) {
        if (degree[i] == 0) {
            Q.push(-i);
        }
    }

    int cnt = 9;
    while (!Q.empty()) {
        int x = -Q.top();
        Q.pop();
        node[x] = cnt--;
        for (int i = 1; i <= k + 1; i++) {
            if (ch[x][i] == 1) {
                if (--degree[i] == 0) {
                    Q.push(-i);
                }
            }
        }
    }

    for (int i = 1; i <= k + 1; i++) {
        cout << node[i];
    }
    cout << '\n';





    //최솟값 구하기

    for (int i = 1; i <= k + 1; i++) {
        if (degree2[i] == 0) {
            Q.push(i);
        }
    }

    cnt = k;
    while (!Q.empty()) {
        int x = Q.top();
        Q.pop();
        node2[x] = cnt--;
        for (int i = 1; i <= k + 1; i++) {
            if (ch[x][i] == 1) {
                if (--degree2[i] == 0) {
                    Q.push(i);
                }
            }
        }
    }

    for (int i = 1; i <= k + 1; i++) {
        cout << node2[i];
    }
    cout << '\n';


   
    return 0;
}

위상정렬을 이용했을 때 시간은 0ms

백트래킹을 이용했을 때 120ms

백트래킹에서 가지치기를 하진 않았지만, 위상정렬을 이용할 때

더 빠른 시간 내에 문제를 해결 할 수 있습니다.