[알고리즘] 알고리즘 개요

알고리즘이란?

알고리즘(algorithm)은 컴퓨터 프로그램을 통해 예측 가능한 시간 내에 정확한 결과를 반환하는 단계별 문제 해결 방법이다. 알고리즘은 주어진 문제에 대해 정확한 결과를 내는 것 뿐만 아니라 성능도 신경써야 한다. 즉, 예측 가능한 시간 내에 답을 내놓을 수 있어야 한다.

• 정확성(correctness) : 이 알고리즘은 모든 입력값에 대해 잘 작동될까?
• 성능(performance) : 이 알고리즘이 정말 효율적인 방법일까? (더 적은 시간 내에 정확한 결과를 내는 더 좋은 알고리즘은 없는가?)

problem instance (문제 인스턴스) : 알고리즘으로 처리할 입력값을 말함.

N : 보통 문제 인스턴스의 크기를 말함. 즉, 입력값의 크기. 예) p = [1, 5, 3, 2] → N = len(p) = 4

알고리즘의 작업 시간 측정

N의 크기를 가지는 문제 인스턴스에 대해 알고리즘이 정확한 값을 내는 데에 걸리는 시간을 T(N)이라고 표현하겠다. 알고리즘의 작업 시간 측정에 대해 다음의 두 사실이 알려져 있다.

• T(N)의 값을 미리 예측할 수는 없다. 이 말은, N의 크기를 가지는 문제 인스턴스를 알고리즘이 푸는데에 걸리는 시간을 미리 예측할 수 없다는 뜻이다. 이는 컴퓨터마다의 플랫폼(윈도우냐, 맥OS냐), 또는 사용된 프로그래밍 언어마다 그 시간이 다 다르게 측정되기 때문이다. 즉, 외부 환경이 각자 다르기 때문이다.
• 그렇다 하더라도, 일단 T(N)의 크기를 직접 측정하였다면, T(aN) (a는 양의 정수) 의 값도 예측할 수 있다. 물론 어느 정도 범위의 오차는 존재한다.

알고리즘이 어느 정도의 효율성을 가지는지 판단하는 데에는 두 가지 방법이 있겠다.

• 알고리즘 수행 시 얼마나 많은 컴퓨터 연산이 필요했는지 그 연산 횟수를 세는 법. 컴퓨터에는 CPU(Central processing unit)가 있는데, 이 CPU는 기계 명령어(machine instruction)들을 처리한다. 여기서 기계 명령은 어떤 수들에 대해 수학적 계산(덧셈, 곱셈 등)을 수행하거나, CPU register에 값을 할당하거나, 두 값을 비교하는 작업 등이 될 수 있다. 이 방법으로 연산 횟수를 측정하는 것은 거의 불가능하다.

C, C++과 같은 프로그래밍 언어는 해당 언어로 작성된 소스 코드가 기계 명령어로 컴파일 된다. 반면, python, java와 같은 언어들은 중간 수준(intermediate)인 byte code로 먼저 컴파일 된 다음, 이 byte code를 C언어를 통해 다시 기계 명령어로 번역한다.

• 알고리즘 내에서 특정 핵심 연산(key operation)이 수행된 그 횟수를 센다. 예를 들면, “한 배열 내의 숫자들 중 최대(또는 최소)값을 찾기 위해 얼마나 많은 비교 연산 (<, >)이 사용되었는가?”, “해당 함수가 얼마나 많이 호출되었느냐” 등이 있겠다. 핵심 연산의 수행 횟수가 적을 수록 그 알고리즘이 더 효율적이라고 판단할 수 있다.

알고리즘의 정확성: 모든 입력값에 대해 작동할 수 있어야 한다.

다음은 숫자들이 무작위로 배열된 리스트를 입력값으로 받아 그 중 최대값을 반환하는 알고리즘이다.

def my_max_with_wrong_something(array: list) -> int:
    current_max = 0  # 최대값을 기록하기 위한 변수. 0으로 초기화.
    for value in array:
        if current_max < value:
            current_max = value
    return current_max

if __name__ == '__main__':
    print(my_max_with_wrong_something([1, 5, 2, 9, 3, 4]))
    print(my_max_with_wrong_something([-3, -2, -5])) # 결과: 0 -> 부정확한 결과
    print(my_max_with_wrong_something([])) # 결과: 0 -> 최대값은 존재하지 않는데?

