'PS(Problem Solving)/Segment Tree'에 해당되는 글 3건

  1. 2019.03.14 최솟값과 최댓값
  2. 2019.03.13 [BOJ]10868. 최솟값
  3. 2019.03.13 [BOJ]2042. 구간 합 구하기

최솟값과 최댓값

PS(Problem Solving)/Segment Tree
posted by 귀염둥이채원 2019. 3. 14. 19:50

# 문제링크

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


# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

- https://palyoung.tistory.com/64


# 풀이

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
public class BOJ2357 {
    static int N, M;
    static int a, b;
    static int arr[], segMinArr[], segMaxArr[];
 
    static void init(int N) {
        segMinArr = new int[N*4];
        segMaxArr = new int[N*4];
        Arrays.fill(segMinArr, Integer.MAX_VALUE);
        Arrays.fill(segMaxArr, Integer.MIN_VALUE);
    }
    
    static int createMinTree(int arr[], int left, int right, int node) {
        if (left == right) return segMinArr[node] = arr[left];
        int mid = (left+right)/2;
        return segMinArr[node] = Math.min(createMinTree(arr, left, mid, node*2), createMinTree(arr, mid+1, right, node*2+1));
    }
    
    static int getMinQuery(int left, int right, int node, int nodeLeft, int nodeRight) {
        if (left > nodeRight || right < nodeLeft) return Integer.MAX_VALUE;
        if (left <= nodeLeft && right >= nodeRight) return segMinArr[node];
        int mid = (nodeLeft+nodeRight)/2;
        return Math.min(getMinQuery(left, right, node*2, nodeLeft, mid), getMinQuery(left, right, node*2+1, mid+1, nodeRight));
    }
    
    static int createMaxTree(int arr[], int left, int right, int node) {
        if (left == right) return segMaxArr[node] = arr[left];
        int mid = (left+right)/2;
        return segMaxArr[node] = Math.max(createMaxTree(arr, left, mid, node*2), createMaxTree(arr, mid+1, right, node*2+1));
    }
    
    static int getMaxQuery(int left, int right, int node, int nodeLeft, int nodeRight) {
        if (left > nodeRight || right < nodeLeft) return Integer.MIN_VALUE;
        if (left <= nodeLeft && right >= nodeRight) return segMaxArr[node];
        int mid = (nodeLeft+nodeRight)/2;
        return Math.max(getMaxQuery(left, right, node*2, nodeLeft, mid), getMaxQuery(left, right, node*2+1, mid+1, nodeRight));
    }
    
    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        init(N);
        createMinTree(arr, 0, N-1, 1);
        createMaxTree(arr, 0, N-1, 1);
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken())-1;
            b = Integer.parseInt(st.nextToken())-1;
            
            sb.append(getMinQuery(a, b, 1, 0, N-1) + " " +getMaxQuery(a, b, 1, 0, N-1) + "\n");
        }
        System.out.println(sb.toString());
    }
}
cs


'PS(Problem Solving) > Segment Tree' 카테고리의 다른 글

[BOJ]10868. 최솟값  (0) 2019.03.13
[BOJ]2042. 구간 합 구하기  (0) 2019.03.13

[BOJ]10868. 최솟값

PS(Problem Solving)/Segment Tree
posted by 귀염둥이채원 2019. 3. 13. 21:28

# 문제링크

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


# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

- https://palyoung.tistory.com/64


# 풀이

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
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BOJ10868 {
    static int arr[];
    static int N, M;
    static int a, b;
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder("");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        SegmentTree segObj = new SegmentTree(arr, N);
        //segObj.print();
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            sb.append(segObj.query(a-1, b-1, 1, 0, N-1) + "\n");
        }
        System.out.println(sb);
    }
}
 
class SegmentTree {
    long segmentArr[];
    
    SegmentTree(int arr[], int N){
        segmentArr = new long[N*4];
        Arrays.fill(segmentArr, Integer.MAX_VALUE);
        init(arr, 0, N-1, 1);
    }
    
