반응형

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

 

3755번: Double Queue

The new founded Balkan Investment Group Bank (BIG-Bank) opened a new office in Bucharest, equipped with a modern computing environment provided by IBM Romania, and using modern information technologies. As usual, each client of the bank is identified by a

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 두 개 선언해, 오름차순과 내림차순으로 각각 저장합니다.

 

2. visited 배열을 만들어 현재 K 고객이 서비스를 이용한 상태인지 그렇지 않은 상태인지 저장합니다.

 

3. 입력되는 명령어에 따라 값을 출력해줍니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<queue>
 
using namespace std;
 
int visited[1000000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int cmd;
    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> greater;
    priority_queue<pair<int, int>, vector<pair<int, int>>, less<>> less;
 
    while (1) {
        cin >> cmd;
 
        if (cmd == 1) {
            int K, P;
            cin >> K >> P;
            greater.push({ P,K });
            less.push({ P,K });
            visited[K] = 0;
        }
        else if (cmd == 2) {
            while (1) {
                if (less.empty()) {
                    cout << 0 << '\n';
                    break;
                }
                const int K = less.top().second;
                less.pop();
                if (visited[K] != 1) {
                    visited[K] = 1;
                    cout << K << '\n';
                    break;
                }
            }
        }
        else if (cmd == 3) {
            while (1) {
                if (greater.empty()) {
                    cout << 0 << '\n';
                    break;
                }
                const int K = greater.top().second;
                greater.pop();
                if (visited[K] != 1) {
                    visited[K] = 1;
                    cout << K << '\n';
                    break;
                }
            }
        }
        else {
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 9084번 - 동전 (C++)  (0) 2023.09.13
[ 백준 ] 22116번 - 창영이와 퇴근 (C++)  (0) 2023.09.12
[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)  (0) 2023.09.10
[ 백준 ] 16940번 - BFS 스페셜 저지 (C++)  (0) 2023.09.09
[ 백준 ] 16936번 - 나3곱2 (C++)  (0) 2023.09.08
반응형

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

 

2610번: 회의준비

첫째 줄에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/24

 

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk

rudalsd.tistory.com

 

 

1. 서로 알고 있는 관계에 대해 입력받고, 그래프로 이어줍니다.

 

2. dfs를 활용하여 이어져 있는 사람들끼리 그룹으로 묶고, 번호를 매기고, 각 사람들이 어떤 그룹에 속해있는지 저장합니다.

 

3. 플로이드 와샬 알고리즘을 이용하여 각 사람들끼리의 거리를 저장합니다.

 

4. 1부터 N까지 for문을 이용해 돌면서 각 번호의 사람이 이어져 있는 사람 중 가장 먼 사람을 Max에 저장하고, 그 값이 가장 적은 사람을 ans[ i ]에 저장합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> list[101];
int group[101];
int arr[101][101];
pair<int,int> ans[101];
int cnt;
 
void dfs(int cur)
{
    for (auto& next : list[cur]) {
        if (group[next] == 0) {
            group[next] = cnt;
            dfs(next);
        }
    }
 
    return;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        list[u].push_back(v);
        list[v].push_back(u);
        arr[u][v] = 1;
        arr[v][u] = 1;
    }
 
    for (int i = 1; i <= N; i++) {
        if (group[i] == 0) {
            group[i] = ++cnt;
            dfs(i);
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (arr[j][i] != 0 && arr[i][k] != 0) {
                    if (arr[j][k] == 0 || arr[j][k] > arr[j][i] + arr[i][k]) {
                        arr[j][k] = arr[j][i] + arr[i][k];
                    }
                }
            }
        }
    }
 
    for (int i = 1; i <= cnt; i++) {
        ans[i].second = 987654321;
    }
 
    for (int i = 1; i <= N; i++) {
        int Max = 0;
        for (int j = 1; j <= N; j++) {
            if (i != j) {
                Max = max(Max, arr[i][j]);
            }
        }
 
        if (ans[group[i]].second > Max) {
            ans[group[i]].second = Max;
            ans[group[i]].first = i;
        }
    }
 
    cout << cnt << '\n';
 
    sort(ans + 1, ans + cnt + 1);
 
    for (int i = 1; i <= cnt; i++) {
        cout << ans[i].first << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1339번 - 단어 수학 (C++)  (0) 2023.09.01
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 1939번 - 중량제한 (C++)  (0) 2023.08.28
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
반응형

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

 

1939번: 중량제한

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언하고, vect[ i ] = i로 초기화합니다.

 

2. arr 배열을 거리를 기준으로 내림차순으로 정렬합니다.

 

3. Union-Find를 이용하여 각 지점들을 연결하고, 각 공장 사이에 길이 완성되었다면 연결된 순간의 다리의 길이를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<algorithm>
 
using namespace std;
 
struct node {
    int A, B, C;
};
 
bool cmp(node left, node right)
{
    return left.C > right.C;
}
 
int N, M;
node arr[100000];
int vect[10001];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int A, int B)
{
    int pA = Find(A);
    int pB = Find(B);
 
    vect[pB] = pA;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        arr[i] = { A,B,C };
    }
 
    int s, e;
    cin >> s >> e;
 
    sort(arr, arr + M, cmp);
 
    for (int i = 0; i < M; i++) {
        const int A = arr[i].A;
        const int B = arr[i].B;
        const int C = arr[i].C;
 
        if (Find(A) != Find(B)) {
            Union(A, B);
        }
 
        if (Find(s) == Find(e)) {
            cout << C;
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
[ 백준 ] 11058번 - 크리보드 (C++)  (0) 2023.08.27
[ 백준 ] 2758번 - 로또 (C++)  (0) 2023.08.26
[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
반응형

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

 

2463번: 비용

첫 번째 줄에 정점의 수 N (1< ≤ N ≤ 100,000)과 간선의 수 M (1 ≤ M ≤ 100,000)이 빈칸을 사이에 두고 주어진다. 다음 M개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 x,y,w가 빈칸

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열과 연결된 노드의 개수를 저장할 cnt 배열을 선언합니다.

 

2. vect[ i ] = i, cnt[ i ] = 1로 초기화하고, 모든 간선의 길이를 더해 sum에 저장합니다.

 

3. 모든 간선을 저장할 arr 배열을 선언하고, 간선의 길이를 기준으로 내림차순으로 정렬합니다.

 

4. for문으로 arr 배열을 돌면서 Union-Find를 이용하여 노드들이 연결될 때마다 ans에 sum을 더해주고, sum에서 간선의 길이를 빼줍니다.

 

5. ans % 1,000,000,000을 출력해줍니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct edge {
    int u, v, c;
};
 
int N, M;
edge arr[100000];
int vect[100001];
int cnt[100001];
 
bool cmp(edge left, edge right)
{
    return left.c > right.c;
}
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = vect[a];
    int pb = vect[b];
 
    vect[pb] = pa;
    cnt[pa] += cnt[pb];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    ll sum = 0;
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
        cnt[i] = 1;
    }
 
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        arr[i] = { u,v,c };
 
        sum += c;
    }
 
    sort(arr, arr + M, cmp);
 
    ll ans = 0;
 
    for (int i = 0; i < M; i++) {
        const int u = arr[i].u;
        const int v = arr[i].v;
        const int c = arr[i].c;
 
        if (Find(u) != Find(v)) {
            ans += sum * cnt[Find(u)] * cnt[Find(v)];
            Union(u, v);
        }
 
        sum -= c;
    }
 
    cout << ans % 1000000000;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2580번 - 스도쿠 (C++)  (0) 2023.08.25
[ 백준 ] 4343번 - Arctic Network (C++)  (0) 2023.08.24
[ 백준 ] 2479번 - 경로 찾기 (C++)  (0) 2023.08.22
[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
반응형

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

 

10216번: Count Circle Groups

백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 진영의 위치와 R을 입력받아 arr에 저장하고, visited 배열을 만들어 각 진영의 방문 여부를 체크해 줍니다.

 

2. for문을 통해 모든 진영을 돌면서 visited[ i ] 가 0이라면 ans++를 해주고 bfs를 돌며 이어진 진영의 visited를 1로 갱신해 줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int x, y, R;
};
 
int T, N;
node arr[3000];
int visited[3000];
 
void bfs(int num)
{
    queue<int> q;
 
    q.push(num);
 
    while (!q.empty()) {
        const int x = arr[q.front()].x;
        const int y = arr[q.front()].y;
        const int R = arr[q.front()].R;
        q.pop();
 
        for (int i = 0; i < N; i++) {
            if (visited[i] == 0) {
                const int xx = arr[i].x;
                const int yy = arr[i].y;
                const int RR = arr[i].R;
 
                if (sqrt(pow(x - xx, 2) + pow(y - yy, 2)) <= R + RR) {
                    visited[i] = 1;
                    q.push(i);
                }
            }
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        cin >> N;
 
        for (int i = 0; i < N; i++) {
            int x, y, R;
            cin >> x >> y >> R;
            arr[i] = { x,y,R };
        }
 
        int ans = 0;
        fill(visited, visited + N, 0);
 
        for (int i = 0; i < N; i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                bfs(i);
                ans++;
            }
        }
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2591번 - 숫자카드 (C++)  (0) 2023.08.21
[ 백준 ] 2116번 - 주사위 쌓기 (C++)  (0) 2023.08.20
[ 백준 ] 3067번 - Coins (C++)  (0) 2023.08.18
[ 백준 ] 16965번 - 구간과 쿼리 (C++)  (0) 2023.08.17
[ 백준 ] 20007번 - 떡 돌리기 (C++)  (0) 2023.08.16
반응형

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

 

13537번: 수열과 쿼리 1

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/462

 

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)

1. 머지 소트 트리(Merge Sort Tree) 머지 소트 트리(Merge Sort Tree)는 분할 정복을 활용하는 합병 정렬(Merge Sort)을 저장하는 자료구조 입니다. 2. 머지 소트 트리(Merge Sort Tree) 동작 원리 머지 소트 트리(Me

rudalsd.tistory.com

 

1. 수열을 입력받고, 머지 소트 트리를 구현합니다.

 

2. 해당 구간에 대해 upper_bound를 활용하여, 해당 구간의 값 중 k보다 큰 값을 ans에 저장합니다.

 

3. 쿼리마다 ans를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> mergeSortTree[262222];
int arr[100001];
int ans;
 
void merge(int node, int s, int e) {
    int s_size = mergeSortTree[node * 2].size();
    int e_size = mergeSortTree[node * 2 + 1].size();
    int i = 0;
    int j = 0;
    while (1) {
        if (mergeSortTree[node * 2][i] < mergeSortTree[node * 2 + 1][j]) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i++]);
        }
        else {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j++]);
        }
 
        if (i == s_size || j == e_size) {
            break;
        }
    }
 
    if (i == s_size) {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
    else {
        for (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        mergeSortTree[node].push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    merge(node, s, e);
}
 
void getTree(int node, int s, int e, int i, int j, int k)
{
    if (e < i || j < s) return;
    if (i <= s && e <= j) {
        ans += mergeSortTree[node].end() - upper_bound(mergeSortTree[node].begin(), mergeSortTree[node].end(), k);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, i, j, k);
    getTree(node * 2 + 1, m + 1, e, i, j, k);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    cin >> M;
 
    for (int a = 0; a < M; a++) {
        int i, j, k;
        cin >> i >> j >> k;
        ans = 0;
 
        getTree(1, 1, N, i, j, k);
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
반응형

1. 머지 소트 트리(Merge Sort Tree)

 

머지 소트 트리(Merge Sort Tree)는 분할 정복을 활용하는 합병 정렬(Merge Sort)을 저장하는 자료구조 입니다.

 

2. 머지 소트 트리(Merge Sort Tree) 동작 원리

머지 소트 트리(Merge Sort Tree)는 각 노드에서 해당 노드에 포함된 모든 원소들을 정렬한 상태로 저장하는 트리입니다.

머지 소트 트리(Merge Sort Tree)는 아래와 같이 구성되어 있습니다.

 

1 2 3 4 5 6 7 8
1 2 5 6  3 4 7 8 
1 5 2 6 3 7 4 8
1 5 2 6 3 7 4 8

 

3. 머지 소트 트리(Merge Sort Tree) 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void merge(int node, int s, int e) {
    int s_size = mergeSortTree[node * 2].size();
    int e_size = mergeSortTree[node * 2 + 1].size();
    int i = 0;
    int j = 0;
    while (1) {
        if (mergeSortTree[node * 2][i] < mergeSortTree[node * 2 + 1][j]) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i++]);
        }
        else {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j++]);
        }
 
        if (i == s_size || j == e_size) {
            break;
        }
    }
 
    if (i == s_size) {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
    else {
        for (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        mergeSortTree[node].push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    merge(node, s, e);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'자료구조' 카테고리의 다른 글

[ 자료구조 ] 트라이(Trie)  (0) 2023.06.24
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)  (0) 2023.05.04
[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)  (0) 2023.01.16
[ 자료구조 ] 희소 배열(Sparse Table)  (0) 2022.08.07
[ 자료구조 ] 세그먼트 트리 (Segment Tree)  (0) 2022.07.02
반응형

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

 

2465번: 줄 세우기

첫째 줄에는 전체 사람의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에 사람들의 키를 나타내는 양의 정수가 하나씩 주어진다. 여기서 모든 키들은 2×109이하이다. 그리고 마지막 줄에 수열

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 키를 입력받고, map 자료구조를 활용해 각 키의 개수를 저장합니다.

 

2. 입력받은 키를 오름차순으로 정렬해 vector에 저장합니다.

 

3. vector의 인덱스를 기준으로 segment tree를 만듭니다.

 

4. 키의 순서를 N번째부터 1번째까지 돌면서 현재 남아있는 키 중에서 해당 정수 + 1만큼의 값을 가지고 있는 수를 ans 배열에 추가합니다.

 

5. ans 배열을 N번부터 1번까지 역으로 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<set>
#include<unordered_map>
#include<vector>
 
using namespace std;
 
int N;
int segTree[262222];
unordered_map<int, int> m;
set<int> se;
vector<int> arr;
vector<int> ans;
int seq[100000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] += m[arr[s]];
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
void updateTree(int node, int s, int e, int idx)
{
    segTree[node]--;
    if (s == e) {
        ans.push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    if (segTree[node * 2] >= idx) {
        updateTree(node * 2, s, m, idx);
    }
    else {
        updateTree(node * 2 + 1, m + 1, e, idx - segTree[node * 2]);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        se.insert(n);
        m[n]++;
    }
    
    arr.push_back(-1);
 
    for (auto& next : se) {
        arr.push_back(next);
    }
 
    makeTree(1, 1, arr.size() - 1);
 
    for (int i = 0; i < N; i++) {
        cin >> seq[i];
    }
 
    for (int i = N - 1; i >= 0; i--) {
        updateTree(1, 1, arr.size() - 1, seq[i] + 1);
    }
 
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
반응형

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

 

5012번: 불만 정렬

정렬 알고리즘의 상한(upper bound)은 n2이다. 이 사실은 쉽게 증명할 수 있다. 올바른 순서가 아닌 임의의 두 원소(ai > aj, i < j)를 선택하고, 그 위치를 서로 바꿔준다. 이렇게 올바른 순서가 아닌 것

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. arr배열에 수열을 입력받고, 0부터 n-1번까지 for문을 통해 돌면서 자신보다 큰 값을 gop에 저장합니다.

 

2. n-1부터 0까지 for문을 통해 돌면서 자신보다 작은 값을  gop에 곱합니다.

 

3. ans에 모든 gop의 값을 더한 후 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#define ll long long
 
using namespace std;
 
int n;
int segTree[200000];
int arr[100000];
ll gop[100000];
ll ans;
 
void updateTree(int idx)
{
    while (idx) {
        segTree[idx]++;
        idx >>= 1;
    }
}
 
int getTree(int l, int r)
{
    int ret = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            r--;
        }
        l >>= 1;
        r >>= 1;
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < n; i++) {
        gop[i] = getTree(n + arr[i], 2 * n - 1);
        updateTree(n + arr[i] - 1);
    }
 
    fill(segTree, segTree + 2 * n, 0);
 
    for (int i = n - 1; i >= 0; i--) {
        gop[i] *= getTree(n, n + arr[i] - 2);
        updateTree(n + arr[i] - 1);
        ans += gop[i];
    }
    
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 13537번 - 수열과 쿼리 1 (C++)  (0) 2023.08.08
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
반응형

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

 

17408번: 수열과 쿼리 24

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i < j ≤ r을 만족하는 모든 Ai + Aj 중에서

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 세그먼트 트리의 노드에 구간의 최댓값과 인덱스를 저장해 줍니다.

 

2. l부터 r까지의 인덱스 중 최댓값의 인덱스를 저장하고, l 부터 인덱스까지 와 인덱스 + 1 부터 r 까지의 값과 l부터 인덱스 -1 까지와 인덱스부터 r까지의 합 중 더 큰 값을 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
 
using namespace std;
 
int N, M;
pair<int,int> segTree[262222];
int arr[100001];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = { arr[s], s};
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    if (segTree[node*2].first > segTree[node*2+1].first) {
        segTree[node] = segTree[node * 2];
    }
    else {
        segTree[node] = segTree[node * 2 + 1];
    }
}
 
void updateTree(int node, int s, int e, int idx, int v)
{
    if (idx < s || e < idx) return;
    if (s == e) {
        segTree[node].first = v;
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, idx, v);
    updateTree(node * 2 + 1, m + 1, e, idx, v);
 
    if (segTree[node * 2].first > segTree[node * 2 + 1].first) {
        segTree[node] = segTree[node * 2];
    }
    else {
        segTree[node] = segTree[node * 2 + 1];
    }
}
 
pair<int,int> getTree(int node, int s, int e, int sidx, int eidx)
{
    if (e < sidx || s > eidx) return { 0,0 };
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    pair<int, int> left = getTree(node * 2, s, m, sidx, eidx);
    pair<int, int> right = getTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    if (left.first > right.first) {
        return left;
    }
    else {
        return right;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    cin >> M;
 
    for (int t = 0; t < M; t++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int i, v;
            cin >> i >> v;
            updateTree(1, 1, N, i, v);
        }
        else {
            int l, r;
            cin >> l >> r;
            int idx = getTree(1, 1, N, l, r).second;
 
            int ans = max(getTree(1, 1, N, l, idx).first + getTree(1, 1, N, idx + 1, r).first, getTree(1, 1, N, l, idx - 1).first + getTree(1, 1, N, idx, r).first);
            cout << ans << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
[ 백준 ] 16978번 - 수열과 쿼리 22 (C++)  (0) 2023.08.01

+ Recent posts

티스토리툴바