위 알고리즘은 문제가 없는 것 같지만, 사실 결함이 존재한다. 위 코드에서도 알 수 있듯, 모든 입력값이 음수일 경우, 그 음수 내에서의 최대값이 아닌 무조건 0만을 반환하는 문제점이 존재한다. 또한, 빈 리스트를 입력값으로 받을 때도 원래 최대값이 존재하지 않는데 위 함수에서는 0을 반환한다. 이렇듯, 알고리즘은 모든 입력값에 대해 정확한 결과를 반환할 수 있어야 한다.

위 알고리즘에서 최대값을 찾기 위해 반드시 수행되어야할 핵심 연산은 바로 “<” 비교 연산자이다. N의 크기를 가지는 문제 인스턴스에 대해서 해당 비교 연산이 수행되는 횟수는 총 N번이다. for문을 통해 N의 크기를 가지는 배열 내 모든 입력값에 대해 접근하기 때문이다.

핵심 연산 횟수 세기

주어진 리스트 내에 최대값이 존재하기에, 이번에는 해당 리스트의 첫 번째 값을 먼저 저장하는 방식으로 최대값을 찾는 알고리즘을 다음과 같이 짜보았다.

def find_max(array: list) -> int | None:
    try: 
        current_max = array[0]
    except IndexError: 
        # 최대값이 존재하지 않으므로 None 반환.
        return None  
    
    for i, value in enumerate(array):
        if i == 0: continue
        if current_max < value:
            current_max = value
    return current_max

if __name__ == '__main__':
    print(find_max([1, 5, 2, 9, 3, 4])) # 결과: 9
    print(find_max([-3, -2, -5])) # 결과: -2
    print(find_max([])) # 결과: None -> 최대값이 존재하지 않음.

위 알고리즘은 예제 1-1에서 음수 값을 받으면 0이 출력되는 문제를 해결한다. (또한 빈 리스트를 입력 받으면 결과값이 없다는 의미로 None을 반환하도록 하였다)

위 알고리즘에서 비교 연산자 “<”이 호출된 횟수는 N-1임을 알 수 있다. 알고리즘의 문제점을 해결함과 동시에 성능도 조금이나마 향상시켰다.

알고리즘 비교

다음은 주어진 입력값에서 최대값을 찾는 똑같은 문제를 다른 알고리즘으로 푸는 코드이다.

def find_max_with_bool(array: list) -> int | None:
    for value in array:
        current_value_is_max = True
        for other_value in array:
            if value < other_value:
                current_value_is_max = False
                break
        if current_value_is_max: return value
    return None  # 빈 리스트 입력 대비.

위 알고리즘도 똑같이 최대값을 반환한다.

위 알고리즘은 내부 for문에서 현재 값보다 다음 값이 더 클 경우 해당 for문을 빠져나가는 방식이다. 이는 입력값의 순서에 따라 비교 연산 “<”의 실행 횟수가 달라지는 구조이다. 또한 외부 for문에서도, 현재 값이 최대값인지를 판별하는 변수인 current_value_is_max 의 값에 따라 for문을 빠져나가는 형태이다. 즉, 이것도 입력값의 순서에 따라 핵심 연산의 횟수가 달라지는 구조이다.

해당 알고리즘이 문제 인스턴스 [1, 5, 2, 9, 3, 4]을 푸는 방식. 해당 문제 인스턴스에서는 핵심 연산이 총 14번 수행되었다. [1] 참고함.

이렇게 입력값에 따라 핵심 연산의 횟수가 달라지는 알고리즘의 경우, 핵심 연산을 세기 위해 최선의 경우와 최악의 경우로 나눌 수 있다.

• 최선의 경우 (best case): 알고리즘으로 최소한의 작업을 수행하도록 하는 N 크기의 문제 인스턴스의 경우를 말함. (즉, 핵심 연산의 횟수가 최소값을 가지게 하는 문제 인스턴스)
• 최악의 경우 (worst case): 알고리즘으로 최대한의 작업을 수행하도록 하는 N 크기의 문제 인스턴스의 경우를 말함. (즉, 핵심 연산의 횟수가 최대값을 가지게 하는 문제 인스턴스)

위 예제를 들면, 최선의 경우는 입력값들이 큰 수부터 차례대로 작은 수까지 내림차순으로 정렬되어 있는 경우이다. 이 경우, 맨 처음 입력값이 내부 for 문에서 N번을 순회한 뒤, 외부 for문의 if문을 바로 만족시켜서 빠져나갈 수 있으므로 N번만 수행하면 된다. 최악의 경우는 입력값들이 반대로 오름차순으로 배열되어 있어 최대값이 맨 오른쪽 끝에 있는 경우이다. 이 경우 핵심 연산의 횟수는 \((N^2+3N-2)/2\)이다.

