Strong Root

알고리즘의 복잡도란? (2. 시간 복잡도)

뿌리튼튼 CS/Algorithm2017. 7. 28. 23:03

1. 공간 복잡도 (Space complexity)


이전 글에..



2. 시간 복잡도 (Time complexity)


반복문을 총 몇번 도는지를 의미합니다.



아래는 1부터 n까지의 합을 구하는 함수입니다.


시간 복잡도는 "n" 입니다.


1
2
3
4
5
6
7
8
9
public int solution(int n) {
    int sum = 0;
 
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
 
    return sum;
}
cs





같은 함수를 수학공식을 이용해 아래와 같이 바꾸면 시간 복잡도는 "1" 이 됩니다.


(수학을 잘하면 알고리즘에 유리합니다)


1
2
3
public int solution(int n) { 
    return (1 + n) * n / 2;
}
cs





API 사용시에는 주의해야합니다.


아래 함수의 시간 복잡도는 얼마일까요? "A.length" 일까요?


(함수 내용은 이해할 필요 없음)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int solution(int[] A) {
    List<Integer> marks = new ArrayList<>();
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] > A.length) {
            return 0;
        }
 
        if (marks.contains(A[i])) {
            return 0;
        }
 
        marks.add(A[i]);
    }
 
    return 1;
}
cs


답은 "A.length X A.length" 입니다. "A.length" 의 제곱이지요.


왜냐하면 ArrayList.contains() 함수의 시간 복잡도가 "해당 list의 길이" 이기 때문입니다.


(내부적으로 list 전체를 반복문을 돌면서 인자로 던져준 객체가 있는지 확인합니다)





위 함수에서 ArrayList 대신 HashSet 을 사용하면 어떨까요?


출력은 같지만 복잡도는 "A.length" 가 됩니다.


HashSet.contains() 함수의 시간 복잡도는 "1" 이기 때문입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int solution(int[] A) {
    Set<Integer> marks = new HashSet<>();
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] > A.length) {
            return 0;
        }
 
        if (marks.contains(A[i])) {
            return 0;
        }
 
        marks.add(A[i]);
    }
 
    return 1;
}
cs






3. 빅오 표기법 (Big-O notation)


다음 글에..

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

codility - Brackets 정답 및 해설  (0) 2017.08.08
알고리즘의 복잡도란? (3. 빅오 표기법)  (0) 2017.07.28
알고리즘의 복잡도란? (1. 공간 복잡도)  (0) 2017.07.28
codility - Triangle 정답 및 해설  (0) 2017.07.12
codility - MaxProductOfThree 정답 및 해설  (0) 2017.07.12

알고리즘의 복잡도란? (1. 공간 복잡도)

뿌리튼튼 CS/Algorithm2017. 7. 28. 22:42

복잡도가 낮을 수록 성능이 뛰어난 알고리즘입니다.


알고리즘의 복잡도(Complexity)는 두 가지 요소로 측정합니다.





1. 공간 복잡도 (Space complexity)


간단합니다. 사용되는 변수의 개수를 의미합니다.


단, 인자 변수들은 일반적으로 제외하고 카운트합니다.



예를들어 아래와 같은 함수의 경우, 공간 복잡도는 "2" 입니다. (sum, i)


(함수 내용은 이해할 필요 없음)


1
2
3
4
5
6
7
8
9
public int solution(int n) {
    int sum = 0;
 
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
 
    return sum;
}
cs






또 하나의 예시를 들어보면, 아래 함수의 경우 공간 복잡도는 "N + 3" 입니다. (counter, tmpMaxCounter, doneMaxCounter, i)


(마찬가지로 함수 내용은 이해할 필요 없음)


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
public int[] solution(int N, int[] A) {
    int[] counter = new int[N];
    int tmpMaxCounter = 0;
    int doneMaxCounter = 0;
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] > N) {
            doneMaxCounter = tmpMaxCounter;
        }
        else {
            if (counter[A[i] - 1] < doneMaxCounter) {
                counter[A[i] - 1] = doneMaxCounter;
            }
 
            counter[A[i] - 1]++;
 
            if (counter[A[i] - 1] > tmpMaxCounter) {
                tmpMaxCounter = counter[A[i] - 1];
            }
        }
    }
 
    if (doneMaxCounter > 0) {
        for (int i = 0; i < counter.length; i++) {
            if (counter[i] < doneMaxCounter) {
                counter[i] = doneMaxCounter;
            }
        }
    }
 
    return counter;
}
cs






