Ch.04 빅 오로 코드 속도 올리기 (도서 요약 "누구나 자료구조와 알고리즘")

ImKDM 2022. 4. 26. 16:45

728x90

빅 오를 사용 하면 내가 만든 알고리즘과 세상에 존재하는 범용 알고리즘을 비교할 기회가 생기며, 제작한 알고리즘이 얼마나 빠른지 혹은 느린지 확인이 가능하다. 이번 파트에선 빅 오를 사용해서 작성한 알고리즘을 평가해본다. 그리고 효율성을 높이기 위한 알고리즘 수정 방법도 알아본다.

4. 1 버블 정렬

정렬 알고리즘은 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 지난 수년간 수십 개의 정렬 알고리즘이 개발돼 왔다. 이러한 알고리즘은 모두 "정렬되지 않은 배열을 어떻게 오름차순으로 정렬할 수 있을까?"에 대한 문제를 해결한다.

가장 먼저 '단순 정렬(simple sort)'이라고 알려진 알고리즘 분류가 있다. 이것은 이후 배울 알고리즘보다 비효율적이다. 대표적으로 "버블 정렬(bubble sort)"가 있다. 버블 정렬은 배열 내에서 첫 번째 항목과 두 번째 항목을 비교한다. 왼쪽 값이 오른쪽 값보다 크면 두 항목을 교환한다(순서가 올바르다면 2단계에서는 아무것도 하지 않는다). 포인터를 오른쪽으로 한 셀씩 옮긴다. 배열의 끝까지 또는 이미 정렬된 값까지 해당 단계를 반복한다. 즉 배열 끝까지 값을 하나하나 가리키며 배열을 "통과"시킨다. 이것을 '첫 번째 패스스루(pass-through)'라고 한다.

4. 2 버블 정렬의 효율성

버블 정렬 알고리즘은 두 가지 중요한 단계를 가진다.

(1) 비교(comparison): 어느 쪽이 더 큰지 두 수를 비교함.

(2) 교환(swap): 정렬하기 위해 두 수를 교환함.

먼저 버블 정렬에서 얼마나 많은 '비교'가 일어나는지 알아보면, 예를 들어 원소가 5개인 배열에선 첫 번째 패스스루에 두 수의 비교를 4번 해야 한다. 첫 번째 패스스루를 거치면서 마지막 숫자가 올바른 위치로 갔기 때문에 마지막 두 수를 비교할 필요가 없어서 두 번째 패스스루에서는 비교를 3번만 한다. 세 번째 패스스루에선 비교를 2번을, 네 번째엔 비교를 딱 1번만 한다. 따라서 4 + 3 + 2 + 1 = 총 10번의 비교가 필요하다.

즉 원소 N개가 있을 때, (N - 1) + (N - 2) + (N - 3) + (N - 4).... + 1번의 비교를 수행해야 한다.

버블 정렬에서 최악의 시나리오라면 '교환'은 비교할 때마다 교환하는 것이다. 즉, 총 10번의 비교가 일어났다면 10번의 교환이 발생해 총 20단계가 필요한 것이다.

만약 값 10개가 역순으로 된 배열에서는 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45번의 비교와 45번의 교환이 일어나 총 90단계다.

원소가 20개인 배열에서는 19 + 18 + 17 + 16 + 15 + 14 + 13 + 12 +.... + 4 + 3 + 2 + 1 = 190번의 비교와 190번의 교환이 일어나므로 총 380단계다.

원소가 증가할수록 단계 수가 기하급수적으로 늘어난다. 이는 N이 증가할 때마다 단계 수는 대략 N² 만큼 늘어난다는 뜻이다. 이것을 O(N)로 표기하면 다음과 같다.

O(N²)

버블 정렬의 효율성이 O(N²)로, N(O)보다 비효율적인 알고리즘이다. O(N²)은 '이차 시간(quadratic time)'이라고 부른다.

4. 4 이차 문제

중복된 값이 있는지 확인하는 알고리즘을 보자.

예를 들어 배열 [1, 5, 3, 9, 1, 4, 5]에 중복된 값이 있는지 확인하려고 한다. 중첩 for문을 통해 알아낼 수 있다.

