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

codility - Distinct 정답 및 해설

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

난이도 ★☆☆☆☆


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





문제 요약

 몇 가지 종류의 숫자를 입력받았는지를 리턴





힌트

 자료구조 문제입니다. HashSet 활용하면 끝





이하는 코드입니다.


1
2
3
4
5
6
7
8
9
public int solution(int[] A) {
    Set<Integer> nums = new HashSet<>();
 
    for (int a : A) {
        nums.add(a);
    }
 
    return nums.size();
}
cs

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

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

codility - Triangle 정답 및 해설  (0) 2017.07.12
codility - MaxProductOfThree 정답 및 해설  (0) 2017.07.12
codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09
codility - GenomicRangeQuery 정답 및 해설  (0) 2017.06.09
codility - PassingCars 정답 및 해설  (0) 2017.06.09

codility - MinAvgTwoSlice 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 6. 9. 00:43

난이도 ★★★☆☆


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





문제 요약

 A배열을 slice한 자식배열 중 평균값이 최저인 경우를 찾고 그때의 시작 인덱스를 리턴하기





힌트

 경우의수 혹은 아이디어 문제입니다. 평균값이 최저인 경우는 딱 2가지씩만 체크하면 됩니다


 풀이법 링크 : http://disq.us/p/1dwms28





이하는 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int solution(int[] A) {
    double minAvg = (A[0] + A[1]) / 2.0;
    int minStartIndex = 0;
 
    for (int i = 2; i < A.length; i++) {
        double avg = (A[i - 2] + A[i - 1] + A[i]) / 3.0;
 
        if (avg < minAvg) {
            minAvg = avg;
            minStartIndex = i - 2;
        }
 
        avg = (A[i - 1] + A[i]) / 2.0;
 
        if (avg < minAvg) {
            minAvg = avg;
            minStartIndex = i - 1;
        }
    }
 
    return minStartIndex;
}
cs

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

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

codility - MaxProductOfThree 정답 및 해설  (0) 2017.07.12
codility - Distinct 정답 및 해설  (0) 2017.07.12
codility - GenomicRangeQuery 정답 및 해설  (0) 2017.06.09
codility - PassingCars 정답 및 해설  (0) 2017.06.09
codility - CountDiv 정답 및 해설  (0) 2017.06.08

codility - GenomicRangeQuery 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 6. 9. 00:29

난이도 ★★★★☆


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





문제 요약

 S는 문자열 데이터이고, P와 Q는 인덱스입니다.


 S문자열의 P인덱스부터 Q인덱스까지의 글자 중 가장 작은 글자 찾기





힌트

 풀이법을 모르면 천재라도 힘든 문제입니다. 고민 많이 해보신 후 정답을 익히시는 것을 추천합니다.


 풀이법 링크 : http://disq.us/p/1ckv0jr





이하는 코드입니다.


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
public int[] solution(String S, int[] P, int[] Q) {
    int[] answer = new int[P.length];
 
    int[] A = new int[S.length()];
    int[] C = new int[S.length()];
    int[] G = new int[S.length()];
 
    // index == 0
    {
        char c = S.charAt(0);
 
        if (c == 'A') {
            A[0]++;
        }
        else if (c == 'C') {
            C[0]++;
        }
        else if (c == 'G') {
            G[0]++;
        }
    }
 
    // index > 0
    for (int i = 1; i < S.length(); i++) {
        char c = S.charAt(i);
 
        if (c == 'A') {
            A[i] = A[i - 1] + 1;
            C[i] = C[i - 1];
            G[i] = G[i - 1];
        }
        else if (c == 'C') {
            A[i] = A[i - 1];
            C[i] = C[i - 1] + 1;
            G[i] = G[i - 1];
        }
        else if (c == 'G') {
            A[i] = A[i - 1];
            C[i] = C[i - 1];
            G[i] = G[i - 1] + 1;
        }
        else {
            A[i] = A[i - 1];
            C[i] = C[i - 1];
            G[i] = G[i - 1];
        }
    }
 
    for (int i = 0; i < P.length; i++) {
        if (P[i] > 0) {
            if (A[Q[i]] > A[P[i] - 1]) {
                answer[i] = 1;
            }
            else if (C[Q[i]] > C[P[i] - 1]) {
                answer[i] = 2;
            }
            else if (G[Q[i]] > G[P[i] - 1]) {
                answer[i] = 3;
            }
            else {
                answer[i] = 4;
            }
        }
        else {
            if (A[Q[i]] > 0) {
                answer[i] = 1;
            }
            else if (C[Q[i]] > 0) {
                answer[i] = 2;
            }
            else if (G[Q[i]] > 0) {
                answer[i] = 3;
            }
            else {
                answer[i] = 4;
            }
        }
    }
 
    return answer;
}
cs

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

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

codility - Distinct 정답 및 해설  (0) 2017.07.12
codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09
codility - PassingCars 정답 및 해설  (0) 2017.06.09
codility - CountDiv 정답 및 해설  (0) 2017.06.08
codility - MaxCounters 정답 및 해설  (0) 2017.06.06

codility - PassingCars 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 6. 9. 00:07

난이도 ★★☆☆☆


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





문제 요약

 각 0의 뒤에 나오는 1의 개수를 각각 구한다음 걔네를 다 더하기 (오버플로우나면 -1 리턴)





힌트

 미리 1의 개수를 구해놓는 방법을 통해 중첩for문 제거





이하는 코드입니다. (복잡도 2n의 코드인데, 개선하면 n도 가능할겁니다)


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
public int solution(int[] A) {
    int firstZeroIndex = -1;
 
    for (int i = 0; i < A.length; i++) {
        if (A[i] == 0) {
            firstZeroIndex = i;
            break;
        }
    }
 
    if (firstZeroIndex == -1) {
        return 0;
    }
 
    int totalOneCount = 0;
 
    for (int i = firstZeroIndex + 1; i < A.length; i++) {
        if (A[i] == 1) {
            totalOneCount++;
        }
    }
 
    if (totalOneCount == 0) {
        return 0;
    }
 
    int result = totalOneCount;
    int lastOneCount = 0;
 
    for (int i = firstZeroIndex + 1; i < A.length; i++) {
        if (A[i] == 0) {
            result += totalOneCount - lastOneCount;
 
            if (result > 100000000 || result < 0) {
                return -1;
            }
        }
        else if (A[i] == 1) {
            lastOneCount++;
        }
    }
 
    return result;
}
cs


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

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

codility - MinAvgTwoSlice 정답 및 해설  (0) 2017.06.09
codility - GenomicRangeQuery 정답 및 해설  (0) 2017.06.09
codility - CountDiv 정답 및 해설  (0) 2017.06.08
codility - MaxCounters 정답 및 해설  (0) 2017.06.06
codility - MissingInteger 정답 및 해설  (1) 2017.06.06

티스토리툴바