알고리즘 기초 - 1 [알고리즘 정의, 평가, 분석, 빅오 표기법]

목차

알고리즘의 역할

주어진 조건에서, 어떤 절차와 방법으로 문제를 해결할 수 있을까?

알고리즘의 정의

• "어떤 문제를 해결하기 위한 절차나 방법"

  • 어떤 방식이더라도, 결국 문제를 해결할 수 있는 절차와 방법이 중요하다.
  • 다만, 해결 방식에서의 효율성[시공간적], 안정성[Race Condition]등을 생각해야 한다.

• 알고리즘의 조건

  • 입력 : 0 또는 그 이상의 외부에서 제공된 자료가 존재
  • 출력 : 최소 1개 이상의 결과
  • 명확성 : 각 단계의 애매함 없는 명확한 과정 구성
  • 유한성 : 유한한 수의 단계 수행 후, 문제가 해결되어 종료
  • 효율성 : 모든 연산은 명백하게 실행할 수 있음을 검증

알고리즘 평가

알고리즘은 어떤 조건 condition이 중요하냐에 따라 효율적인 문제 해결 방법이 달라진다. 따라서 여러 정렬 알고리즘이 있다고 하더라도, 해당 알고리즘이 적용될 조건이 어떠하냐에 따라서 가장 효율적인 정렬 알고리즘이 결정된다.

• 알고리즘 평가의 세 가지 효율성 요소
  • 시간
  • 공간
  • 코드

시간의 효율성

컴퓨터에서 실행되는 프로그램은 주어진 조건에 맞춰 문제를 해결하는데 무한대의 시간을 사용할 수 없다. 또한 여러 경우에서 한 가지 간단한 문제를 해결하는데에 1시간 이상을 소요하는 것은 바람직하지 않다. 되도록 빠른 시간 안에 가장 효율적인 해결책을 찾는 것이 좋은 알고리즘이다.

공간의 효율성

공간의 효율성은 컴퓨터에서 사용하는 메모리와 관계가 있다. 물리적인 메모리 가격이 저렴해졌다고, 무한대로 메모리를 사용할 수 있다는 것이 아니다. 운영체제에서 여러 개의 프로그램들이 하나의 물리적인 메모리를 공유함으로 메모리를 효율적으로 관리하고 사용하는 것이 중요하다.

• 예) 무분별한 전역변수 사용
  • 프로그램 시작부터 끝까지 메모리 공간을 점유함으로 여러 곳에서 공유하는 자원이 아닌 이상 지역 변수 사용을 권장

코드의 효율성

프로그래머 입장에서 보는 코드의 효율성과 컴퓨터 입장에서 보는 코드의 효율성이 있다.

• 프로그래머 입장에서의 코드 효율성

  • 가독성
    • 코드 작성 후 시간이 지난 후, 자신이나 다른 사람이 다시 보더라도 코드를 쉽게 수정가능해야한다.

• 컴퓨터 입장에서의 코드 효율성

  • 컴파일러와 하드웨어에 좀 더 최적화된 코드
    • unsigned int, int, byte 등의 타입을 지정할 때, 사용하는 수의 범위에 따른 더욱 효율적인 number type 지정.
    • 재귀 호출의 경우, 프로그래머 입장에서는 코드 길이가 간결해지고 이해하는데 명확하다고 생각되지만, 실제 컴퓨터 입장에서 재귀 호출을 위한 여러 부가 작업(함수 호출, 반환 등)의 오버헤드가 발생되어 비효율적.

수학적 배경

알고리즘의 수학적 표기 방법

개발한 알고리즘을 다른 알고리즘들과 비교할 때 성능이 좋다는 것을 증명해야 한다.
하지만, 알고리즘의 성능은 적용된 시스템, 컴파일러의 종류, 사용환경에 따라 많은 영향을 받으므로 단순한 시간 측정이나 메모리 사용 여부만으로 알고리즘의 효율성 판단을 하기엔 쉽지 않다.
또한, 정렬, 검색, 압축, 암호화 등의 복잡한 알고리즘의 경우에는 최선, 혹은 최악의 경우에 따른 성능 평가가 달라진다.

