[코딩 테스트] 제로부터 시작하는 코딩테스트 (시간 복잡도) - 0 -

코딩테스트를 준비하기 위해서 가장 먼저 알아야 할 것은 시간 복잡도 입니다.

쩝... 시..간..복..잡..도 그게 머지

아마 이글을 보시는 여러분은 저와 마찬가지로 코딩테스트를 처음으로 대비하는 분들일 것이라 생각이 듭니다.

저와 함께 대비하시면서, 조금이라도 도움이 됐으면 좋겠네요.

---

시간 복잡도란?

 

시간 복잡도란 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가르킵니다. 

...?

무슨 말씀이신지 이해가 잘 되지 않을거에요. 그래서 제가 찾은 내용을 바탕으로 간단하게 요약하려 합니다.

 

#시간복잡도

🚀 개발자가 알고리즘을 작성한 코드에서 효율성을 측정하기 위해서 등장한 개념

🚀 개발자가 작성한 알고리즘 코드에서 입력값의 변화에 따라 연산을 실행할때, 연산 횟수 대비 걸리는 시간 측정

🚀 주로 빅-오 표기법으로 사용해 나타낸다.

 

쉽게 말해서, 효율성을 측정하기 위해서 연산 횟수 대비 걸리는 시간을 측정하는 기준이라고 보면 될 것 같아요.

---

📢 Big-O (빅-오) 표기법.

Big-O 표기법은 시간 복잡도를 표기하는 세가지 방법 중 최악의 경우에 대비하여 나타내는 방식입니다.

그럼 왜 최악의 경우를 나타내는 방식이 가장 많이 사용될까요? 그 이유는 최선의 경우를 대비하는 방식보다는 최악의 경우를 대비하는 것이 더 나은 방식이기 때문입니다. 최선의 경우 10분이면 해결되지만, 최악의 경우 300분이 걸린다면 어떡할까요? 최선만 대비했다면 이런 최악의 경우는 대비하지 못하기 때문에 그에 맞는 대응을 못하게 됩니다. 그렇기에 빅-오 방식으로 최악에 경우에 대비하는 것이 일반적입니다.

그리고 이 빅-오를 표기법의 종류로 총 5가지가 있습니다. 하나하나 살펴볼게요.

---

🔗 O( 1 )

먼저 O(1)[일정한 복잡도(constant complexity)]입니다..

O(1)같은 경우에는 입력값이 증가하더라도 시간이 늘어나지 않습니다

간단한 예시 코드를 샘플로 작성해보면, 아래와 같이 작성 할 수 있습니다.

public class O1Test {
    public int O1Algorithm(int[] arr,int index){
        return arr[index];
    }

    public static void main(String[] args){
        O1Test o1Test = new O1Test();
        int[] arr = {1,2,3,4};
        int index = 1;
        int result = o1Test.O1Algorithm(arr,index);

        System.out.println(result);

    }

}

arr는 지정되어 있고 index 넘버로 찾아가게 됩니다. 이런 경우에는 index 번호로 조회하기 때문에,  배열의 길이가 아무리 길어도 해당 index 값을 통해 바로 출력 값을 얻게 됩니다. 이렇듯 걸리는 시간이 일정한 경우를 O(1)이라 합니다. 

그리고 이런 특성때문에 O(1)은 가장 빠른 시간복잡도를 가지고 있습니다.

---

🔗 O( n )

다음으로는 O( n )[선형 복잡도 (Linear Complexity)] 입니다. 해당 방식은 입력값이 증가함에 따라 시간또한 같은 비율로 증가 합니다.

쉽게 설명드리면  입력값과 대칭으로 증가한다고 생각 하면 됩니다. 싱글 for 문이 대표적인 O( n )입니다. 샘플 코드를 보시면 조금 더 이해가 쉬울 거에요. 

자 아래와 같은 코드가 있습니다.

int n = [ input number ];

