자바(java) 프로그램 코드의 시간 측정 방법

Java
posted by 귀염둥이채원 2019. 2. 28. 19:02

프로그래밍을 하다보면 특정 소스 코드 구간의 시간을 측정해야 하는 경우 생긴다.

알고리즘을 문제를 풀다보면 시간복잡도가 중요하기 때문에 알고리즘에 대한 속도를 측정하는 것이 필요하다.

또는 개발한 프로그램의 성능이 잘 안나오는 경우 어느 부분이 병목인지 확인이 필요할수도 있다.


자바(Java)에서 System 함수인 System.currentTimeMillis() 함수를 이용하면 쉽게할 수 있다.

시작 구간과 끝나는 구간에 각각 해당 함수를 써서 시간을 저장한 후,

두 시간간의 차이를 계산하면 ms 단위의 시간차를 구할 수 있다.


아래의 코드는 특정 부분의 로직에 걸리는 시간을 테스트 할때 사용하면 좋다.


# 샘플 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TEST {
    public static void main(String arg[]) throws Exception {
        long beforeTime = System.currentTimeMillis();
        long count = 0;
        for (int i = 0; i < 1000000; i++) {
            for (int j = 0; j < 1000000; j++) {
                count++;
            }
        }
        System.out.println("count= " + count);
        long afterTime = System.currentTimeMillis();
        long secDiffTime = (afterTime - beforeTime);
        System.out.println("시간차이(msec) : " + secDiffTime);
    }
}
cs

# 참고 사이트

https://hijuworld.tistory.com/2

http://www.topcredu.com/bbs/board.php?bo_table=LecJava&wr_id=736

'Java' 카테고리의 다른 글

[자바/JAVA] String, StringBuilder, StringBuffer 차이 정리  (0) 2019.03.03
[자바/JAVA] String to int, int to String 변환하는 방법  (0) 2019.03.03
자바(Java) static 키워드 개념 및 사용법  (0) 2019.02.28
자바(Java) final 키워드 개념 및 사용법  (0) 2019.02.28
[Java] 데이터 자료형(byte, char, int long, float, long) 최대값, 최소값 확인 방법  (0) 2019.02.28

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

[Java] 데이터 자료형(byte, char, int long, float, long) 최대값, 최소값 확인 방법

Java
posted by 귀염둥이채원 2019. 2. 28. 15:54

# 자바 기본 타입(Primitive)

- 정수타입: byte(1바이트), short(2바이트), char(2바이트), int(4바이트), long(8바이트)

- 실수타입: float(4바이트), double(8바이트)

- 논리타입: Boolean(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
public class TEST {
    public static void main(String[] args) throws Exception {
        System.out.println("##### byte 타입의 값");
        System.out.println("MIN: " + Byte.MIN_VALUE);
        System.out.println("MAX: " + Byte.MAX_VALUE + "\n");
 
        System.out.println("##### short 타입의 값");
        System.out.println("MIN: " + Short.MIN_VALUE);
        System.out.println("MAX: " + Short.MAX_VALUE + "\n");
 
        System.out.println("##### int 타입의 값");
        System.out.println("MIN: " + Integer.MIN_VALUE);
        System.out.println("MAX: " + Integer.MAX_VALUE + "\n");
 
        System.out.println("##### long 타입의 값");
        System.out.println("MIN: " + Long.MIN_VALUE);
        System.out.println("MAX: " + Long.MAX_VALUE + "\n");
 
        System.out.println("##### float 타입의 값");
        System.out.println("MIN: " + Float.MIN_VALUE);
        System.out.println("MAX: " + Float.MAX_VALUE + "\n");
 
        System.out.println("##### double 타입의 값");
        System.out.println("MIN: " + Double.MIN_VALUE);
        System.out.println("MAX: " + Double.MAX_VALUE + "\n");
    }
}
cs


# 결과

##### byte 타입의 값

MIN: -128

MAX: 127


##### short 타입의 값

MIN: -32768

MAX: 32767


##### int 타입의 값

MIN: -2147483648

MAX: 2147483647


##### long 타입의 값

MIN: -9223372036854775808

MAX: 9223372036854775807


##### float 타입의 값

MIN: 1.4E-45

MAX: 3.4028235E38


##### double 타입의 값

MIN: 4.9E-324

MAX: 1.7976931348623157E308 


'Java' 카테고리의 다른 글

[자바/JAVA] String, StringBuilder, StringBuffer 차이 정리  (0) 2019.03.03
[자바/JAVA] String to int, int to String 변환하는 방법  (0) 2019.03.03
자바(Java) static 키워드 개념 및 사용법  (0) 2019.02.28
자바(Java) final 키워드 개념 및 사용법  (0) 2019.02.28
자바(java) 프로그램 코드의 시간 측정 방법  (0) 2019.02.28

티스토리툴바