• 확실한 알고리즘의 성능 평가 방법
  • 수학적 증명 방법
    • 실수를 다루는 함수 T(N)과 f(N)이 있음을 가정
      1. T(N)≤cf(N), N≥N₁, 이라는 두 조건을 만족하는 상수 c와 N₁이 존재한다면 T(N)=O(f(N))이라고 한다.
      2. T(N)≥cf(N), N≥N₁ 이라는 두 조건을 만족하는 상수 c와 N₁이 존재한다면 T(N)=Ω(f(N))이라고 한다.
      3. T(N)=O(f(N))이라는 조건을 만족하는 상수 c₁과 N₁이 존재하고 T(N)=Ω(f(N))이라는 조건을 만족하는 상수 C₂와 N₁이 존재할 때 T(N)=Θ(f(N))이라고 한다.

(1.) 의 경우

빅오(O) 표기법 (Big-O Notation)

• 알고리즘의 성능 평가 중 가장 많이 사용하는 방법
  • 최고의 성능과 최악의 성능 중 최악의 성능을 측정하는 방법
    • 최악 성능 평가 이유 : 이 정도 성능 이상은 보장

(2.)의 경우

오메가(Ω) 표기법(Omega Notation)

• 알고리즘의 성능이 최고인 경우를 측정하는 표기법

(3.)의 경우

세타(Θ) 표기법(Theta Notation)

• 정확한 알고리즘 성능을 측정하는 방법
  • 가장 좋은 성능 표기 방법이지만, 실제 알고리즘의 성능을 표기하기는 어렵다.

따라서 가장 많이 사용하는 측정 방법은 빅오 표기법이다.

• 빅오 표기법의 사용
  • 알고리즘 분석하기 전 몇 가지 가정이 필요
    1. 헤더 파일은 알고리즘의 성능에 영향을 주지 않는다.
    2. 함수 진입과 함수 반환은 알고리즘의 성능에 영향을 주지 않는다.
    3. 프로그램은 첫 번째 행부터 마지막 행까지 차례로 실행된다.

# include <stdio.h>

int main(int argc, char *argv[])
{
    int Sum = 0;
    int i;

    for(i=1; i<=100; i++) {
        Sum = Sum +1;
    }

    printf("1부터 100까지의 합: %d\n", Sum);
}

위의 프로그램에서 1행의 헤더 파일과, 3행, 4행은 알고리즘 성능에 영향을 주지 않는다.
프로그램 시작인 int Sum == 0; 줄부터 printf("1부터 100까지의 합: %d\n",Sum); 까지 실행 횟수를 계산하면 다음 표와 같다.

알고리즘 성능에 영향을 주는 코드	실행 횟수
int Sum = 0;	1회
int i;	1회
for(i=1; i<=100; i++)	101회
Sum=Sum+i;	100회
printf("...")	1회
합계	204회

위 표의 실행 횟수를 빅오 표기법으로 나타내면 다음과 같다.
O(204) = O(1)

204회가 실행되더라도 204라는 상수의 존재는 알고리즘의 성능에 아무런 영향을 끼치지 못한다.
따라서 빅오 표기법으로 위 알고리즘을 나타내면 O(1)이 된다.
O(1)은 알고리즘의 성능이 고정적이라는 의미가 되므로 1부터 100까지의 합을 구하는 경우라면 위 알고리즘을 최적화 하더라도 알고리즘의 성능에는 거의 영향을 주지 않는다.

그렇다면 1부터 N가지 1을 계속해서 더하는 경우를 생각한다면 어떻게 될까

for(i=1; i<=N; i++) {
        Sum = Sum +1;
}

N=1, 1회
N=100, 100회
N의 값이 얼마인가에 따라서 for문의 반복횟수가 결정되고, for문의 반복횟수는 결국 알고리즘의 성능에 가장 큰 영향을 미치는 요소가 되는 것이다.

C + ⋯ + C (N times) = O(C x N) = O(N), {C는 상수}

위와 같이 빅오 표기법은 처리해야 할 데이터 양에 대한 실행 시간을 수학적으로 계산하여 알고리즘의 성능을 평가한다.

