알고리즘 분석(1)

박정훈·2021년 2월 7일
0

Algorithm

목록 보기
5/7

개관

어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법을 가리켜 알고리즘(algorithm)이라고 한다.
주어진 문제를 해결하는 한 가지 방법을 명료하게 써 놓은 것을 알고리즘이라고 한다. 주관적이거나 모호한 것은 알고리즘이라고 할 수 없다.

예를 들어 서울 신촌역에서 춘천에 간다고 하자.
다음과 같은 것은 정당한 알고리즘이다.

  1. 지하철 2호선을 타고 시청역으로 간다.
  2. 지하철 1호선으로 갈아타고 청량리역으로 간다.
  3. 경춘선을 타고, 춘천역에서 내린다.

반면 다음과 같은 것은 알고리즘이라고 할 수 없다.

  1. 강동구 쪽으로 가는 버스를 탄다.
  2. 동서울 버스 터미널 근처에서 온 것 같으면 내린다.
  3. 춘천 쪽으로 가는 버스를 타고, 한참 가다 내린다.

특히 컴퓨터과학에서 알고리즘이란 컴퓨터가 따라 할 수 있도록 자세히 설명한 과정을 나타낸다.
알고리즘은 문제를 해결하는 방법 그 자체를 가리키기 때문에, 완전히 달라 보이거나 다른 언어로 쓰인 프로그램이라고 해도 같은 원리에 따라 동작한다면 같은 알고리즘을 사용한다고 할 수 있다. 소스 코드들은 알고리즘을 구현하는 한 방법일 뿐이며, 소스 코드가 알고리즘을 정의하는 것이 아니다.

알고리즘을 평가하는 두 가지 큰 기준은 알고리즘이 사용하는 시간과 공간이다.

  • 시간
    알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작한다는 것이다.
  • 공간
    알고리즘이 적은 공간을 사용한다는 것은 더 적은 용량의 메모리를 사용한다는 이야기이다. 알고리즘이 이론적으로 아무리 빠르더라도 너무 많은 메모리 공간을 요구한다면 수행할 수 없다.

위의 두 기준은 서로 상충하는 경우가 많다. 물론 더 빠르면서 메모리도 더 적게 사용하는 알고리즘이 있을 수는 있지만, 메모리 사용량을 희생해 속도를 늘리거나, 속도를 희생해 메모리 사용량을 줄인 알고리즘들이 훨씬 많다.

알고리즘의 시간 복잡도 분석

도입

좀더 빠른 알고리즘을 만들기 위해 가장 먼저 해야 할 일은 바로 알고리즘의 속도를 어떻게 측정할지를 정하는 것이다.
두 알고리즘의 속도를 비교하는 가장 직관적인 방법은 각각을 프로그램으로 구현한 뒤 같은 입력에 대해 두 프로그램의 수행 시간을 측정하는 것이다. 하지만 프로그램의 실행 시간은 알고리즘의 속도를 일반적으로 이야기하는 기준이 되기에는 부적합하다. 가장 큰 이유는 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어는 물론이고 운영체제, 컴파일러까지 수많은 요소에 의해 바뀔 수 있기 때문이다. 더 빠르게 동작하던 코드가 다른 컴퓨터에서는 더 느리게 동작하는 일은 얼마든지 있을 수 있는 일이다. 심지어 이런 외적 요인을 전부 통일하더라도 어떤 문자열 구현을 사용했는지, 함수 인자를 어떻게 넘겼는지 등의 사소한 문제에 따라 프로그램의 최종 수행 시간은 크게 달라질 수 있다.
두 번째 이유는 프로그램의 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못한다는 것이다. 알고리즘은 언제나 같은 속도로 동작하는 것이 아니며, 입력의 크기나 특성에 따라 수행 시간이 달라질 수 있다.

반복문이 지배한다.