boolean hasDuplicateValue(int[] arr) {
    for(int i=0; i<arr.length; i++) {
        for(int j=0; j<arr.length; j++) {
            if(i != j && arr[i] == arr[j]) {
                return true;     //   중복값이 있으면 true
            }
        }
    }
    return false;     //   중복값이 없으면 false
}

변수 i를 사용해 배열 내 각 원소를 순회한다. 그리고 변수 j로 배열 내 모든 값을 살펴보며 i와 j 인덱스에 있는 두 값이 같은지 확인한다.

자, 빅 오의 의미를 해당 hasDuplicateValue 메서드에 적용해보자. "hasDuplicateValue 메서드에 값 N개를 포함하는 배열이 주어졌을 때, 최악의 시나리오에서 알고리즘에 얼마나 많은 단계가 필요할까?" 이 질문에 답하려면 어떤 단계가 필요한지, 그리고 최악의 시나리오는 어떤 경우인지 분석해야 한다.

이 메서드에는 '비교'라는 한 단계만 존재한다. 메서드를 반복해서 i와 j를 비교함으로써 같은지 확인한다. 최악의 시나리오는 배열이 중복 값을 포함하지 않아 false를 반환하기 전에 모든 루프를 수행하고 모든 조합을 전부 비교하는 것이다.

결론적으로 배열 값 N개가 있을 때 함수는 N²번의 비교를 수행한다. 배열을 전부 살펴보기 위해 무조건 N번을 순회해야 하고, 순회마다 안쪽 루프에서 다시 N번을 순회해야 하기 때문이다. 이는 N단계 x N단계이므로 O(N²)의 알고리즘이다.

중첩 루프 알고리즘은 대부분 O(N²)이다. 따라서 중첩 루프가 보이면 O(N²)를 가장 먼저 고려해봐야 한다. 그러나 O(N²)는 상대적으로 느린 알고리즘이라 더 나은 대안에 대해 고민이 필요하다.

4. 5 선형 해결법

앞에서 알아본 O(N²)의 비효율성을 개선하기 위해 중첩 루프를 사용하지 않는 메서드를 만들 수 있다.

일단 existingNumbers라는 빈 배열을 생성한다. 그리고 for문을 사용해 array의 각 숫자를 확인하고, 각 숫자가 나올 때마다 existingNumbers 배열의 해당 숫자 자리(인덱스)에 1을 넣는다.

boolean hasDuplicateValue(int[] arr) {
	int[] existingNumbers = new int[]; // 가상 배열 생성. 정확한 생성 방법은 아직 모르겠다 ㅠㅠ
    
    for(int i=0; i<arr.length; i++) {
        if(existingNumbers[array[i]] == 1) {
            return true;    //  existingNumbers 배열의 자리에 곂치는 1이 있으면 중복 값 존재!
        } else {
            existingNumbers[array[i]] = 1;
        }
    }
    return false;   //  existingNumbers 배열의 각 자리에 곂치는 1이 없으면 중복된 값은 없다!
}

여기서 중요한 단계는 해당 인덱스에 이미 1이 있는지 확인하는 것이다. 1이 있다면 이미 나왔던 숫자라는 뜻이고 바로 true를 반환하게 된다. true를 반환하지 않고 for문 끝까지 갔다면 중복 값이 없다는 뜻이니 false를 반환한다.

빅 오 관점에서 이 알고리즘의 효율성을 알아내려면 최악의 시나리오일 때 알고리즘에 필요한 단계 수를 알아내야 한다.

이 알고리즘에서 existingNumbers 배열에 해당 인덱스의 값이 1인지 확인하는 것이 중요하다. 그래서 원소가 N개 있는 배열인 경우 N번 확인하기 때문에 O(N)이 된다.

O(N)은 O(N²) 보다 훨씬 빠르기 때문에 두 번째 접근법을 사용함으로써 속도 향상을 이뤄낼 수 있다.

4. 6 마무리

빅 오 표기법을 명확히 이해하면 두 경쟁 알고리즘 중 더 빠른 알고리즘을 골라낼 수 있다. 하지만 빅 오 표기법에서는 두 알고리즘이 속도가 같다고 해도 실제로는 어느 한쪽이 더 빠른 상황이 나올 수 있다. 빅 오 표기법으론 이러한 차이를 발견할 수 없는 알고리즘들의 효율성을 평가하는 법을 앞으로 배워보자.

해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.

오로지 학습용으로 작성하였음을 밝힙니다.

더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.