[코딩테스트] 어떤 알고리즘을 선택해야할까

알고리즘 선택 기준이 되는 시간복잡도

알고리즘의 성능

좋은 알고리즘이란 무엇일까? 상황에 따라 좋은 알고리즘에 대한 정의가 달라지겠지만 일반적으로 좋은 알고리즘이란 성능이 좋은 알고리즘이라고 할 수 있다. 그렇다면 알고리즘의 성능을 평가할 수 있는 지표는 무엇이 있을까?

 

알고리즘 성능을 평가할 수 있는 지표는 공간과 시간이 있다. 

• 이 알고리즘이 수행하는데 얼마나 적은 메모리 공간을 차지하는가? - 공간 복잡도
• 이 알고리즘이 수행하는데 얼마나 빠른가? - 시간 복잡도

현대 기술이 발전과 함께 메모리 성능 발전도 이뤄지게 되었고, 따라서 상대적으로 성능 평가 지표 중 하나인 공간복잡도에 대한 중요성이 낮아졌다. 따라서 시간 복잡도(=얼마나 빠른가?)가 더 중요한 지표가 되었다.

 

그렇다면 알고리즘이 얼마나 빠른지, 즉 시간복잡도는 어떻게 알 수 있을까? 시간 복잡도는 알고리즘이 사용하는 연산횟수를 통해 알 수 있다. 일반적으로 1억번 연산에 1초가 걸린다. 만약 3억번의 연산을 하는 알고리즘이 있다면 이 알고리즘이 시작하고 끝날라면 3초가 걸릴 것이다.

 

시간복잡도 표기에는 3가지 종류가 있다.

• 빅-오메가: 최선(best case)일 때 연산 횟수를 나타내는 표기법
• 빅-세타: 보통(average case)일 때 연산 횟수를 나타내는 표기법
• 빅-오(O(n)): 최악(worst case)일 때 연산횟수를 나타내는 표기법

물론 보통일 때를 기준으로 해서 성능을 표기하면 좋겠지만, 실제로 보통일 때의 시간복잡도를 구하는 과정은 복잡하고 어렵다. 따라서 최선일 때와 최악일 때 중 하나를 선택해야 한다. 일반적으로 프로그램이 안정적이라면 최악의 상황에서도 기본적으로 요구되는 성능을 유지해야 한다. 또한 코딩테스트에서 10개의 테스트 케이스 중에서 1개만 틀려도 정답이 아니게 된다. 따라서 모든 케이스에 통과하려면 최악의 상황을 가정하고 모든 테스트케이스에 통과하려고 노력해야한다. 따라서 빅-오 표기법을 자주 사용한다.

 

이해를 하기 위해 아래와 메서드의 시간복잡도를 1.빅-오메가 2.빅-세타 3.빅-오로 표기한다면 각각 얼마일까?

 

public static void main(String[] args) {
	// 0~99의 범위에서 무작위 값을 찾아 출력하는 메소드
    int findNumber = (int)(Math.random() * 100);	// 0~99
    for(int i=0; i<100; i++) {
    	if(i == findNumber) {
            System.out.println("찾았습니다");
            break;
        }
    }
}

• 빅-오메가의 시간복잡도: 1(찾는 값이 1이였을 때)
• 빅-세타의 시간복잡도: 계산하기 어려움
• 빅-오의 시간복잡도: N번(찾는 값이 99였을 때)

다음과 같이 구할 수 있다. 참고로 여기서 N은 데이터의 크기다.

 

두 알고리즘의 성능차이 예시

더 이해를 돕기 위해 예시를 가져왔다. 어떤 데이터 집합을 정렬하는 알고리즘에도 여러가지가 있다. 이러한 여러가지 알고리즘 중 시간 복잡도를 기준으로 사용할 알고리즘을 선택할 수 있다.

 

버블 정렬의 경우 시간복잡도가 O(n^2)이다. 반면 병합 정렬의 시간복잡도는 O(nlogn)이다. 위 사실을 알고 있다고 가정하고 문제를 풀어보겠다.

 

백준 2750번 문제

위의 문제는 N개의 숫자가 주어졌을 때 숫자들을 오름차순으로 정렬하는 문제다. 위 예시에서는 데이터 크기가 1<=N<=1,000이지만

1<=N<=100,000로 바꾸어 생각해보자.

 

데이터의 크기가 최대 100,000이 될 수 있다. 만약 버블 정렬 알고리즘을 사용한다면 최악의 경우 100,000^2번 연산을 해야한다. 반면 병합 정렬 알고리즘을 사용한다면 100,000*log(100,000)이 될 것이다. 계산해보면 다음과 같다.

 

• 연산횟수 = 시간 복잡도 * 데이터의 크기(N)
  • 버블 정렬 = 100,000^2 = 10,000,000,000 = 100억 = 100초 
  • 병합 정렬 = 100,000log(100,000) = 약500,000  = 0.005초

위 문제를 보면 제한 시간이 2초이다. 즉 연산횟수가 2억번 이하여야 된다는 말이다. 따라서 버블 정렬로 한다면 시간초과 나고 병합 정렬로 문제를 풀어야 함을 알 수 있다. 따라서 문제에서 주어지는 데이터의 크기(N)와 사용할 알고리즘의 시간복잡도를 곱해서 연산횟수를 구해보고 시간 안에 문제를 풀 수 있는지 확인하는 게 좋다.