반응형

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

 

10868번: 최솟값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 최솟값을 구해야 하므로 왼쪽 노드와 오른쪽 노드 중 더 작은 값을 return 해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[100001];
int segTree[263000];
 
int makeTree(int node, int start, int end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);
    int right = makeTree(node * 2 + 1, mid + 1, end);
 
    if (left < right) {
        return segTree[node] = left;
    }
    else {
        return segTree[node] = right;
    }
}
 
int getTree(int node, int start, int end, int sidx, int eidx)
{
    if (end < sidx || start > eidx) return 1987654321;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    int left = getTree(node * 2, start, mid, sidx, eidx);
    int right = getTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    if (left < right) {
        return left;
    }
    else {
        return right;
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        printf("%d\n", getTree(1, 1, N, a, b));
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 17141번 - 연구소 2 (C++)  (0) 2023.01.06
[ 백준 ] 1275번 - 커피숍2 (C++)  (0) 2023.01.05
[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
반응형

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

 

3176번: 도로 네트워크

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/95?category=1073064 

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까

rudalsd.tistory.com

 

1. 희소 배열의 각 노드에 max, min 값을 각각 저장해줍니다.

 

2. 두 노드의 높이를 맞춰줄 때 Max, Min을 계속 갱신해줍니다.

 

3. Min과 Max를 출력해줍니다.

 

[ 소스 코드 ]

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<cstdio>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int to;
    int max;
    int min;
};
 
int N, K;
int H;        //트리의 높이
node arr[100001][18];
vector<vector<node>> list;
int visited[100001];
int h[100001];    //노드의 높이
 
void dfs(int cur)    //arr[cur][0] 채우기
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur])
    {
        if (visited[next.to] != 1) {
            arr[next.to][0] = { cur, next.max, next.min };
            h[next.to] = h[cur] + 1;
            dfs(next.to);
        }
    }
}
 
void makeTree()        //트리 만들기
{
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= N; j++) {
            auto next = arr[j][i - 1];
            if (arr[next.to][i-1].to != 0) {
                int Max = max(next.max, arr[next.to][i - 1].max);
                int Min = min(next.min, arr[next.to][i - 1].min);
                arr[j][i] = { arr[next.to][i - 1].to, Max, Min };
            }
        }
    }
}
 
void Dist(int a, int b)    //a, b 사이의 가장 긴 도로와 짧은 도로 길이 구하기
{
    if (h[a] > h[b]) {    //a가 트리의 더 위에 있도록
        int temp = a;
        a = b;
        b = temp;
    }
 
    int Min = 987654321;
    int Max = 0;
 
    if (h[a] != h[b]) {    //높이가 다르다면 맞춰주기
        for (int i = H; i >= 0; i--) {
            int mask = 1 << i;
            if (h[b] - h[a] >= mask) {
                Min = min(Min, arr[b][i].min);
                Max = max(Max, arr[b][i].max);
                b = arr[b][i].to;
            }
            if (h[a] == h[b]) break;
        }
    }
 
    if(a!=b) {    //같은 높이일 때 서로 다른 숫자면
        for (int i = H; i >= 0; i--) {
            if (arr[a][i].to == arr[b][i].to || arr[a][i].to == 0 || arr[b][i].to == 0) continue;
            Max = max(Max, max(arr[a][i].max,arr[b][i].max));
            Min = min(Min, min(arr[a][i].min, arr[b][i].min));
            a = arr[a][i].to;
            b = arr[b][i].to;
        }
 
        Max = max(Max, max(arr[a][0].max, arr[b][0].max));
        Min = min(Min, min(arr[a][0].min, arr[b][0].min));
    }
 
    printf("%d %d\n", Min, Max);
}
 
int main()
{
    scanf("%d", &N);
 
    H = ceil(log2(N));
    list.resize(N + 1);
    h[1] = 1;
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, dist;
        scanf("%d %d %d", &a, &b, &dist);
 
        list[a].push_back({ b,dist,dist });
        list[b].push_back({ a,dist,dist });
    }
 
    dfs(1);
    makeTree();
 
    scanf("%d", &K);
 
    for (int i = 0; i < K; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        Dist(a, b);
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
[ 백준 ] 11286번 - 절댓값 힙 (C++)  (0) 2022.08.23
[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20
[ 백준 ] 11047번 - 동전 0 (C++)  (0) 2022.08.19
반응형

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

 

14942번: 개미

자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너

www.acmicpc.net

 

 

[ 문제풀이 ]

 

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

https://rudalsd.tistory.com/95?category=1073064 

 

[ 자료구조 ] 희소 배열(Sparse Table)

1. 희소 배열(Sparse Table) - 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 - 희소 배열은 배열의 원소 위치가 연속적이지 않은 배열 2. 희소 배열 만들기 보통 5번 노드에서 1번 노드까

rudalsd.tistory.com

 

1. 희소 배열을 이용하여 n번 이동했을 때의 노드와 거리를 저장

 

2. n번 이동했을 때 거리가 현재 가지고 있는 에너지보다 작다면 이동

 

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
struct node {
    int to;
    int dist;
};
 
int n;
int energy[100001];
vector<node> list[100001];
int visited[100001];
int arr[100001][17];
int dist[100001][17];
int H;
 
void dfs(int cur)    //그래프 그리기
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next.to] == 1) continue;
        arr[next.to][0] = cur;
        dist[next.to][0] = next.dist;
        dfs(next.to);
    }
}
 
