'전체 글'에 해당되는 글 120건

  1. 2019.03.14 최솟값과 최댓값
  2. 2019.03.13 [BOJ]10868. 최솟값
  3. 2019.03.13 Segment Tree (구간 트리) ---- (작성중,,,,,)

최솟값과 최댓값

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

Segment Tree (구간 트리) ---- (작성중,,,,,)

알고리즘
posted by 귀염둥이채원 2019. 3. 13. 18:32

Segment Tree (구간 트리)는 일차원 배열에서 각각의 구간을 특정 기준으로 질의를 던지고 빠르게 답을 구할 수 있는 알고리즘이다.


# Segment Tree

- 이진 트리를 통해 표현 (대부분 full binary tree)

- 각 노드에는 구간에 대한 정보가 저장이 되어있는 트리

  - 자식이 있는 "부모노드"는 구간에 대한 정보를 가지고 있다.

  - 자식이 없는 "리프노드"는 하나의 정보만 가지고 있다.


# Segment Tree 유형 문제

- 하나의 (또는 연속된 구간) 값이 매번 변경되는 데이터의 구간합

- 하나의 값이 매번 변경되는 데이터의 최소값

- 하나의 값이 매번 변경되는 데이터의 최대값

- 하나의 값이 빈번히 변경되는 데이터의, 구간 정렬 값


# Segment Tree를 사용하는 이유?

배열 arr에 1,2,3,4,5가 있다고 하자.

arr[1]+arr[2]+arr[3]=9를 구하려면 O(N)이 걸린다.


arr[2]를 10으로 바꾸고 다시 arr[1]+arr[2]+arr[3]를 구해야한다면,

값을 바꾸는데 O(1), 구간의 합을 구하는데 O(N)이 걸린다.

M번 실행하게 되면 O(MN+M)의 시간이 걸린다.


Segment Tree를 사용하면,

값을 바꾸는 과정: O(lgN)

구간의 합을 구하는 과정: O(lgN)

M번 실행 O(MlgN + MlgN) -> O(MlgN)의 시간이 걸린다.


M = 100, N = 2^20이라고 가정하면

O(MN)에서는 100*2^20 = 10,000,000(대략)

O(MlgN)에서는 100*20 = 2,000으로 데이터와 반복수행이 잦아질수록 시간 복잡도 차이가 기하급수적으로 커진다.



※ 그림 추가 (세그먼트 트리 모양)



# Segment Tree의 전체 크기 구하기

N = 12일 때의 세그먼트 트리의 전체 크기(배열 사이즈 정하기)를 구하기 위해서는 

2^k로 12보다 바로 큰 값을 만들 수 있는 k를 찾아야한다. 

즉, k는 4이다.


그리고 난 뒤 2^k를 하면 16이 되고 16에 *2를 하면 우리가 원하는 세그먼트 트리의 크기를 구할 수 있다. 

이 과정이 귀찮다면 그냥 N * 4를하면(여기서는 48이 세그먼트 트리 크기가 될 것이다.)

메모리는 조금 더 먹지만, 편리하게 이용할 수 있다.


포인터로 동적할당을 통한 트리가 아닌 배열로 트리를 만들고 있다.

그 이유는 세그먼트 트리는 full binary tree에 가깝기에 배열에 모든 값들이 꽉꽉차서 올 가능성이 매우 높기때문에 포인터보다는 배열을 이용하게 된다.


# 초기화

구간의 합 또는 최대 그리고 최소값이든 특정 기준에 따라 구간의 값을 지정해주기 위해 트리를 만드는 과정이다.


# 질의처리

주어진 구간 트리에서 원하는 구간의 값을 물어볼때 답을 얻는 과정이다.


# 업데이트

일차원 배열의 값이 변경되는 경우이다.

배열의 특정 index의 값이 변경되면 구간 트리의 값도 변경된다.

하지만 변화의 차이 값을 가지고 루트부터 탐색하면 O(logN)으로 갱신이 가능하다.


# 관련 문제

[BOJ]2042번 구간 합 구하기

[BOJ]2357번 최대값,최소값


# 유투브 영상

https://www.youtube.com/watch?v=e6xnetirNN0&list=PLQ9c2GXvqNKyqrihVgiDJ0upU0pGyqUJy&index=5


# 참고 사이트

https://www.acmicpc.net/blog/view/9

https://www.crocus.co.kr/648

https://meylady.tistory.com/38

https://wondy1128.tistory.com/150

https://jin1ib.tistory.com/116

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

Parametric Search(파라메트릭 서치) 알고리즘 개념  (0) 2019.02.28
시간복잡도(Time Complexity), 빅오(Big-O)표기법이란?  (0) 2019.02.28
이진 탐색(Binary Search) 알고리즘 개념 및 예제 소스  (0) 2019.02.27

티스토리툴바