반응형

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

 

7511번: 소셜 네트워킹 어플리케이션

각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 친구 관계를 이어주고, 부모 노드의 값이 같다면 1, 아니라면 0을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int n, k, m;
int vect[1000001];
 
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()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 1; t <= T; t++) {
        scanf("%d", &n);
 
        for (int i = 1; i <= n; i++) {
            vect[i] = i;
        }
 
        scanf("%d", &k);
 
        for (int i = 0; i < k; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
 
            Union(a, b);
        }
 
        scanf("%d", &m);
 
        printf("Scenario %d:\n", t);
 
        for (int i = 0; i < m; i++) {
            int a, b;
            scanf("%d %d", &a, &b);
 
            if (Find(a) != Find(b)) {
                printf("0\n");
            }
            else {
                printf("1\n");
            }
        }
 
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14595번 - 동방 프로젝트 (Large) (C++)  (0) 2023.06.01
[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
[ 백준 ] 18116번 - 로봇 조립 (C++)  (0) 2023.05.27
반응형

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

 

17352번: 여러분의 다리가 되어 드리겠습니다!

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다. 어제까지는 그랬다. "왜 다리

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 다리를 이어주고, 부모 노드의 값이 1과 다른 다리를 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
#include<iostream>
 
using namespace std;
 
int N;
int vect[300001];
 
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()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 0; i < N - 2; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (Find(a) != Find(b)) {
            Union(a, b);
        }
    }
 
    for (int i = 2; i <= N; i++) {
        if (Find(1) != Find(i)) {
            printf("1 %d", i);
            return 0;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20955번 - 민서의 응급 수술 (C++)  (0) 2023.05.31
[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
[ 백준 ] 18116번 - 로봇 조립 (C++)  (0) 2023.05.27
[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
반응형

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

 

12899번: 데이터 구조

첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 쿼리 업데이트를 통해 해당 자연수 노드에 1을 더해주고, 구간 합을 세그먼트 트리를 이용하여 구현해 줍니다.

 

2. 왼쪽 노드의 값이 원하는 인덱스의 값보다 크다면 왼쪽 노드로 들어가고, 그렇지 않다면 인덱스의 값에 왼쪽 노드의 값을 뺀 값을 이용하여 오른쪽 노드로 들어가 줍니다.

 

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
#include<iostream>
 
using namespace std;
 
int N;
int segTree[4200000];
 
void updateTree(int node, int s, int e, int idx)
{
    if (idx < s || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx);
        updateTree(node * 2 + 1, m + 1, e, idx);
    }
}
 
void getTree(int node, int s, int e, int idx)
{
    if (s == e) {
        printf("%d\n", s);
        segTree[node]--;
        return;
    }
 
    int m = (s + e) / 2;
 
    if (segTree[node * 2] >= idx) {
        getTree(node * 2, s, m, idx);
        segTree[node]--;
    }
    else {
        getTree(node * 2 + 1, m + 1, e, idx - segTree[node*2]);
        segTree[node]--;
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int cmd, X;
        scanf("%d %d", &cmd, &X);
 
        if (cmd == 1) {
            updateTree(1, 1, 2000000, X);
        }
        else {
            getTree(1, 1, 2000000, X);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7511번 - 소셜 네트워킹 어플리케이션 (C++)  (0) 2023.05.30
[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
[ 백준 ] 18116번 - 로봇 조립 (C++)  (0) 2023.05.27
[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
반응형

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

 

18116번: 로봇 조립

성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 관계된 친구들의 수를 저장할 cnt 배열과 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. cnt 배열을 모두 1로 초기화하고, vect[ i ] = i 로 초기화합니다.

 

3. Union-Find를 활용하여 친구들의 관계를 이어주고, 부모 노드의 cnt 배열의 값을 더해주고, 이를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int vect[1000001];
int cnt[1000001];
 
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;
    cnt[pa] += cnt[pb];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
    
    for (int i = 1; i < 1000001; i++) {
        vect[i] = i;
        cnt[i] = 1;
    }
 
    for (int i = 0; i < N; i++) {
        char cmd;
        cin >> cmd;
 
        if (cmd == 'I') {
            int a, b;
            cin >> a >> b;
            if (Find(a) != Find(b)) {
                Union(a, b);
            }
        }
        else {
            int a;
            cin >> a;
 
            cout << cnt[Find(a)] << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17352번 - 여러분의 다리가 되어 드리겠습니다! (C++)  (0) 2023.05.29
[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
반응형

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

 

11376번: 열혈강호 2

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고,

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/384

 

[ 알고리즘 ] 이분 매칭(Bipartite Matching)

1. 이분 매칭(Bipartite Matching)이란? 정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 이분 그래프(Bipartite Graph)라고 말합니다.

rudalsd.tistory.com

 

1. 한 명이 총 2개의 일을 할 수 있으므로 N * 2의 범위까지 사람을 늘리고, i * 2 와 i * 2 - 1 을 한 사람으로 생각하고 문제를 풉니다.

 

2. 이분 매칭을 이용하여 매칭이 될 때마다 ans에 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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
vector<int> list[2001];
int visited[2001];
int work[1001];
int cnt;
 
bool dfs(int cur)
{
    if (visited[cur] == cnt) return false;
    visited[cur] = cnt;
 
    for (int& next : list[cur]) {
        if (!work[next] || dfs(work[next])) {
            work[next] = cur;
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        int n;
        scanf("%d", &n);
 
        for (int j = 0; j < n; j++) {
            int m;
            scanf("%d", &m);
 
            list[i * 2].push_back(m);
            list[i * 2 - 1].push_back(m);
        }
    }
 
    int ans = 0;
 
    for (int i = 1; i <= N * 2; i++) {
        cnt++;
        if(dfs(i)) ans++;
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12899번 - 데이터 구조 (C++)  (0) 2023.05.28
[ 백준 ] 18116번 - 로봇 조립 (C++)  (0) 2023.05.27
[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
반응형

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

 

11375번: 열혈강호

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/384

 

[ 알고리즘 ] 이분 매칭(Bipartite Matching)

1. 이분 매칭(Bipartite Matching)이란? 정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 이분 그래프(Bipartite Graph)라고 말합니다.

rudalsd.tistory.com

 

1. 이분 매칭을 이용하여 매칭이 될 때마다 ans에 1을 더해줍니다.

 

2. 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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
vector<int> list[1001];
int visited[1001];
int m[1001];
 
bool dfs(int cur)
{
    if (visited[cur]) return false;
    visited[cur] = 1;
 
    for (int& next : list[cur]) {
        if (!m[next] || dfs(m[next])) {
            m[next] = cur;
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        int n;
        scanf("%d", &n);
 
        for (int j = 0; j < n; j++) {
            int a;
            scanf("%d", &a);
            list[i].push_back(a);
        }
    }
 
    int ret = 0;
 
    for (int i = 1; i <= N; i++) {
        fill(visited, visited + N + 1, 0);
        if (dfs(i)) ret++;
    }
 
    printf("%d", ret);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 18116번 - 로봇 조립 (C++)  (0) 2023.05.27
[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
반응형

1. 이분 매칭(Bipartite Matching)이란?

 

정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 이분 그래프(Bipartite Graph)라고 말합니다. 이러한 이분 그래프에서 예를 들어, 한쪽 그룹은 X 그룹, 다른 한쪽 그룹은 Y 그룹이라고 할 때 모든 경로의 방향이 X->Y인 그래프의 최대 유량을 구하는 것이 이분 매칭(Bipartite Matching)입니다.

 

2. 이분 매칭(Bipartite Matching)동작 원리

 

 

우선, 정점 A는 정점 1을 점유할 수 있습니다. (총 매칭 수 : 1)

 

 

그 다음 정점 B는 정점 1을 점유하려고 합니다. 그런데 정점 A가 이미 정점 1을 보유하고 있으므로 A는 다른 정점을 점유하러 경로를 다시 찾습니다. 정점 3이 비어있으므로 A는 정점 3을 점유합니다. (총 매칭 수 : 2)

 

 

정점 C는 정점 5를 점유합니다. (총 매칭 수 : 3)

 

 

정점 D는 정점 3을 점유하려고 합니다. 그런데 정점 A가 이미 정점 3을 점유하고 있으므로 A가 다른 경로를 찾아 정점 1의 점유를 시도합니다. 그런데 정점 1 역시 정점 B가 점유하고 있으므로 B는 다른 경로를 찾아 비어있던 정점 2를 점유합니다. (총 매칭 수 : 4)

 

 

정점 E가 정점 2를 점유하려고 합니다. 그러나 정점 E는 더이상 매칭할 수 없습니다. 2를 점유하면 B가 경로를 다시 찾을 것이고 또 A가 다시 경로를 찾게되며 또 D가 다시 경로를 찾고 계속해서 반복되기 때문에 매칭이 불가능합니다.

 

따라서 최종 매칭 수는 4가 됩니다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[ 알고리즘 ] 뤼카의 정리 (Lucas' theorem)  (0) 2023.07.03
[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)  (0) 2022.10.24
[ 알고리즘 ] 단절선(Articulation Bridge)  (0) 2022.08.28
[ 알고리즘 ] 단절점(Articulation Point)  (0) 2022.08.26
[ 알고리즘 ] 강한 연결 요소 추출 알고리즘(Strongly Connected Component)  (0) 2022.07.23
반응형

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

 

2934번: LRH 식물

상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 상근이는 매일 매일 화단에

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 느리게 갱신되는 세그먼트 트리를 이용하여 L + 1 부터 R - 1 까지 1을 더해주고, L노드와 R노드의 값에 이전에 핀 꽃의 개수인 cnt[ L ] + cnt[ R ]의 값을 빼고, 그 값을 출력합니다.

 

2. cnt[ L ]의 값과 cnt[ 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
#include<iostream>
 
using namespace std;
 
int N;
int segTree[262222];
int lazy[262222];
int cnt[100001];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        segTree[node] += lazy[node];
 
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node]++;
 
        if (s != e) {
            lazy[node * 2]++;
            lazy[node * 2 + 1]++;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
int getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (s > idx || e < idx) return 0;
    if (s == e) return segTree[node];
 
    int m = (s + e) / 2;
    int left = getTree(node * 2, s, m, idx);
    int right = getTree(node * 2 + 1, m + 1, e, idx);
 
    return  left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int L, R;
        scanf("%d %d", &L, &R);
 
        if (L + 1 <= R - 1) {
            updateTree(1, 1, 100000, L + 1, R - 1);
        }
 
        int tempL = getTree(1, 1, 100000, L);
        int tempR = getTree(1, 1, 100000, R);
 
        printf("%d\n", tempL + tempR - cnt[L] - cnt[R]);
 
        cnt[L] = tempL;
        cnt[R] = tempR;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
반응형

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

 

14245번: XOR

첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 초기 배열을 arr 배열에 저장합니다.

 

2. segmentTree의 리프 노드에 arr 배열의 값들을 넣습니다.

 

3. 느리게 갱신되는 세그먼트 트리를 이용하여 lazy 배열의 값들에 XOR한 값을 저장합니다.

 

4. 해당 쿼리를 출력합니다.

 

[ 소스코드 ]

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;
int segTree[1050000];
int lazy[1050000];
int arr[500000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr[s];
        return;
    }
 
    int m = (s + e)/2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
}
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        segTree[node] ^= lazy[node];
 
        if (s != e) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int a)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node] ^= a;
        if (s != e) {
            lazy[node * 2] ^= a;
            lazy[node * 2 + 1] ^= a;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, a);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, a);
}
 
void getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (idx < s || e < idx) return;
    if (s == e) {
        printf("%d\n", segTree[node]);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, idx);
    getTree(node * 2 + 1, m + 1, e, idx);
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 0, n - 1);
 
    scanf("%d", &m);
 
    for (int i = 0; i < m; i++) {
        int cmd;
        scanf("%d", &cmd);
 
        if (cmd == 1) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
 
            updateTree(1, 0, n - 1, a, b, c);
        }
        else {
            int a;
            scanf("%d", &a);
 
            getTree(1, 0, n - 1, a);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
반응형

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

 

3006번: 터보소트

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

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

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

rudalsd.tistory.com

 

1. segmentTree의 리프노드를 모두 1로 채우고 나머지 노드들을 구간합으로 채워줍니다.

 

2. 배열을 입력 받고, 각 수의 위치를 arr 배열에 저장합니다.

 

3. 1부터 N까지 번갈아가며 홀수번째 단계에서는 0 ~ arr[ i ] - 1까지의 구간합을 출력하고, 짝수번째 단계에서는 arr[ i ] + 1 ~ 2N - 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
#include<iostream>
 
using namespace std;
 
int N;
int arr[100001];
int segTree[200000];
 
void updateTree(int idx, int k)
{
    while (idx != 0) {
        segTree[idx] += k;
        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()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int n;
        scanf("%d", &n);
        updateTree(N + i, 1);
 
        arr[n] = i;
    }
 
    int L = 1;
    int R = N;
    int cnt = 1;
 
    while (L <= R) {
        if (cnt & 1) {
            printf("%d\n", getTree(N, N + arr[L]) - 1);
            updateTree(N + arr[L], -1);
            L++;
        }
        else {
            printf("%d\n", getTree(N + arr[R], 2 * N - 1) - 1);
            updateTree(N + arr[R], -1);
            R--;
        }
        cnt++;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
[ 백준 ] 17612번 - 쇼핑몰 (C++)  (0) 2023.05.18

+ Recent posts

티스토리툴바