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

Parametric Search(파라메트릭 서치) 알고리즘 개념

알고리즘
posted by 귀염둥이채원 2019. 2. 28. 18:28

# Parametric Search(파라메트릭 서치) 알고리즘 개념

- Binary Search를 응용한 방법으로 기본적인 탐색 방법은 Binary Search와 비슷함

- 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것

- 원하는 조건을 만족하는 가장 알맞는 값을 특정한 오차범위 이내에서 알고싶은 경우 사용

- 임의의 값으로 계산 후 확인해가며 해를 구하는 방법 (Binary Search 사용)


# Binary Search vs Parametric Search

Binary Search: 배열에서 중앙값(middle)이 가리키는 값이 내가 찾는 값인지 중요

Parametric Search:  원하는 조건을 만족하는 가장 알맞는 값을 찾는 것


# 시간복잡도

Binary Search와 마찬가지로 O(logN)의 복잡도를 가지게 된다.


# Parametric Search를 사용할수 있는 조건

1) 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우

2) (최소값을 구하는 경우) 최소값이 x라면, x이상의 값에 대해서는 모두 조건을 만족

3) (최대값을 구하는 경우) 최대값이 x라면, x이하의 값에 대해서는 모두 조건을 만족


# 참고사항

* 데이터는 정렬된 상태이면 좋지만, 정렬되지 않은 경우도 사용가능하다.

   - 데이터가 정렬되지 않은 경우에는 중간값을 설정 기준이 중요하다?? 

     (목적에 맞게 조건을 설정하는 것이 중요)


# SWEA 샘플 코드

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
import java.io.FileInputStream;
import java.util.Scanner;
 
public class ParametricSearch {
    static int K;
    static int N;
    static int low;             // 리본의 최소 길이
    static int high;            // 리본의 최대 길이
    static int mid;             // 리본의 중간 길이
    static int numRibbon;       // 중간 길이로 자른 경우 리본의 개수
    static int Answer;          // 리본의 최대 길이
    static int sizeRibbon[];    // K개 리본의 길이
 
    static void search() {
        // 중간 값을 구하기
        mid = low + (high - low) / 2;
        numRibbon = 0;
        // System.out.printf("[Before] low:%5d, mid=%5d, high=%5d, (high-low)/2=%5d,
        // numRibbon=%5d, Answer=%5d\n",
        // low, mid, high, (high-low)/2, numRibbon, Answer);
 
        // 중간값으로 나눠서 리본 개수를 구하기
        for (int i = 0; i < K; i++) {
            numRibbon += (sizeRibbon[i] / mid);
        }
 
        // 필요한 리본개수보다 같거나 많은 경우
        // - 리본의 최소 길이 = 중간길이 + 1
        // - 중간길이 > 현재 최대 길이
        // - 최대 길이로 설정
        // 필요한 리본개수보다 적은 경우
        // - 리본의 최대 길이 = 중간 길이 - 1
        if (numRibbon >= N) {
            low = mid + 1;
            if (Answer < mid)
                Answer = mid;
        } else {
            high = mid - 1;
        }
 
        // System.out.printf("[After ] low:%5d, mid=%5d, high=%5d, (high-low)/2=%5d,
        // numRibbon=%5d, Answer=%5d\n",
        // low, mid, high, (high-low)/2, numRibbon, Answer);
    }
 
    public static void main(String arg[]) throws Exception {
        System.setIn(new FileInputStream("C:\\java\\SW\\sample.txt"));
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            low = 1;
            high = 0;
            Answer = -1;
 
            K = sc.nextInt();
            N = sc.nextInt();
            sizeRibbon = new int[K];
 
            // 리본 길이의 최대값을 구하기
            for (int i = 0; i < K; i++) {
                sizeRibbon[i] = sc.nextInt();
                if (high < sizeRibbon[i]) {
                    high = sizeRibbon[i];
                }
            }
            // System.out.printf("%d: %d\n", test_case, high);
 
            while (low <= high) {
                search();
            }
            System.out.println("#" + test_case + " " + Answer);
        }
    }
}
cs


# 관련 문제

[2110번] 공유기 설치 :: https://www.acmicpc.net/problem/2110

