[Algorithm] 프로그래밍 문제 접근법 - 빅 오 분석법

• 풀이 분석
  • 빅 오 분석
  • 빅 오 분석법의 원리
  • 최선, 평균, 최악 케이스
  • 빅 오 분석법을 적용하는 방법
  • 어떤 알고리즘이 나을까?
  • 메모리 용량 분석
• Reference

이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

풀이 분석

• 문제에 대한 답을 내놓고 나면 구현의 효율성에 대한 질문이 나오는 경우가 많다.

• 지원자가 구현한 풀이 방법과 다른 풀이 방법을 제시하고 그 둘의 장단점을 비교한다거나

• 어떤 상황에서 어떤 구현 방법이 더 유리할지를 물어보는 경우를 많이 접하게 될 것이다.

• 그리고 메모리 또는 공간 사용에 관한 질문도 자주 나오는 편인데, 특히 재귀 호출을 사요할 경우 이런 질문이 많이 나온다.

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

• 빅 오 분석법은 입력 값의 개수에 따라 알고리즘이 수행되는 데 걸리는 시간을 바탕으로 알고리즘의 효율성을 평가하는 실행 시간 분석법이다.

• 알고리즘의 상대적인 효율성을 간단하게 따져보는 데는 유용하다.

빅 오 분석

• 음이 아닌 수가 저장된 배열에서 최대값을 구하는 간단한 함수를 구현하는 방법에는 최소 두 가지가 있다.

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

• 코드로 구현하면 다음과 같다.

/* n개의 음이 아닌 정수의 배열에서 가장 큰 값 반환 */
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;
}

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

• 코드로 구현하면 다음과 같다.

/* n개의 음이 아닌 정수의 배열에서 가장 큰 값 반환 */
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; j < n; j++) {
            /* 더 큰 값이 있는지 확인 */
            if(array[j] > array[i])
                isMax = false; /* array[i]가 최대값이 아님 */
        }
        /* isMax가 참이면 더 큰 값이 없는 것으로 array[i]가 최대값이다 */
        if(isMax) break;
    }
    
    return array[i];
}

• 이 두 함수는 모두 최대값을 제대로 반환한다.

• 그런데 어느 쪽이 더 효율적인지 알기 위해서는 빅 오 분석법을 활용하면 된다.

• 빅 오 분석법을 활용하면 서로 다른 알고리즘의 상대적인 성능을 예측하고 비교해볼 수 있다.

빅 오 분석법의 원리

• 빅 오 분석법에서는 입력 값의 크기(개수) 를 n개라고 가정한다.

• 문제에 따라 n이 연결 리스트의 노드 개수 또는 특정 자료형의 비트 수 또는 해시 테이블에 들어 있는 항목의 개수일 수 도 있는 등 다양한 값들을 입력 값의 크기 n으로 쓰일 수 있다.

• 이때 연산이라는 말은 일반적으로 입력된 값에 상수를 더하거나 새로운 입력 아이템을 만드거나 입력 값을 삭제하는 작업을 통틀어서 표현한 것이다.

• 빅 오 분석법에서는 이런 모든 연산을 동등하게 본다.

• CompareToMax와 CompareToAll에서는 모두 배열에 있는 값을 다른 값과 비교하는 작업을 연산이라고 생각할 수 있다.

CompareToMax : 배열의 모든 원소를 하나씩 확인하면서 가장 큰 수를 계속 기록한 다음, 확인이 끝나고 나면 그 값을 반환하는 메서드

• CompareToMax에서는 각 배열 원소와 최대값을 한 번 씩 비교했으므로 총 n번의 확인 작업이 수행된다.

• 이런 상황을 O(n)이라고 표현하며 선형 시간 내에 수행된다고 말하기도 한다.

• 이 경우에는 알고리즘을 실행 시키는 데 걸리는 시간이 입력된 항목의 개수에 비례하여 선형적으로 증가한다.

• 빅 오 분석을 할 때는 n이 매우 큰 경우의 실행 시간인 점근적인 실행 시간만 따진다.

• 따라서 빅 오 분석을 할 때는 최고차항 즉, n이 매우 커질 때 가장 큰 항만 남기고 다른 항은 무시한다.

• 지금 다루고 있는 예에는 n이 최고차항이기 때문에 CompareToMax 함수는 O(n) 이 된다.

CompareToAll : 각 값을 다른 모든 값과 비교하는 방법이다. 다른 모든 값이 주어진 값 이하라면 그 값을 반환하는 메서드

• CompareToAll 메서드에서는 일단 최대 원소가 배열의 맨 뒤에 있다고 가정했다.

• 이런 경우에는 n개의 원소를 n개의 다른 원소하고 비교해야 한다.

• 따라서 nxn번 확인을 해야 하므로 이 알고리즘은 O(n^2) 알고리즘이다.

• 즉, 배열이 커짐에 따라서 CompareToAll에서의 비교 횟수가 CompareToMax의 비교 횟수보다 훨씬 커질 것임을 알 수 있다.

최선, 평균, 최악 케이스