    long init(int arr[], int left, int right, int node) {
        if (left == right) return segmentArr[node] = arr[left];
        int mid = (left+right)/2;
        return segmentArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));
    }
 
    long query(int sIdx, int eIdx, int node, int nodeLeft, int nodeRight) {
        if (sIdx > nodeRight || eIdx < nodeLeft) return Integer.MAX_VALUE;
        if (sIdx <= nodeLeft && eIdx >= nodeRight) return segmentArr[node];
        int mid = (nodeLeft + nodeRight)/2;
        return Math.min(query(sIdx, eIdx, node*2, nodeLeft, mid), query(sIdx, eIdx, node*2+1, mid+1, nodeRight)); 
    }
    
    void print() {
        for (int i=0; i<segmentArr.length; i++) {
            System.out.printf("%d, ", segmentArr[i]);
        }
        System.out.println();
    }
}
cs


# 회고

- segment tree 생성시 segmentArr에 초기값을 MAX로 설정해야한다.

  - Arrays.fill(segmentArr, Integer.MAX_VALUE);


- 자식이 있는 "부모노드"는 자식 노드들의 최솟값을 가지고 있어야 한다.

  - segmentArr[node] = Math.min(init(arr, left, mid, node*2), init(arr, mid+1, right, node*2+1));

'PS(Problem Solving) > Segment Tree' 카테고리의 다른 글

최솟값과 최댓값  (0) 2019.03.14
[BOJ]2042. 구간 합 구하기  (0) 2019.03.13

[BOJ]2042. 구간 합 구하기

PS(Problem Solving)/Segment Tree
posted by 귀염둥이채원 2019. 3. 13. 16:55

# 문제링크

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


# 알고리즘

- Segment Tree를 사용해서 풀어야 한다.

- https://palyoung.tistory.com/64


# 풀이

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
package segment;
 
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int N, M, K;
    static int arr[];
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src\\sample.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N];
        int a=0, b=0, c=0;
        
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        SegmentTree seg = new SegmentTree(arr, N);
        //seg.print();
        
        for (int i=0; i<M+K; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            
            // segment tree 업데이트
            if (a == 1) {
                seg.update(b-1, c, 1, 0, N-1);
            }
            // segment tree에서 구간의 합 
            else if (a == 2) {
                sb.append(seg.query(b-1, c-1, 1, 0, N-1)+"\n");
            }
        }
        System.out.println(sb);
    }
}
 
class SegmentTree {
    long SegmentTreeArr[];    // segment tree node 데이터
    
    SegmentTree(int arr[], int N) {
        SegmentTreeArr = new long[N*4];
        init(arr, 0, N-1, 1);
    }
    
    // Leaf Node가 N개인 Segment Tree 생성
    // node 의 왼쪽 자식은 node*2, 오른쪽 자식은 node*2+1
    long init(int arr[], int left, int right, int node) {
        // node가 리프 노드인 경우
        if (left == right) return SegmentTreeArr[node] = arr[left];
        int mid = (left+right)/2;
        return SegmentTreeArr[node] = init(arr, left, mid, node*2) + init(arr, mid+1, right, node*2+1);
    }
    
    // Segment Tree를 갱신하고 노드 구간의 합을 구한다.
    long update(int index, int value, int node, int nodeLeft, int nodeRight) {
        // index가 Node 구간에 포함되지 않는 경우
        if (index < nodeLeft || index > nodeRight) return SegmentTreeArr[node];
        
        // node가 리프 노드인 경우
        if (nodeLeft == nodeRight)  return SegmentTreeArr[node] = value; 
        
        int mid = (nodeLeft + nodeRight)/2;
        return SegmentTreeArr[node] = update(index, value, node*2, nodeLeft, mid) + update(index, value, node*2+1, mid+1, nodeRight); 
    }
    
    // Segment Tree의 구간 합을 구한다.
    long query(int left, int right, int node, int nodeLeft, int nodeRight) {
        // 두 구간이 겹치지 않는 경우
        if (left > nodeRight || right < nodeLeft) return 0;
        
        // [left, right]가 [nodeLeft, nodeRight]를 포함하는 경우
        if (left <= nodeLeft && right >= nodeRight) return SegmentTreeArr[node];
        
        int mid = (nodeLeft + nodeRight)/2;
        return query(left, right, node*2, nodeLeft, mid) + query(left, right, node*2+1, mid+1, nodeRight); 
    }
    
    void print() {
        for (int i=0; i<SegmentTreeArr.length; i++) {
            System.out.printf("%d, ", SegmentTreeArr[i]);
        }
        System.out.println();
    }
}
cs


'PS(Problem Solving) > Segment Tree' 카테고리의 다른 글

최솟값과 최댓값  (0) 2019.03.14
[BOJ]10868. 최솟값  (0) 2019.03.13

티스토리툴바