[TIL] 알고리즘 - 시간 복잡도

 

..................

 

 

 

최근에 봤던 두 번에 걸친 웹 개발 기초와 프로그래밍 언어에 대한 학습 이해 그리고 면접을 걸친 장장 약 3주 동안 진행되었던 코딩 부트캠프 지원은 역시 이번에도 불합격으로 마무리 지었다. 이메일 한통에 담긴 불합격이 솔직히 좀 익숙하긴 한데 받을 때마다 화나는 건 어쩔 수 없다...^^ 부트캠프에 탈락했으므로 다시 알고리즘에 집중할 때이다. 하반기에는 합격소식이 늘었으면. 

 

 

---

 

이때까지 코테를 봤을 때 요구사항 구현에서 막힌 적이 대부분이지만 간혹 효율성을 보는 문제에서 정답으로 해당하는 값이 출력됨에도 불구하고 효율성이 안 좋아서 제출하지 못했던 적도 있다. 그래서 그 부분을 한번 정리해보기로 한다.

 

알고리즘의 효율성을 논할때는 공간 복잡도(space complexity)와 시간 복잡도(time complexity)가 주 관심사이다. 

 

공간 복잡도는 프로그램을 실행할때 필요로 하는 자원 공간의 양 을 의미하고

시간 복잡도는 프로그램을 실행하는데 필요한 절대적인 시간이 아닌 연산을 하는 횟수를 의미한다.

 

공간 복잡도와 시간 복잡도는 상충 관계(trade off)이다. 알고리즘을 짤 때 이 두 개를 주의해가면서 알고리즘을 짜야할 것 같지만 저장공간 의 발달로 인해서 공간 복잡도에 대한 부담에 줄어들어서 보통 시간 복잡도만 주의해가면서 알고리즘을 짜면 된다.

 

---

 

시간 복잡도와 공간 복잡도를 말할때 빼놓을 수 없는 것은 바로 Big-O 표기법이다. 알고리즘의 효율성을 표현하는 방식도 여러 가지가 있지만 Big(O) 표기법이 가장 보편화된 방법이다. 

알고리즘에 따라서 O(1) , O(n), O(logn) 식으로 보통 표기하고 이 세가지 방식만 이해하면 자신이 짠 알고리즘과 기타 다른 응용 표현방식도 이해할 수 있다. 

 

1. O(1) 

괄호 안에 들어간 1은 임의의 상수를 나타낸다. 알고리즘을 실행시 한번 단위 실행만으로 연산이 끝날 때를 의미한다. 

 

 

 

---

2. O(n) 

O(1) 은 한번 단위 실행으로 연산이 끝났다면 O(n) 은 입력한 양이 증가하면 동일하게 필요한 단위 실행도 증가하는 1대 1의 선형 관계이다.

 

 

1번과 2번을 코드로 예시를 들어보자면

import java.util.ArrayList;
import java.util.List;

public class ex {

    public static void main(String[] args) {

        List<Integer> list = new ArrayList<>();        
        
        //1.
        for (int i=0; i < 10; i++){
            list.add(i);
        }
		
        //2.
        int num = list.get(2);

        //3.        
        for (int j : list){
            if (list.get(j) == 3){
                System.out.println(list.get(j));
            }
        }
    }
}

자바에서 List 자료 안에 0부터 9까지의 정수를 넣고 0번 인덱스부터 순회하면서 만약 그 인덱스 값이 3이라면  그 값을 출력하는 코드다. 이때 주석으로 표시된  //2. 의 시간 복잡도를 구해보자.

 

배열의 가장 큰 특징은 내가 원하는 값의 인덱스를 알고 있으면 인덱스 번호만으로 접근이 가능하다는 점이다. 그러므로 시간 복잡도는 O(1)이다.

 

그렇다면 //3. 번의 시간 복잡도는? 답은 O(n)이다. 검색을 위해서 배열의 0번 인덱스부터 차례대로 탐색하기 때문에 배열의 양만큼 탐색해야 하기 때문이다.

 

---

 

3. O(logn)

O(logn) 은 로그에 대한 이해가 조금 필요한데, log 다음에 쓰여있는 첨자 '밑' 으로 '밑' 다음에 써있는 진수가 밑의 몇 제곱인지를 표현하는 수학 용어이다. Big-O에서 의 logn 은 사실 밑이 2인 로그인데 이를 바꿔 말하면 한 번의 단위 실행을 한 다음 그다음에 추가로 필요한 단위 실행이 절반으로 줄어드는 경우를 말한다. 이를 좀 더 수학적으로 보자면 

 

 

빨간색은 O(n)에 해당하는 y = x의 그래프이고 파란색은 O(logn)에 해당하는 밑이 2인 y = logx의 그래프이다. 

x축은 자료의 양, y축은 필요 연산의 수라고 보면 되는데 필요한 자료가 많으면 많아질수록 O(n)은 1대 1로 늘어나는 반면 O(logn)은 연산을 할 때마다 반감되므로 비교적 완만하게 늘어나는 것을 볼 수 있다.

 

https://www.bigocheatsheet.com/

더 많은 내용은 위 사이트에서 확인해볼 수 있다.

 

3번의 예시로는 Tree를 들 수 있다. 

 

import java.util.TreeSet;

public class ex {

    public static void main(String[] args) {

        TreeSet<Integer> tree = new TreeSet<>();

        tree.add(7);
        tree.add(10);
        tree.add(6);
        tree.add(5);
        tree.add(9);
        tree.add(12);
        tree.add(4);


        System.out.println(tree.higher(11));


    }
}

 

Tree 형태의 자료구조를 가진 자바의 TreeSet에서 순차적으로 값을 넣었고 11보다 큰 값이 뭔지 출력하는 알고리즘이다.

위 알고리즘을 그림으로 나타내면

이런 형태이다. 값을 추가할 때 최상단 노드부터 시작해서 그 값보다 작으면 왼쪽으로, 크면 오른쪽으로 내려가는 자료구조이다. 11보다 큰 값을 검색한다면 최상단의 7부터 시작해서 

 

1. 11은 7보다 크므로 오른쪽으로 이동

2. 11은 10보다 크므로 오른쪽으로 이동.

3. 12는 11보다 크므로 원하는 값 출력

 

3번의 탐색만으로 원하는 값을  출력할 수 있다. 부모 노드를 기준으로 해서 작은 값은 왼쪽 큰 값은 오른쪽에 있으므로 아래 level로 내려갈 때마다 필요한 연산이 절반씩 줄어들게 되므로 시간 복잡도는 O(logn)이다.

 

 

---

 

알듯 말듯했던 부분인데 공부하니까 확실히 알 것 같다. 처음 알고리즘 문제를 접했을 때는 O(n * 2)에 해당하는  이중 for문도 서슴지 않고 썼던 것 같은데 공부하면서 정말 기상천외하게 해결하는 다른 사람들의 풀이를 보면서 상황에 맞는 자료구조와 시간 복잡도를 줄이는 효율적인 코드를 짜는 것에 대해서 한 번 더 생각해보는 것 같다. 이런 고민은 알고리즘 문제를 푸는 지금에도 도움이 되지만 대량의 트래픽이 발생하는 서비스를 개발할때도 큰 도움이 되지 않을까 라고 생각해본다.