프로그래밍 면접 이렇게 준비한다. - 2. 빅 오 분석법 원리

5. 풀이 분석

  문제에 대한 답을 내놓고 나면 구현의 효율성에 대한 질문이 나오는 경우가 많다. 지원자가 구현한 풀이 방법과 다른 풀이 방법을 제시하고 그 둘의 장단점을 비교한다거나 어떤 상황에서 어떤 구현 방법이 더 유리할지를 물어보는 경우를 많이 접하게 될 것이다. 그리고 메모리 또는 공간 사용에 관한 질문도 자주 나오는 편인데, 특히 재귀 호출을 사용할 경우 이런 질문이 많이 나온다.

  빅 오 분석법(big-O analysis) 을 제대로 이해하고 있다면 면접관에게 좋은 인상을 남기는 데 크게 도움이 된다.

 예) 음이 아닌 수가 저장된 배열에서 최대값을 구하는 간단한 함수를 생각해 보자. 

  첫 번째 방법은 배열의 모든 원소를 하나씩 환인하면서 가장 큰 수를 계속 기록한 다음, 확인이 끝나고 나면 그 값을 반환하는 방법이다.

int CompareToMax(int array[], int n){
	int curMax, i;
	/* 배열에 적어도 하나 이상의 원소가 있는지 확인 */
	if(n <= 0)
		return -1;
	/* 지금까지 확인한 값 중 최대값을 저장할 변수에 배열의 첫 번째 값 저장 */
	curMax = array[0];

	/* 모든 수를 최대값과 비교함 */
	for (i=1; i<n; i++){
		if(array[i]>curMax){
			curMax = array[i];
		}
	return curMax;
	}
}

  두 번째 방법은 각 값을 다른 모든 값과 비교하는 방법이다. 다른 모든 값이 주어진 값 이하라면 그 값이 최대값이 된다.

int CompareToAll(int array[], int n){
	int i, j;
	bool isMax;
	
	/* 배열에 적어도 하나 이상의 원소가 있는지 확인 */
	if(n <= 0)
		return -1;
	
	for (i=n-1; i>0 ; i--){
		isMax = true;
		for(j=0; jarray[i])
				isMax=false; /* array[i]가 최대값이 아님 */
		}
		/* isMax가 참이면 더 큰 값이 없는 것이므로 array[i]가 최대값이다. */
		if(isMax) break;
	}
	return array[i];
}

이 두 함수는 모두 최대값을 제대로 반환한다. 그런데 어느 쪽이 더 효율적일까? 벤치마킹을 해 볼 수 있겠지만, 모든 방법을 구현해보고 벤치마킹을 하는 것은 비효율적이기도 하거니와 실용적인 면에서도 별로 좋지 않다. 직접 구현해보지 않아도 알고리즘의 성능을 예측할 수 있어야한다. 

6. 빅 오 분석법의 원리

  빅 오 분석법에서는 입력 값의 크기(개수)를 n개라고 가정한다. 위의 예에서는 배열에 있는 원소의 개수가 바로 n이 된다. 문제에 따라 n이 연결 리스트의 노드 개수를 나타낼 수도 있고, 특정 자료형의 비트 수일수도 있고, 해시 테이블에 들어있는 항목의 개수일 수도 있는 등 다양한 값들을 입력 값의 크기 n으로 쓰일 수 있다. 

  입력된 값에 상수를 더한다거나 새로운 입력 아이템을 만든다거나 입력 값을 삭제한다거나 하는 작업을 통틀어서 "확인"한다고 표현할 수 있을 것이다. 빅 오 분석법에서는 이런 모든 작업들을 동등하게 본다.지금 예로 들고 있는 CompareToMax와 CompareToAll 에서는 모두 배열에 있는 값을 다른 값과 비교하는 작업을 확인하는 것으로 생각하면 된다.

[사진] 빅 오 그래프

  CompareToMax에서는 각 배열 원소와 최대값을 한 번씩 비교했다. 따라서 n개의 입력된 항목이 각각 한 번씩 확인되기 때문에 총 n번의 확인 작업이 수행된다. 이런 상황을 O(n)이라고 표현하며 선형 시간 내에 수행된다고 말하기도 한다. 이 경우에는 알고리즘을 실행시키는 데 걸리는 시간이 입력된 항목의 개수에 선형적으로 비례하여 증가한다. 

  잘 보면 각 원소를 한 번씩 확인하는 것 외에 처음에 배열이 비어있지 않은지 확인하는 부분과 curMax 변수의 값을 초기화하는 부분도 있다. 그 부분까지 감안하여 O(n+2) 함수라고 불러야 더 정확하다고 할 수 있다. n이 무한대로 올라가면 n이나 n+2나 크게 차이가 나지 않기 때문에 2와 같은 상수항은 그냥 무시해도 무방하다. 마찬가지로 어떤 알고리즘의 실행 시간이 이나 별 차이가 나지 않게 된다. 따라서 빅 오를 분석할 때는 최고차항 즉, n이 매우 커질 때 가장 큰 항만 남기고 다른 항은 다 무시한다. 지금 다루고 있는 예에서는 n이 최고차항이기 때문에 CompareToMax함수는 O(n)이 된다.

  CompareToAll은 최대 원소가 배열의 맨 뒤에 있다고 가정해보자. 이런 경우에는 n개의 원소를 n개의 다른 원소하고 비교해야 한다. 따라서 nxn번 확인을 해야 하므로 이 알고리즘은 O()알고리즘이다. 

  이렇게 분석을 하고 나면 CompareToMax는 O(n) 알고리즘이고 CompareToAll은 O()알고리즘임을 알 수 있다. 원소 개수가 30,000개라면, 실제로 벤치마크를 해 본 결과 CompareToMax알고리즘은 0.01초도 안 걸려서 실행이 끝났지만 CompareToAll 알고리즘은 23.99초가 걸렸다.