[코딩테스트] 코딩테스트에서의 시간 복잡도 활용

Do it! 알고리즘 코딩 테스트 자바 편
인프런 강좌를 기준으로 작성하였습니다.

 

알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다.  일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측합니다.

 

시간 복잡도 정의하기

실제 시간 복잡도를 정의하는 유형은 3가지입니다. 

• 빅-오메가 : 최선일 때(best case)의 연산 횟수
• 빅-세타 : 보통일 때(average case)의 연산 횟수 
• 빅-오 : 최악일 때(worst case)의 연산 횟수 

0~99 사이의 무작위값을 찾아 출력하는 코드입니다. 

빅-오메가의 경우 최선의 때 이므로 무작위값이 1일 경우이므로 시간 복잡도는 1입니다. 빅-세타의 경우 평균이므로 2/N 번, 빅-오는 최악의 경우인 99가 나올 때이므로 시간복잡도는 N 번입니다. 

public class timeComplexityEx1 {
  public static void main(String[] args){
    int findNumber = (int)(Math.random() * 100);
    for(int i = 0; i  < 100; i++){
      if(i == findNumber){
     	System.out.println(i);
      	break;
      }
    }
  }
}

 

코딩 테스트에서는 어떤 시간 복잡도 유형을 사용해야 될까?

코딩테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋습니다. 왜냐하면 코딩테스트는 테스트 케이스 1개만 보는 게 아니라. 본인이 짠 코드 기준 여러 개의 테스트 케이스를 모두 통과해야 합격이 됩니다. 그러므로 판단할 때는 최악일 때를 기준으로 해야 합니다. 

 

다음은 데이터 크기(N)의 증가에 따른 성능이 표기한 그래프입니다. 

 

빅-오 표기법의 시간 복잡도

다양한 시간복잡도가 있고 알고리즘마다 시간복잡도를 가지고 있습니다. 알고리즘마다 시간복잡도를 외우는 것이 아닌 원리에 따라 시간복잡도를 분석할 수 있어야 합니다.. 

 

결과적으로 코딩테스트에서 시간복잡도를 계산해야 되는 경우는 두 가지가 있습니다.

알고리즘 유형에 따른 시간복잡도와 내가 짠 코드의 시간복잡도를 계산할 수 있어야 합니다.

 

시간 복잡도 활용하기 

알고리즘 선택의 기준으로 사용하기

시작하기 앞서 버블 정렬과 병합 정렬의 시간 복잡도는 각각 O(n^2), O(nlogn)이라고 알고 있다고 가정합니다. 

 

수 정렬하기

 

시간제한 : 2초 

 

N개의 수가 주어졌을 때 이를 오름차순으로 구하는 프로그램을 작성하시오. 

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000 보다 작거나 같은 정수이다. 수는 중복되지 않는다.

예제 입력 1

5
5
2
3
4
1

예제 출력 1

1
2
3
4
5

 

해당 문제가 주어져 있을 때 시간제한이 2초이므로 이 조건을 만족하는 시간복잡도는 2억 번 이하의 연산 횟수로 문제를 해결해야 합니다.

 

따라서 문제에서 주어진 시간 시간과 데이터 크기를 활용해 어떤 정렬 알고리즘을 사용해야 할 것인지 판단할 수 있어야 합니다. 

 

연산 횟수 계산 방법 

연산 횟수 = 알고리즘 시간 복잡도 x 데이터의 크기

위 공식으로 각 알고리즘이 이 문제에 적합한지 판단해 봅시다. 

버블 정렬 = (1,000,000)^2 = 1,000,000,000,000 > 200,000,000  = 부적합 알고리즘 
병합 정렬 = 1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000 = 적합 알고리즘

이와 같이 제한 시간을 통한 시간 복잡도 연산 횟수를 구한 다음, 데이터의 크기를 단서로 사용해야 할 알고리즘을 추측해 볼 수 있습니다. 

 

시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용 가능합니다. 코딩테스트 문제를 풀다 보면 아는 문제라고 판단하고 로직을 작성하며 도출 값이 나왔지만 시간 초과가 나오는 경우를 발생할 수 있습니다. 그런 경우 코드를 개선해야 하는데 그때 필요한 것이 본인의 코드의 시간 복잡도를 도출해야 되는 것입니다.

 

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다. 
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

코드를 예로 확인해 봅시다. 

 

연산 횟수가 N인 경우 

public int solution(){
    int n = 10000;
    int cnt = 0;

    for(int i = 1; i <= n; i++){
    	cnt++;
    }

    return cnt;
}

연산 횟수가 3N인 경우

public int solution(){
    int n = 10000;
    int cnt = 0;

    for(int i = 1; i <= n; i++){
    	cnt++;
    }
    
    for(int i = 1; i <= n; i++){
    	cnt++;
    }
    
    for(int i = 1; i <= n; i++){
    	cnt++;
    }

    return cnt;
}

 

두 예제의 코드 연산 횟수는 3배 차이가 납니다. 큰 차이인 것 같지만 코딩 테스트에서는 일반적으로 상수를 무시하므로 두 코드 모두 시간 복잡도 O(n)으로 같습니다.

 

다음은 중첩된 반복문에 대한 예제 코드를 확인해봅시다. 

 

연산 횟수가 N^2인 경우 

public int solution(){
    int n = 10000;
    int cnt = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
        	cnt++;
         }
    }

    return cnt;
}

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이 코드에서는 이중 for 문이 전체 코드의 시간 복잡도 기준이 됩니다. 이 말이 무슨 말이냐면 위의 코드의 일반 for 문이 10개 더 있다 하더라도 도출 원리에 따라 시간 복잡도는 변화 없이 N^2으로 유지됩니다.