한 가지 항목이 전체의 대소를 좌지우지 하는 것을 지배한다(dominate)고 표현한다.
알고리즘의 수행시간을 지배하는 것은 반복문이다.
입력의 크기가 작을 때는 반복문외의 다른 부분들이 갖는 비중이 클 수 있지만, 입력의 크기가 커지면 커질수록 반복문이 알고리즘의 수행 시간을 지배하게 된다. 따라서 대개 우리는 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정한다. 이때 반복문의 수행 횟수는 입력의 크기에 대한 함수로 표현한다.

주어진 배열에서 가장 많이 등장하는 수를 찾는 코드를 예로 보자.
이 알고리즘의 수행 시간은 배열의 크기 N에 따라 변한다. N번 수행되는 반복문이 두 개 겹쳐져 있으므로, 반복문의 가장 안쪽은 항상 N^2번 실행된다. 따라서 이 알고리즘의 수행 시간은 N^2이다.

// 주어진 배열 A에서 가장 많이 등장하는 숫자를 반환한다.
// 만약 두 가지 이상 있을 경우 아무것이나 반환한다.
int majority1(const vector<int>& A) {
	int N = A.size();
    	int majority = -1, majorityCount = 0;
        for (int i = 0; i < N; ++i) {
        	// A에 등장하는 A[i]의 수를 센다.
            	int V = A[i], count = 0;
                for (int j = 0; j < N; ++j) {
                	if(A[j] == V) {
                    		++count;
                    	}
                }
        	// 지금까지 본 최대 빈도보다 많이 출현했다면 답을 갱신한다.
    	    	if (count > majorityCount) {
       	 		majorityCount = count;
       	     		majority = V;
             	}
        }
        return majority;
}

입력으로 주어지는 숫자들이 사실 100점 만점으로 주어지는 시험 점수 였다고 하자. 이처럼 숫자의 범위가 작다면 배열을 이용해 각 숫자가 등장하는 횟수를 쉽게 셀 수 있다. 그리고 마지막에 빈도수 배열을 순회하면서 최대치의 위치를 찾으면 된다. 이것을 구현한 것이 다음 코드이다. 이 코드에는 반복문이 두 개 있다. 하나는 N번 수행되고, 다른 하나는 100번 수행되므로 전체 반복문의 수행 횟수는 N+100이 된다. 그런데 N이 커지면 커질수록 사실 후자의 반복문은 수행 시간에서 차지하는 비중이 줄어들게 된다. 따라서 궁극적으로 아래의 알고리즘의 수행 시간은 N이 된다.

// A의 각 우너소가 0부터 100 사이의 값일 경우 가장 많이 등장하는 숫자를 반환한다.
int majority2(const vector<int>& A) {
	int N = A.size();
    	vector<int> count(101, 0);
        for (int i = 0; i < N; ++i) {
        	count[A[i]]++;
        }
        // 지금까지 확인한 숫자 중 빈도수가 제일 큰 것을 majority에 저장한다.
        int majority = 0;
        for (int i = 1; i <= 100; ++i) {
        	if (count[i] > count[majority]) {
           	 	majority = i;
            	}
        }
        return (majority);
}

알고리즘의 수행 시간은 매우 종류가 다양하지만 크게 몇 가지 분류로 나눌 수 있다.

선형 시간 알고리즘

이동 평균(moving average)은 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준이다. 시간에 따라 관찰된 숫자들이 주어질 때 M-이동 편귱은 마지막 M개의 관찰 값의 평균으로 정의된다. 따라서 새 관찰 값이 나오면 M-이동 평균은 새 관찰 값을 포함하도록 바뀐다.
이 알고리즘에서 더 빠른 프로그램을 짜는 중요한 아이디어는 중복된 계산을 없애는 것이다.
코드의 수행 시간이 N에 정비례하는 코드들이 있다. 입력의 크기에 대비해 걸리는 시간을 그래프로 그려 보면 정확히 직선이 된다. 그래서 이런 알고리즘을 선형 시간(linear time)알고리즘이라고 부른다. 선형 시간에 실행되는 알고리즘은 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다. 주어진 입력을 최소한 한 번씩 쳐다보기라도 하려면 선형 시간이 걸릴 수 밖에 없기 때문이다.

출처

  • 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략
profile
정팔입니다.

0개의 댓글