for( int i=0;i < n;i++ ){
    System.out.println(i);
}

 초기에 n값이 1이라고 생각해볼게요 그럼 루프는 총 1회 돌게 됩니다. 그리고 한번 루프 할때 1초가 걸린다고 가정하겠습니다. 그럼 n값이 10이라면 총 10회루프를 타게 되고 10초가 걸리겠죠? 이렇게 n이 증가 함에 따라서 시간 복잡도가 같은 비율로 증가하는 경우 O(n) 이라고 표시합니다.

그럼 이번에는 2*n으로 n에 2를 곱해줍니다.

int n = 1; // 1~10

for( int i=0;i <(2*n);i++ ){
    System.out.println(i);
}

 

 

이런 경우에는 어떻게 표시할까요? O(2n) 이라고 하면 될까요?? 

아쉽게도 아닙니다. 

왜 아니냐!! 2초씩 증가하잖아!!

O( n )은 같은 비율로 증가하는 알고리즘을 표기합니다. n이든 2n이든 3n이든 같은 비율로 증가하면 O( n ) 표기법을 사용해 표시합니다.

---

🔗 O(log n)

O(log n) [로그 복잡도(logarithmic complexity)] 는 Big-O표기법 중 O(1) 다음으로 가장 빠른 시간 복잡도를 가졌습니다.

시간이 지남에 따라서 걸리는 시간이 줄어드는 형태를 가지고 있습니다. 탐색 할때마다 범위를 좁히는 알고리즘들이 로그 복잡도를 가지고 있다고 볼 수 있습니다. 

해당 log N 을 이해하기 위해서는 이진트리 자료구조(BST)를 먼저 이해하는 게 좋습니다.

log N 같은 경우 BST와 함께 이후 포스팅에서 조금 더 디테일하게 다루겠습니다. 지금으로선

O(log N)은 O(1) 다음으로 효율적이며, 탐색 시 범위를 좁혀서 효율적으로 검색하는 방식을 표현할때 사용한다. 로 기억해주시면 좋을 것 같습니다.

---

🔗 O(N^2[제곱])

O(N^2)는 2차복잡도 라고 불립니다, 입력값이 증가함에 따라 시간의 n의 제곱수의 비율로 증가합니다. 

흔히 많이 사용하는 2중 루프같은 경우 O(n2)형태로 되어있습니다. 혹시 이중 For문을 사용해서 구구단을 구현해보신분 있나요?

int answer = 9

for(int i=1;i<=9;i++){
	for(int j=1;j<=9;j++){
    	System.out.println(i+"X"+j+"="+(i*j);
    }
}

아마 이런 로직으로 제작되어 있을 겁니다. 

이런 경우 루프가 총 몇번 돌까요? 1단에 9번씩 9단까지 반복하니 81회가 반복됩니다.

즉 9^2 입니다. 초로 따지면 81초가 걸립니다. 앞에서 말씀드린 O(1)과 O(N) O(LogN)과 확연히 차이나죠?

O(N^2)과 마찬가지로 9^3이든 9^100이든 이런 식으로 제곱단위로 늘어나는 경우를 O(n2)라고 합니다.

---

🔗 O(2N)

O(2N)[기하급수적 복잡도(exponential complexity)] 는 Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.

솔직히 O(2N) 방식으로 설계할일은 아마 없을거라고 생각이 듭니다. 대표적으로 재귀 함수의 예시로 피보나치 수열 을 사용하는데, 아래와 같이 구현이 되는 형식이 O(2N) 방식입니다.

public class O1Test {


    public static void main(String[] args){
        O1Test o1Test = new O1Test();
        int n = 10; // 1~10

        String exit = o1Test.o2NTest(1000);
        System.out.println(exit);
    }
    public String o2NTest(int n){
        if(n <= 1){
            return "탈출이다!!!";
        }

        return o2NTest(n-1) + o2NTest(n-2);
    }
}

 

n을 1000정도로 두고 실행시키면 아에 heap 메모리가 부족하다는 에러가 발생합니다. 

 

---

이번 시간에는 시간복잡도의 개념과 Big-O 표기법에 대해서 알아봤습니다. 조금 부족한 부분이 LogN부분인데, 이 부분은 다음 포스팅에 조금 더 자세하게 다뤄보려 합니다.

감사합니다.