[1654번] 랜선 자르기 :: https://www.acmicpc.net/problem/1654

[2613번] 숫자 구슬 :: https://www.acmicpc.net/problem/2613


# 참고사이트

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

https://coderkoo.tistory.com/8

https://sarah950716.tistory.com/16

https://its2eg.tistory.com/entry/%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89Binary-Search%EC%99%80-%ED%8C%8C%EB%9D%BC%EB%A9%94%ED%8A%B8%EB%A6%AD-%EC%84%9C%EC%B9%98Parametric-Search

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

Segment Tree (구간 트리) ---- (작성중,,,,,)  (0) 2019.03.13
시간복잡도(Time Complexity), 빅오(Big-O)표기법이란?  (0) 2019.02.28
이진 탐색(Binary Search) 알고리즘 개념 및 예제 소스  (0) 2019.02.27

시간복잡도(Time Complexity), 빅오(Big-O)표기법이란?

알고리즘
posted by 귀염둥이채원 2019. 2. 28. 02:38

# 시간복잡도(Time Complexity)란?

* 알고리즘이 문제를 해결하기 위한 시간(연산)의 횟수

* INPUT N에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것

* 최고차항의 계수만 표기하는 방법을 사용

  (N이 커질수록 낮은 차수들의 연산의 횟수는 상대적으로 작아져서 무시해도 됨)


ex) n개의 데이터에 대한 연산 횟수가 

2n^3-5n^2+n+1일 경우 시간 복잡도는 O\left(n^3\right)이다. 
최고차항의 계수 2와 -5n^2+n+1이 시간 복잡도에 영향을 안 끼치는 것은 아니나, 
전체적인 관점에서 보면 최고차항의 차수가 가장 큰 영향을 끼치고 그 외의 것들은 최고차항의 차수에 비하면 상대적으로 영향이 미미하기 때문이다.


# 알고리즘 성능 파악

1. 최선의 경우 Best Case

2. 최악의 경우 Worst Case

3. 평균적인 경우 Average Case


평균적인 경우가 가장 이상적으로 보이겠지만 알고리즘이 복잡해 질수록 평균적인 경우는 구하기가 매우 어려워 진다.

그러므로 최악의 경우로 알고리즘의 성능을 파악한다.


# 빅오(Big-O)표기법이란?

* 최악의 경우로 알고리즘의 성능을 파악하는 것

ex) Binary Search 알고리즘의 시간복잡도를 Big-O로 나타내면 O(n log n)

-> Binary 알고리즘은 n개의 원소가 있을때 아무리 못해도(최악의 경우에) 

   n log n번 정도(대략적) 반복문을 돌리면 값을 찾을 수 있다는 의미이다.


# 시간복잡도 정리

은 \log_{2}n을 의미한다.

  •  과 같은 상수(Constant) 형태
  • O\left(\log n\right) 과 같은 로그(Logarithmic) 형태
  • O\left(n\right) 과 같은 선형
  • O\left(n \log n\right) 과 같은 선형로그 형태
  • O\left(n^c\right), O\left(n^3\right)과 같은 다차(Polynomial) 형태
  • O\left(c^n\right), O\left(3^n\right)과 같은 지수(Exponential) 형태
  • O\left(n!\right)과 같은 팩토리얼(Factorial) 형태


\log n



시간복잡도가 O(N^3)이상이면 시간복잡도가 기하급수적으로 늘기때문에 실행하기 힘든 프로그램



# 참고사항

* 작성한 알고리즘이 1억 번의 연산을 하면 수행시간은 1초로 가정하고 접근하는것이 일반적이다.



# 참고 사이트

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

https://namu.wiki/w/%EC%8B%9C%EA%B0%84%20%EB%B3%B5%EC%9E%A1%EB%8F%84

https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220769859177&proxyReferer=https%3A%2F%2Fwww.google.com%2F

https://www.youtube.com/watch?v=OVRLHJC95Gs

https://www.youtube.com/watch?v=6Iq5iMCVsXA


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

Segment Tree (구간 트리) ---- (작성중,,,,,)  (0) 2019.03.13
Parametric Search(파라메트릭 서치) 알고리즘 개념  (0) 2019.02.28
이진 탐색(Binary Search) 알고리즘 개념 및 예제 소스  (0) 2019.02.27

