-쇠 막대기(10799, 백준)
기본적인 STL stack자료구조 응용 문제이다. '('이 들어올때는 stack에 push해주고, ')'이 들어오면 한 막대기가 완전히 잘린 것임으로 ans++을 해준다. 하지만 '('와 ')'가 연속해서 들어오는 경우 즉, 레이저가 들어오게되면, 현재범위에 있는 모든 막대기를 잘라야함으로, stack의 크기만큼 ans에 더해준다.
<소스 코드>
더보기
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
int l;
char s[100010];
stack <char> st;
int main()
{
int i, j;
scanf("%s", s);
l = strlen(s);
for (i = 0; i < l - 1; i++) {
if (s[i] == '(' && s[i + 1] == ')') {
s[i] = '1';
s[i + 1] = '0';
}
}
int ans = 0;
for (i = 0; i < l; i++) {
if (s[i] == '0') continue;
if (s[i] == '1') ans += st.size();
if (s[i] == '(') {
st.push(s[i]);
}
if (s[i] == ')') {
ans++;
st.pop();
}
}
printf("%d", ans);
return 0;
}-괄호의 값(2504, 백준)
위 문제와 마찬가지로, stack라이브러리를 사용하여 간단히 구할 수 있다. 괄호의 수를 레벨로 두고, cnt배열을 만들어, 괄호가 쌍으로 만나 pop될때, 레벨-1 의 cnt배열에 현재까지의 값에 ()라면 2를, []라면 3을 곱해준 값을 더해준다. 즉 속해있는 괄호의 개수가 같은 구간끼리는 더해주고 아닌 구간은 곱해주면 되는 문제이다. cnt배열을 선언한다는 생각이 좀 힘들었던것 같다.
<소스 코드>
더보기
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <string.h>
using namespace std;
char s[35];
stack <char> st;
int cnt[35];
int main()
{
int i, j;
scanf("%s", s);
int l = strlen(s);
for(i=0;i<l;i++) {
if(s[i] == '(') st.push(s[i]);
else if(s[i] == '[') st.push(s[i]);
else if(s[i] == ')') {
if(st.empty()) {
printf("0");
return 0;
}
if(st.top() == '(') {
st.pop();
if(cnt[st.size() + 1] == 0) cnt[st.size()] += 2;
else cnt[st.size()] += 2*cnt[st.size() + 1];
cnt[st.size() + 1] = 0;
}
else {
printf("0");
return 0;
}
}
else if(s[i] == ']') {
if(st.empty()) {
printf("0");
return 0;
}
if(st.top() == '[') {
st.pop();
if(cnt[st.size() + 1] == 0) cnt[st.size()] += 3;
else cnt[st.size()] += 3*cnt[st.size() + 1];
cnt[st.size() + 1] = 0;
}
else {
printf("0");
return 0;
}
}
}
printf("%d", cnt[0]);
return 0;
}-학교 탐방하기(134818, 백준)
MST(최소 비용 신장 트리)문제였다. 문제에서 그래프까지 그려주며 MST문제인 티를 내서 MST를 생각하고, 풀이를 떠올리는대 까지는 오래걸리지 않았다. MST를 2번 실행시켜 최대, 최소의 값을 구해주면된다. 최소값을 구할때는 정렬을 내리막길이 올라가는 길보다 우선순위가 되게 compare해주고, 최대값의 경우에는 오르막길이 내리막길보다 우선순위가 되게 정렬해준뒤, 각각 MST를 돌려주면 된다.
<소스 코드>
더보기
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m;
int par[1010];
struct dat{
int x, y, val;
};
bool comp(dat a, dat b)
{
return a.val < b.val;
}
int ffind(int x)
{
if(par[x] == x) return x;
else return par[x] = ffind(par[x]);
}
void funion(int x, int y)
{
int a = ffind(x);
int b = ffind(y);
if(a < b) par[b] = a;
else par[a] = b;
return;
}
vector <dat> vec;
int main()
{
int i, j;
scanf("%d %d", &n, &m);
m++;
for(i=0;i<m;i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
vec.push_back({x, y, z});
}
for(i=1;i<=n;i++) par[i] = i;
sort(vec.begin(), vec.end(), comp);
// for(i=0;i<m;i++) printf("%d %d %d\n", vec[i].x, vec[i].y, vec[i].val);
int ansL = 0, ansS = 0;
for(i=0;i<m;i++) {
int x = vec[i].x, y = vec[i].y;
if(ffind(x) == ffind(y)) continue;
funion(x, y);
if(vec[i].val == 0) ansL++;
}
for(i=0;i<=n;i++) par[i] = i;
for(i=0;i<m;i++) {
int val = vec[i].val;
if(val == 1) vec[i].val = 0;
else vec[i].val = 1;
}
sort(vec.begin(), vec.end(), comp);
// for(i=0;i<m;i++) printf("%d %d %d\n", vec[i].x, vec[i].y, vec[i].val);
for(i=0;i<m;i++) {
int x = vec[i].x, y = vec[i].y;
if(ffind(x) == ffind(y)) continue;
funion(x, y);
if(vec[i].val == 1) ansS++;
}
printf("%d", (ansL * ansL) - (ansS * ansS));
return 0;
}-트리(4803, 백준)
노드와 간선들이 주어졌을 때, 이 그래프에서 트리의 수를 찾는 문제이다. 트리는 우선 싸이클이 없어야함으로, 싸이클 판단을 위해 Union Find(분리집합)알고리즘을 이용하였다. 로직은 연결된 노드를 모두 유니온해가되, 싸이클이 발생(연결하려는 두 노드의 부모노드가 같은 상황)했다면, 해당 노드와 연결되어있는 모든 노드에 부모노드를 -1로 바꿔버리고 나머지를 탐색했다. 모두 연결시켜 준 뒤, 모든노드를 순회해가면서 -1이아니고 서로다른 부모노드의 수만큼 cnt++시켜 구했다.
<소스 코드>
더보기
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int par[510], ch[510];
int n, m;
int ffind(int x)
{
if(x == -1) return -1;
if(x == par[x]) return x;
else return par[x] = ffind(par[x]);
}
void funion(int x, int y)
{
int a = ffind(x), b = ffind(y);
if(a < b) par[b] = a;
else par[a] = b;
return;
}
int main()
{
int i, j;
int tc = 0;
while(1) {
tc++;
scanf("%d %d", &n, &m);
if(n == 0 && m == 0) break;
for(i=1;i<=n;i++) par[i] = i;
for(i=0;i<m;i++) {
int x, y;
scanf("%d %d", &x, &y);
int fx = ffind(x), fy = ffind(y);
if(fx == fy) {
par[fx] = -1;
}
funion(x, y);
}
int ans = 0;
for(i=1;i<=n;i++) {
int fx = ffind(i);
if(fx == -1) continue;
if(ch[fx] == 0) ch[fx] = 1, ans++;
}
if(ans > 1) printf("Case %d: A forest of %d trees.\n", tc, ans);
else if(ans == 1) printf("Case %d: There is one tree.\n", tc);
else if(ans == 0) printf("Case %d: No trees.\n", tc);
for(i=0;i<=n;i++) ch[i] = 0;
}
return 0;
}-노드사이의 거리(1240, 백준)
주어진트리에서, 주어진 두 노드간의 최소 거리를 구하는 문제이다. 아무런 생각없이 다익스트라(Dijkstra)를 돌려서 맞췄다. 시간제한과 N범위를 보니 visit을 체크해준다면, BFS로도 풀릴 것 같다.
<소스 코드>
더보기
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector <pair<int, int>> vec[1010];
int Dijkstra(int s, int e)
{
int i, j;
int dis[1010];
priority_queue <pair<int, int>> pq;
pq.push({ 0, s });
for (i = 0; i <= n; i++) dis[i] = 2e9;
dis[s] = 0;
while (!pq.empty()) {
int now_idx = pq.top().second, now_val = -pq.top().first;
pq.pop();
if (dis[now_idx] < now_val) continue;
for (i = 0; i < vec[now_idx].size(); i++) {
int idx = vec[now_idx][i].first, val = now_val + vec[now_idx][i].second;
if (dis[idx] > val) {
dis[idx] = val;
pq.push({ -val, idx });
}
}
}
return dis[e];
}
int main()
{
int i, j;
scanf("%d %d", &n, &m);
for (i = 0; i < n - 1; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
vec[x].push_back({ y, z });
vec[y].push_back({ x, z });
}
for (i = 0; i < m; i++) {
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", Dijkstra(x, y));
}
return 0;
}'PS(알고리즘 문제풀이) 관련 글 > PS일지' 카테고리의 다른 글
| 2024-03-07 (1) | 2024.03.07 |
|---|---|
| 2024-03-06 (2) | 2024.03.06 |
| 2024-03-04 (0) | 2024.03.04 |
| 2024-03-03 (0) | 2024.03.03 |
| 2024-03-02 (0) | 2024.03.03 |