• 빅오 표기법의 종류

  • O(1)

    • 처리해야 할 데이터양과 상관 없이 항상 일정한 실행 시간을 갖는 알고리즘을 의미

  • O(logN)

    • 처리해야 할 데이터 양이 증가할수록 실행 시간도 약간씩 증가하는 알고리즘을 의미. 단, 실행 시간의 증가 폭이 logN 그래프를 갖기 때문에 급격하게 증가하지는 않는다. 일반적으로 효율이 높은 검색 알고리즘의 성능이 이에 해당한다.

  • O(N)

    • 처리해야 할 데이터양과 비례해 실행 시간도 증가하는 경우

  • O(NlogN)

    • 처리해야 할 데이터양보다 실행 시간이 좀 더 빠르게 증가한다. 일반적으로 효율이 높은 정렬 알고리즘의 성능이 이에 해당한다.

  • O(N²)

    • 보통 반복문이 두 번 중첩된 경우의 알고리즘
      • 처리해야 할 데이터 양이 증가할수록 제곱만큼의 실행 시간이 소요

  • O(N³)

    • 반복문이 세 번 중첩된 경우
      • 위의 경우와 마찬가지로 데이터 양이 증가할수록 세제곱만큼의 실행 시간이 소요

  • O(2ⁿ)

    • 데이터양의 증가에 따라 2ⁿ 실행 시간이 증가하는 알고리즘

분석의 대상

알고리즘의 성능을 평가하는 가장 현실적인 항목은 시간의 효율성 부분이다.
대입 연산이나, 기타 C에서 제공하는 연산자를 이용한 단순 연산 등은 알고리즘의 성능에 그다지 영향을 미치지 못한다는 점을 기억하고, 알고리즘의 성능을 좌우하는 반복문을 빅오 표기법으로 어떻게 나타내는지 살펴보자.

알고리즘 안에 있는 반복문의 구성과 개수 등을 세밀하게 살펴보자.

반복문은 최대 반복 횟수로 계산한다.

1부터 100까지의 수를 더하는 반복문이 있다고 가정할 때, 빅오 표기법에서는 아무리 큰 수라고 하더라도 상수인 경우는 무조건 O(1)이 된다.
만약 100이 아닌, N까지의 수를 더하는 경우 빅오 표기법은 O(N)이 된다.

중첩된 반복문은 중첩문 각각의 최대 반복 횟수를 곱해서 계산한다.

다음과 같이 2개의 for문이 중첩되어 있다고 가정할 때

    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            k++
        }
    }

위의 코드에서 중첩된 for문의 최대 반복 횟수를 곱해서 빅오 표기법으로 계산한다.

• 첫 번째 반복문의 최대 반복 횟수는 N이며
• 두 번째 반복문의 최대 반복 횟수도 N이므로
• O(N N) = *O(N²)**이 된다

반복문이 떨어져서 2개 이상 있는 경우 그중 가장 큰 값으로 계산한다.

    for(i=0; i<N; i++) {
        k++
    }

    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            k++
        }
    }

위 코드의 경우 각각 for문의 빅오 표기법은 O(N), O(N²)이 되므로 더 큰 차수인
O(N²)이 빅오 표기법으로 나타내어진다.

if~else 조건문은 알고리즘 성능에 큰 영향을 미치지 않는다.

프로그램에서 가장 빈번하게 사용되지만 if~else문은 프로그램 성능에 큰 영향을 미치지 않는다.

재귀 호출

재귀 호출을 사용해 팩토리얼(factorial) 연산을 실행하는 프로그램

    int Fact(int N)
    {
        if(N<=1)
            return 1;
        else
            return N * Fact(N-1);
    }

위의 코드에서 영향을 미치는 부분은 return N * Fact(N-1); 부분이다.
위 재귀 호출은

• N * (N-1) * Fact(N-2) = N * (N-1) * (N-2) * Fact(N -3) = N * (N-1) * ⋯ * 2 * 1
• 결국에는 1부터 N까지의 곱셈이고, 위 재귀 호출 역시 반복 횟수는 N번이라는 것이다.
• 이를 빅오표기법으로 나타내면 O(N)이다.

알고리즘 분석과 최적화

프로그램의 수학적 분석 예

알고리즘 성능에 제일 중요한 요소는 시간이고, 이는 곧 같은 기능을 실행하는데 실행 시간을 얼마나 줄일 수 있느냐라는 것이 해당 알고리즘이 얼마나 효율적인 알고리즘인지 판단하는 기준이 된다.