최선의 경우인 [9, 5, 2, 1, 3, 4]와 최악의 경우인 [1, 2, 3, 4, 5, 9]에 대해 해당 알고리즘이 작동하는 방식. [1] 참고함.

• 위 알고리즘에서 최악의 경우, 핵심 연산 횟수 증명.

  

예제 2-1의 find_max() 함수로 구현한 알고리즘은 입력값의 순서에 상관없이(빈 리스트인 경우는 제외) 항상 N-1번만 연산을 한다. 그러나 예제 3-1의 알고리즘은 최선의 경우 N번, 최악의 경우 N^2에 해당하는 연산 횟수를 수행해야만 한다. 이들을 비교하면, 두 알고리즘 모두 똑같은 문제를 해결할 수 있으나, find_max()가 더 좋은 성능을 지닌 알고리즘이라고 볼 수 있다.

여태까지 입력값의 크기 N에 따른 핵심 연산의 횟수를 세어 두 알고리즘의 성능을 비교하였다. 그런데 정말로 핵심 연산의 횟수만으로 두 알고리즘의 성능을 파악, 비교할 수 있는 것일까?

[1] 참고함.

위 사진은 [1]의 저자가 직접 예제 3-1의 알고리즘에서의 “<” 연산자가 사용된 횟수와 해당 알고리즘을 실제로 수행했을 때 걸리는 시간을 비교하여 그린 그래프이다. 파란 막대 그래프가 “<” 연산자의 사용 횟수이고, 검은색 점들이 이어진 그래프가 실제 알고리즘 수행 시간을 나타낸다. 이 두 그래프가 입력값의 크기 N이 증가함에 따라 서로 똑같은 양상으로 증가함을 알 수 있다. 이는 알고리즘에서의 핵심 연산의 횟수를 측정하는 것만으로도 입력값의 크기가 증가함에 따라 해당 알고리즘의 수행 시간이 어떤 양상으로 증가할 것인지를 대략적으로 예측할 수 있음을 알려준다. 이러한 사실을 통해 알고리즘에서의 핵심 연산의 횟수를 이용하여 똑같은 문제를 해결하는 여러 다른 알고리즘들의 성능을 서로 비교할 수 있음을 알 수 있다. 즉, 여태까지 핵심 연산 (위 예에서는 ”<” 비교 연산자의 사용 횟수)의 횟수를 세었던 것이 무의미한 행동이 아님을 증명한다.

find_max와 find_max_with_bool 알고리즘의 입력값의 크기에 따른 수행 시간 및 비교 연산 “<”의 횟수를 표로 나타낸 사진이다. 최악의 경우를 상정하였으며, 여기서 Largest는 find_max, Alternate는 find_max_with_bool에 해당한다. 핵심 연산의 횟수는 N의 크기가 증가할수록 find_max_with_bool이 더 많은데, 실제 수행 시간에서도 해당 알고리즘의 수행 시간이 더 큰 것을 알 수 있다. [1] 참조함

최고의 알고리즘 판단 기준들

똑같은 문제를 푸는 여러 알고리즘들 중 최고의 알고리즘을 판단하는 기준은 핵심 연산의 횟수로 수행 시간이 가장 적은 알고리즘을 판단하는 방법 뿐만 아니라 그 외 다양한 기준으로도 판단할 수 있다.

• 추가 메모리가 더 필요한가? 즉, 해당 알고리즘이 원래 문제 인스턴스의 복사본을 필요로 하는가? 추가 메모리가 적을수록 더 좋은 알고리즘으로 판단할 수 있다.
• 해당 알고리즘을 구현하기 위해 얼마나 많은 코드를 작성하였는가? 코드가 적을수록 좋은 알고리즘이라고 판단할 수 있다.
• 가변형 입력값(mutable input) : 해당 알고리즘이 문제 인스턴스를 변형시켜야 하는가? 문제 인스턴스를 그대로 두는 것이 더 좋은 알고리즘이라고 판단할 수도 있다.
• 속도: 해당 알고리즘이 입력값에 무관하게 아주 좋은 성능 (즉, 적은 수행 시간)을 내는가?

이러한 모든 기준을 만족하는 알고리즘을 찾기는 어려울 것이다. 그럴 땐 상황에 따라 어떤 기준을 적용할 것인지 고민해보고, 해당 기준을 통해 좋은 알고리즘을 판단하는 것이 좋겠다.

---

Reference

[1] George T. Heineman, “Learning Algorithms: A Programmer’s Guide to Writing Better Code”, (O’Reilly, 2021)

This content is licensed under CC BY-NC 4.0