void makeTree()        //트리 만들기
{
    for (int i = 1; i < H; i++) {        //순서 중요!!!
        for (int j = 2; j <= n; j++) {
            int next = arr[j][i - 1];
            if (arr[next][i - 1] == 0) continue;
            arr[j][i] = arr[next][i - 1];
            dist[j][i] = dist[next][i - 1] + dist[j][i-1];
        }
    }
}
 
int getRomm(int cur)    //최종 도달 방 찾기
{
    int ret = cur;
    int E = energy[cur];
    for (int i = H - 1; i >= 0; i--) {
        if (arr[ret][i] != 0 && dist[ret][i] <= E) {
            E -= dist[ret][i];        //순서 중요!!!
            ret = arr[ret][i];
        }
        if (ret == 1 || E == 0) break;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &n);
    H = ceil(log2(n));
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &energy[i]);
    }
 
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        list[a].push_back({ b,c });
        list[b].push_back({ a,c });
    }
 
    dfs(1);
 
    makeTree();
 
    for (int i = 1; i <= n; i++) {
        printf("%d\n", getRomm(i));
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 17401번 - 일하는 세포 (C++)  (0) 2022.08.10
[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07
[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
반응형

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

 

11438번: LCA 2

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정

www.acmicpc.net

 

 

[ 문제풀이 ]

 

다음 글의 두 번째 풀이 방식과 동일합니다!

https://rudalsd.tistory.com/68?category=1064612 

 

[ 백준 ] 1761번 - 정점들의 거리 (C++)

https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄

rudalsd.tistory.com

 

[ 소스 코드 ]

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<cmath>
 
using namespace std;
 
int N, M;
vector<int> list[100001];    //간선 정보
int parent[100001][18];        //2^i번째 부모
int height[100001];            //각 노드의 높이
int visited[100001];        //방문 여부
int limit;
 
void dfs(int cur)        //그래프
{
    if (visited[cur] == 1) return;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next] == 0) {
            height[next] = height[cur] + 1;
            parent[next][0] = cur;
            dfs(next);
        }
    }
}
 
int find(int a, int b)        //LCA 찾기
{
    if (height[a] > height[b]) {    //a가 루트에 더 가깝게
        int temp = a;
        a = b;
        b = temp;
    }
 
    for (int i = limit; i >= 0; i--) {    //높이 맞추기
        int mask = 1 << i;
        if (height[b] - height[a] >= mask) {
            b = parent[b][i];
        }
    }
 
    if (a == b) return a;    //같은 노드라면 a return
 
    for (int i = limit; i >= 0; i--) {        //같인 부모 찾기
        if (parent[a][i] == parent[b][i]) continue;
 
        a = parent[a][i];
        b = parent[b][i];
    }
    
    return parent[a][0];
}
 
int main()
{
    scanf("%d", &N);
 
    limit = ceil(log2(N));
 
    for (int i = 0; i < N - 1; i++) {    //간선 정보 얻기
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    dfs(1);
 
    for (int i = 1; i < limit; i++) {    //parent배열 채우기
        for (int j = 1; j <= N; j++) {
            int next = parent[j][i - 1];
            if (next != 0) {
                parent[j][i] = parent[next][i - 1];
            }
        }
    }
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        printf("%d\n", find(a, b));
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 16287번 - Parcel (C++)  (0) 2022.08.06
[ 백준 ] 10026번 - 적록색약 (C++)  (0) 2022.08.05
[ 백준 ] 1725번 - 히스토그램 (C++)  (0) 2022.08.03
[ 백준 ] 6549번 - 히스토그램에서 가장 큰 직사각형 (C++)  (0) 2022.08.02
[ 백준 ] 1629번 - 곱셈 (C++)  (0) 2022.08.01

+ Recent posts

티스토리툴바