• 여기에서 CompareToAll을 분석할 때 최대값이 맨 뒤에 있다고 가정했기 때문에 불공평한 것이라고 생각할 수 도 있다.

• 이런 문제 때문에 최선 케이스, 평균 케이스, 최악 케이스의 실행 시간을 따져봐야 하는 문제가 생긴다.

• 위의 CompareToAll을 분석할 때는 최악의 시나리오를 가정했다.

• 하지만 평균을 따져서 최대값이 가운데 있는 경우를 생각해보자.

• 최대값이 중간에 있다면 절반만 n번씩 확인하면 된다. 그러면 n(n/2)이므로 실행 시간은 O(n^2/2) 가 된다.

• 하지만 각 값을 실제로 확인하는 데 걸리는 시간은 코드에 의해 생성되는 기계어와 CPU에서 그러한 명령들을 수행하는 데 걸리는 시간에 의해 크게 좌우된다.

• 따라서 1/2이라는 숫자가 그리 큰 의미를 가진다고 볼 수 없다.

• 빅 오 분석법에서는 모든 상수 인자들을 빼 버리기 때문에 평균 케이스와 최악 케이스 모두 크게 다를 바가 없다.

• 여전히 O(n^2) 일 뿐이다.

• CompareToAll의 최선 케이스의 실행 시간은 최대값이 배열의 맨 앞에 있는 경우다.

• 이때는 최대값을 다른 모든 값들과 딱 한 번만 비교하면 되기 때문에 실행 시간은 O(n) 이 된다.

• CompareToMaax에서는 최선, 평균, 최악 케이스 모두 실행 시간이 같으므로 항상 O(n) 이다.

• 면접관에게 어떤 시나리오에 가장 중점을 둬야 할지 물어보는 것도 한 방법이다.

• 문제 자체에 이에 대한 언급이 들어 있는 경우도 있다.

빅 오 분석법을 적용하는 방법

• 일반적으로 빅 오 실행 시간 분석은 다음과 같은 방법으로 하면 된다.

1. 입력 값이 무엇인지 확인하고 어떤 것을 n으로 놓아야 할지 결정한다.
2. 알고리즘에서 수행해야할 연산 횟수를 n의 식으로 표현한다.
3. 차수가 제일 높은 항만 남긴다.
4. 모든 상수 인수를 없앤다.

• 면접에서 다루는 알고리즘의 경우에는 입력 데이터의 크기에 의존하는 연산을 제대로 파악하면 빅 오 분석법이 그리 까다롭지는 않다.

어떤 알고리즘이 나을까?

• 가장 빠른 것은 O(1) 알고리즘으로, 보통 상수 실행 시간이라고 부른다.

• 알고리즘 성능은 대부분 입력 크기인 n에 따라 변한다.

• 성능이 가장 좋은 것부터 나쁜 것까지 순서대로 알고리즘 종류를 나열하면 다음과 같다.

  • O(log n) : 실행 시간이 입력 크기의 로그에 비례해서 늘어나는 알고리즘을 로그 알고리즘이라고 부른다.

  • O(n) : 실행 시간에 입력 크기에 비례하는 알고리즘을 선형 알고리즘이라고 부른다.

  • O(n log n) : 준선형 알고리즘이라 부르며 선형 알고리즘과 다항식 알고리즘의 중간쯤 된다.

  • O(n^2) : 입력 크기가 늘어나면 실행 시간이 빠르게 늘어나며, 다항식 알고리즘이라고 부른다.

  • O(2^n) : 다항식 알고리즘보다 실행 시간이 빠르게 늘어나며 지수 알고리즘이라고 부른다.

  • O(n!) : 가장 느린 알고리즘으로, n이 작아도 금방 거의 쓰기 힘든 수준으로 느려지며, 팩토리얼 알고리즘이라고 부른다.

• n이 커지면 실행 시간 차이가 매우 두드러진다. ndl 10일 때 각 알고리즘의 실행 시간을 따져보자.

  • log 10 = 1

  • 10 = 10

  • 10 log 10 = 10

  • 10^2 = 100

  • 2^10 = 1,024

  • 10! = 3,628,800

• 준선형 알고리즘, 또는 그보다 더 빠른 알고리즘(로그 알고리즘)을 찾으면 애플리케이션 성능을 크게 향상시킬 수 있다.

메모리 용량 분석

• 성능을 따지는 데 실행 시간 분석 말고도 중요한 게 메모리 용량이다.

• 애플리케이션의 메모리 용량 또는 알고리즘의 메모리 용량은 앞에서 설명한 빅 오 분석법을 썼던 것과 유사하게 필요한 메모리 사용량을 입력 크기 n의 식으로 표현하는 접근법을 사용해야 한다.

• 입력 크기에 따라 필요한 연산 횟수 대신 각 항목에 대해 필요한 저장 공간을 따져보면 된다.

• 면접관이 구현 방법의 메모리 사용량을 물어보는 경우는 실제 자료구조가 어떻게 구현되는지 제대로 이해하는 가를 알고자 하는 것이다.

Reference

프로그래밍 면접 이렇게 준비한다