알고리즘 성능을 측정하는데에 시간을 재는 것과 같은 방법을 사용할 수 있겠지만 알고리즘에 따라 시간이 1달, 2달에 걸리는 것을 그때까지 측정할 수는 없는 노릇이다.
따라서, 성능 측정 방법 중 가장 빠르고 정확한 것이 수학적 분석이고, 수학적 분석에서 가장 많이 이용하는 것이 빅오 표기법 기반의 분석이다.

빅오 표기법을 이용한 프로그램의 수학적 분석 예

[문제] Array에 저장된 1부터 N까지의 요소 중 첫번째 요소부터 차례로 더했을 때의 합이 가장 큰 수를 찾아내는 부분 수열의 합을 구하는 프로그램

[조건] Array = [4, -1, 5, -2]
[결과] 4 -1 +5를 더했을 때의 값 8

#include <stdio.h>

int MaxSum(int);
void init(void);
int Array[100];

int MaxSum(int N)
{
    int Sum, Max, i, j, k;
    Sum = Max = 0;

    for(i=0; i<N; i++) {
        for(j=i; j<N; j++) {
            Sum = 0;

            for(k=1; k<j; j++)
                Sum = Array[k]

            if(Sum > Max)
                Max = Sum
        }
    }
    return Max;
}

void Init()
{
    int i;
    for(int i=0; i<100; i++)
        Array[i] = 100 -i
}

int main(int argc, char *argv[])
{
    int ret;
    Init();
    ret = MaxSum(10);

    printf("ret : %d\n", ret);

    return 0;
}    

위의 프로그램에서 3개의 for문을 사용했음으로 빅오 표기법으로 이 알고리즘을 분석하면 O(N³)이 될 것이다.

다만 다른것이 있다면, 각각의 for문의 반복되는 횟수가 다 다르다는 것이다.
3개의 반복문이 중첩되어 있지만 각각 최대의 반복 횟수가 다른데 어째서 빅오 표기법으로 O(N³)이 될 수 있을까

위의 프로그램을 시그마식으로 나타내보면 아래와 같다

반복문이 3개가 중첩되어 있으므로 하나의 반복문 마다 시그마 연산으로 나타내어졌다.
또한, 마지막 for문에서 Sum += Array[k];가 이전 반복 실행의 값을 포함해 더하지 않으므로 시그마 연산 안의 일반항은 1로 표현된다.

가장 안쪽에 있는 for문부터 살펴보자면

= j - i + 1
제어 변수 k는 i부터 j까지 반복되므로 세 번째 for문에서 변수 i와 j는 상수 취급되고 따라서 (최댓값 - 최솟값 + 1)이라는 식으로 나타낼 수 있다.

이제 앞의 결과를 포함해 두 번째 for문을 시그마 식으로 나타내어 본다면

=

로 나타내어진다.

결국, 첫 번째 for문을 기준으로 시그마 연산은

=

=

=

=

O(N³)

프로그램 최적화 예

알고리즘을 최적화한다는 것은 수학적인 접근 방법을 기반으로 프로그램을 살피고 고치는 것이다.

빅오 표기법은 최악의 경우를 판단할 수 있으므로, 최선의 경우라면 평균 실행 시간이 최악의 경우보다는 빠르다는 것을 간접적으로나마 주장 가능하다.
최악의 성능인 경우를 표현하여 "적어도 이 성능 이상은 보장한다" 라는 것을 나타내는 것이다.

최적화

최적화는 최악의 성능을 더 좋아지게 수정해 전체적인 성능을 향상시키는 것이다.
수학적으로 표현하자면, 빅오 표기법으로 표현된 값을 줄이는 과정이라고 설명할 수 있겠다.

코드를 예로 들어 위에서 살펴본 부분 수열의 합을 구하는 프로그램의 성능(O(N³))을 O(N²) 이나 O(NlogN) 더 나아가서 O(N)으로 향상시킬 수 있다.

• O(N²) 향상

    int Max(int N)
    {
        int Sum, Max, i, j;
        Sum = Max = 0
  
        for(i = 0; i< N; i++)
        {
            Sum = 0;
            for(j=1; j<N; j++)
            {
                Sum += Array[j];
                if(Sum > Max)
                    Max = Sum;
            }
        }
        return Max;
    }

정리

알고리즘들을 잘 사용하려면 성능이 좋다고 평가받는 알고리즘을 추종하기보다는, 알고리즘의 개념을 잘 이해하고, 각각 조건에 맞는 알맞은 알고리즘을 적용하거나 개발하는 것이 중요