알고리즘이란 무엇인가

컴퓨터 과학을 공부하다 보면 “알고리즘”이라는 단어를 수도 없이 마주치게 됩니다. 그런데 막상 “알고리즘이 정확히 무엇인가요?”라는 질문을 받으면 명쾌하게 답하기 어려울 수 있습니다. 이번 시리즈의 첫 글에서는 알고리즘의 정확한 정의와 좋은 알고리즘이 반드시 갖춰야 할 조건들을 살펴보겠습니다.

알고리즘의 정의

**알고리즘(Algorithm)**이란 주어진 문제를 해결하기 위한 유한한 단계의 명확한 절차입니다. 이름의 어원은 9세기 페르시아 수학자 알-콰리즈미(Al-Khwarizmi)의 라틴어 이름 ‘Algoritmi’에서 유래했습니다.

핵심은 입력을 받아서, 명확히 정의된 절차를 수행하고, 결과를 출력한다는 흐름에 있습니다.

알고리즘을 요리 레시피에 비유하면 이해하기 쉽습니다. “파스타를 맛있게 끓여라”는 알고리즘이 아닙니다. 하지만 “물 500mL를 끓이고 → 면을 넣고 8분 삶고 → 소스를 넣고 2분 볶는다”는 알고리즘입니다. 각 단계가 누가 봐도 동일하게 수행할 수 있을 만큼 명확하기 때문입니다.

좋은 알고리즘의 5가지 조건

컴퓨터 과학에서는 알고리즘이 반드시 갖춰야 할 다섯 가지 조건을 정의합니다.

① 입력 (Input)

알고리즘은 0개 이상의 입력을 받을 수 있습니다. 입력이 없어도 되지만(예: 랜덤 숫자 생성), 입력이 있다면 그 형식과 범위가 명확해야 합니다.

② 출력 (Output)

반드시 1개 이상의 결과를 출력해야 합니다. 아무 결과도 내지 않는 절차는 알고리즘이라 할 수 없습니다.

③ 명확성 (Definiteness)

각 단계는 모호함이 없어야 합니다. “적당히 섞어라”처럼 해석이 여러 개인 지시는 알고리즘에서 허용되지 않습니다. “배열의 i번째 원소와 i+1번째 원소를 비교해 arr[i] > arr[i+1]이면 교환한다”처럼 누가 읽어도 동일하게 수행해야 합니다.

④ 유한성 (Finiteness)

알고리즘은 반드시 종료해야 합니다. 유한한 단계를 거쳐 결과를 내지 않는 무한 루프는 알고리즘이 아닙니다. (운영체제처럼 의도적으로 무한히 실행되는 것은 알고리즘이 아니라 프로세스라 부릅니다.)

⑤ 효과성 (Effectiveness)

각 연산은 사람이(또는 컴퓨터가) 실제로 수행할 수 있는 기본 단위여야 합니다. “π번째 소수를 즉시 반환”처럼 계산 불가능한 연산은 효과적이지 않습니다.

알고리즘과 프로그램의 차이

알고리즘은 **아이디어(절차의 명세)**이고, 프로그램은 알고리즘의 구체적인 구현입니다. 같은 알고리즘을 Python으로도, Java로도, C로도 구현할 수 있습니다.

# 알고리즘: 배열에서 최댓값 찾기
# 입력: 정수 배열 arr (비어 있지 않음)
# 출력: 배열에서 가장 큰 정수

def find_max(arr):
    max_val = arr[0]        # Step 1: 첫 원소를 최댓값으로 초기화
    for num in arr[1:]:     # Step 2: 나머지 원소를 순회
        if num > max_val:   # Step 3: 더 크면 갱신
            max_val = num
    return max_val          # Step 4: 결과 반환

print(find_max([3, 1, 4, 1, 5, 9, 2, 6]))  # 9

위 코드는 5가지 조건을 모두 만족합니다. 입력이 있고(배열), 출력이 있고(최댓값), 각 단계가 명확하고, 배열 길이 n번 만에 반드시 종료되고, 각 연산(비교, 대입)이 기본 연산입니다.

왜 알고리즘을 공부해야 하는가

좋은 알고리즘과 나쁜 알고리즘의 차이는 단순히 코드 스타일 문제가 아닙니다. 입력 크기 n이 1,000만이 될 때 O(n²) 알고리즘은 1조 번의 연산을 필요로 하지만, O(n log n) 알고리즘은 약 2,300만 번만으로 끝납니다. 현실적인 실행 시간의 차이가 수백만 배에 달할 수 있습니다.

import time

def naive_search(arr, target):        # O(n)
    for x in arr:
        if x == target:
            return True
    return False

def sorted_binary_search(arr, target): # O(log n)
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

n=10,000,000일 때 선형 탐색은 최악 1,000만 번 비교가 필요하지만, 이진 탐색은 최악 24번 비교로 끝납니다.

정리

• 알고리즘 = 문제를 해결하는 유한하고 명확한 절차
• 5조건: 입력, 출력, 명확성, 유한성, 효과성
• 프로그램은 알고리즘의 구현체 — 같은 알고리즘을 여러 언어로 구현 가능
• 알고리즘의 효율 차이는 현실에서 수백만 배 성능 격차를 만든다

---

다음 글: 알고리즘 분석 입문

읽어주셔서 감사합니다. 😊