이진 탐색(Binary Search) 알고리즘 개념 및 예제 소스

알고리즘
posted by 귀염둥이채원 2019. 2. 27. 21:28

# 이진 탐색(Binary Search)이란?

* 반씩 범위를 나누어 가면서 분할정복하여 탐색하는 방법

* 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘 (정렬된 데이터가 아니면 적용이 불가능)

* 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고, 찾을 때까지 그걸 반복하는 걸 생각하면 쉽다.

* 1부터 n까지 숫자중 하나 맞추기 게임을 생각하면 쉽다.


# 선형 자료구조의 대표적인 탐색 방법

* 선형탐색 (Linear Search)

처음부터 하나하나 비교하여 검색하는 방법

장점: 구현하기 쉽고, 정렬이 안되어 있어도 된다.

단점: 검색하는데 시간이 오래 걸린다.


시간 복잡도

최고: O(1), 평균: O(N), 최악: O(N)


* 이진탐색 (Binary Search)

장점: 속도가 빠르다.

단점: 값들이 정렬된 상태이어야 한다.


시간 복잡도

최고: O(1), 평균: O(log N), 최악: O(log N)


# 이진 탐색의 성능

* 탐색 대상의 범위 : 1/2 1/4, 1/16, ... (탐색 대상이 반씩 줄어들게 된다.)

* n : 데이터 집합의 크기

   x : 탐색 반복 횟수

   x = log2n

* 100만개의 데이터 집합 : 최대 20회

* 1000만개의 데이터 집합 : 최대 23회

* 4,294,967,296개(약 43억개)의 데이터 집합: 최대 32회


# 이진탐색 (Binary Search) 과정

1. 데이터 집합의 중앙에 있는 요소 선택

2. 중앙 요소의 값과 찾고자 하는 목표 값을 비교

3. 목표 값이 중앙 요소의 값보다 작다면 중앙을 기준으로 데이터 집합의 왼편에 대해 새로 검색을 수행

   크다면 오른편에 대해 이진 탐색을 새로이 수행

4. 찾고자 하는 값을 찾을 때까지 1번~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
import java.io.FileInputStream;
import java.util.Scanner;
 
public class BinarySearch_Test {
    static int M; // 배열의 개수
    static int N; // 검색할 숫자의 개수
    static int input[];
 
    static void binarySearch(int input[], int low, int high, int searchValue) {
        // 값을 찾지 못한 경우
        if (low > high) {
            System.out.print("-1 ");
            return;
        }
 
        // 중간 index 구하기
        int mid = (low + high) / 2;
 
        // 1. searchValue < 중간값
        // 2. searchValue > 중간값
        // 3. searchValue == 중간값
        if (searchValue < input[mid]) {
            binarySearch(input, low, mid - 1, searchValue);
        } else if (searchValue > input[mid]) {
            binarySearch(input, mid + 1, high, searchValue);
        } else {
            System.out.print(+mid + " ");
            return;
        }
    }
 
    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("C:\\java\\SW\\sample.txt"));
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
 
        for (int test_case = 1; test_case <= T; test_case++) {
            M = sc.nextInt();
            N = sc.nextInt();
            input = new int[M];
 
            for (int i = 0; i < M; i++) {
                input[i] = sc.nextInt();
            }
 
            System.out.print("#" + test_case + " ");
            for (int i = 0; i < N; i++) {
                int searchValue = sc.nextInt();
                binarySearch(input, 0, M - 1, searchValue);
            }
            System.out.println();
        }
        sc.close();
    }
}
cs


# 참고 사이트

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

https://www.youtube.com/watch?v=Vfg6-AWGsCw

https://ledgku.tistory.com/35

https://mygumi.tistory.com/72

https://blockdmask.tistory.com/167

https://wayhome25.github.io/cs/2017/04/15/cs-16/

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

Segment Tree (구간 트리) ---- (작성중,,,,,)  (0) 2019.03.13
Parametric Search(파라메트릭 서치) 알고리즘 개념  (0) 2019.02.28
시간복잡도(Time Complexity), 빅오(Big-O)표기법이란?  (0) 2019.02.28

티스토리툴바