2. 시간 복잡도 (Time complexity)


다음 글에..




3. 빅오 표기법 (Big-O notation)


다음 다음 글에..

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

알고리즘의 복잡도란? (3. 빅오 표기법)  (0) 2017.07.28
알고리즘의 복잡도란? (2. 시간 복잡도)  (0) 2017.07.28
codility - Triangle 정답 및 해설  (0) 2017.07.12
codility - MaxProductOfThree 정답 및 해설  (0) 2017.07.12
codility - Distinct 정답 및 해설  (0) 2017.07.12

codility - Triangle 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 7. 12. 14:42

난이도 ★★☆☆☆


문제를 보시려면 여기를 클릭





문제 요약

 입력받은 숫자들을 변의 길이라고 가정했을 때, 삼각형을 그릴 수 있는지를 리턴





힌트

 논리적인 답은 몇줄이면 끝난다. 근데 -.-; 두가지 이유때문에 코드가 지저분해진다. (경우의 수 문제)


 1. 음수가 입력될 수 있다.

 2. 오버플로우를 고려해야 한다.





이하는 코드입니다.


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
public int solution(int[] A) {
    Arrays.sort(A);
 
    for (int i = A.length - 3; i >= 0; i--) {
        if (isTriangular(A[i], A[i + 1], A[i + 2])) {
            return 1;
        }
    }
 
    return 0;
}
 
private boolean isTriangular(int l1, int l2, int l3) {
    boolean ok;
 
    int sum12 = l1 + l2;
    if (l1 > 0 && l2 > 0 && sum12 < 0) {
        ok = true;
    }
    else if (l1 < 0 && l2 < 0 && sum12 > 0) {
        ok = false;
    }
    else {
        ok = sum12 > l3;
    }
 
    if (!ok) {
        return false;
    }
 
    int sum23 = l2 + l3;
    if (l2 > 0 && l3 > 0 && sum23 < 0) {
        ok = true;
    }
    else if (l2 < 0 && l3 < 0 && sum23 > 0) {
        ok = false;
    }
    else {
        ok = sum23 > l1;
    }
 
    if (!ok) {
        return false;
    }
 
    int sum31 = l3 + l1;
    if (l3 > 0 && l1 > 0 && sum31 < 0) {
        ok = true;
    }
    else if (l3 < 0 && l1 < 0 && sum31 > 0) {
        ok = false;
    }
    else {
        ok = sum31 > l2;
    }
 
    return ok;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

알고리즘의 복잡도란? (2. 시간 복잡도)  (0) 2017.07.28
알고리즘의 복잡도란? (1. 공간 복잡도)  (0) 2017.07.28
codility - MaxProductOfThree 정답 및 해설  (0) 2017.07.12
codility - Distinct 정답 및 해설  (0) 2017.07.12
codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09

codility - MaxProductOfThree 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 7. 12. 14:29

난이도 ★☆☆☆☆


문제를 보시려면 여기를 클릭





문제 요약

 입력받은 숫자들 중 3개를 뽑아서 곱했을 때 가장 큰 값을 리턴





힌트

 정렬을 한 후 최대값끼리 곱한다. 단! 음수에 주의하여야 한다 (경우의 수 문제)





이하는 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int solution(int[] A) {
    Arrays.sort(A);
 
    if (A[A.length - 1] < 0) {
        return A[A.length - 1] * A[A.length - 2] * A[A.length - 3];
    }
 
    if (A[A.length - 2] < 0 || A[A.length - 3] < 0) {
        return A[A.length - 1] * A[0] * A[1];
    }
 
    int p1 = A[A.length - 1] * A[A.length - 2] * A[A.length - 3];
    int p2 = A[A.length - 1] * A[0] * A[1];
 
    return p1 > p2 ? p1 : p2;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

알고리즘의 복잡도란? (1. 공간 복잡도)  (0) 2017.07.28
codility - Triangle 정답 및 해설  (0) 2017.07.12
codility - Distinct 정답 및 해설  (0) 2017.07.12
codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09
codility - GenomicRangeQuery 정답 및 해설  (0) 2017.06.09

티스토리툴바