Algorithm (알고리즘) | KAITRUST AI 백과사전

📖 상세 설명

알고리즘(Algorithm)은 특정 문제를 해결하기 위한 명확하고 유한한 단계별 절차입니다. 어원은 9세기 페르시아 수학자 알-콰리즈미(Al-Khwarizmi)의 라틴어 이름에서 유래했으며, 컴퓨터 과학의 근본 개념으로 프로그램의 핵심 로직을 구성합니다.

알고리즘의 효율성은 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 측정됩니다. 빅오 표기법(Big-O notation)을 사용하여 입력 크기에 따른 성능 변화를 나타내며, O(1)은 상수 시간, O(n)은 선형 시간, O(log n)은 로그 시간, O(n^2)는 이차 시간 복잡도를 의미합니다.

대표적인 알고리즘 유형으로는 정렬(Sorting), 검색(Searching), 그래프 탐색(Graph Traversal), 동적 프로그래밍(Dynamic Programming), 분할 정복(Divide and Conquer) 등이 있습니다. 각 유형은 특정 문제 패턴에 최적화되어 있으며, 적절한 알고리즘 선택이 시스템 성능을 결정합니다.

실무에서 알고리즘은 데이터베이스 인덱싱, 네트워크 라우팅, 추천 시스템, 검색 엔진 랭킹 등 모든 곳에 적용됩니다. 코딩 테스트와 기술 면접에서도 핵심 평가 요소이며, 2025년 현재 AI/ML 분야에서는 신경망 최적화 알고리즘(SGD, Adam 등)이 모델 학습의 핵심으로 활용됩니다.

💻 코드 예제

# 1. 퀵 정렬 (Quick Sort) - O(n log n) 평균
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"정렬 전: {numbers}")
print(f"정렬 후: {quick_sort(numbers)}")  # [11, 12, 22, 25, 34, 64, 90]


# 2. 이진 탐색 (Binary Search) - O(log n)
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

sorted_arr = [11, 12, 22, 25, 34, 64, 90]
index = binary_search(sorted_arr, 25)
print(f"25의 인덱스: {index}")  # 3


# 3. 동적 프로그래밍 - 피보나치 (메모이제이션)
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(f"피보나치(50): {fibonacci(50)}")  # 12586269025


# 4. BFS (너비 우선 탐색) - 그래프 최단 경로
from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']
}
print(f"BFS 탐색 순서: {bfs(graph, 'A')}")  # ['A', 'B', 'C', 'D', 'E', 'F']

🗣️ 실무에서 이렇게 말하세요

💬 회의에서

"현재 검색 기능이 O(n)인데, 데이터가 100만 건으로 늘어나면 병목이 될 겁니다. 인덱스를 추가해서 O(log n)으로 최적화하거나, 자주 조회되는 결과는 캐싱 레이어를 도입하는 방안을 검토해봐야 할 것 같습니다."

💬 면접에서

"퀵 정렬의 평균 시간 복잡도는 O(n log n)이지만, 이미 정렬된 배열에서 피벗을 첫 번째 원소로 선택하면 O(n^2)로 저하됩니다. 이를 방지하기 위해 랜덤 피벗 또는 median-of-three 방식을 사용합니다."

💬 코드 리뷰에서

"이 이중 루프는 O(n^2)네요. 해시맵을 사용하면 O(n)으로 줄일 수 있습니다. 현재 데이터 규모에서는 문제없지만, 확장성을 고려하면 지금 개선해두는 게 좋겠습니다."

⚠️ 흔한 실수 & 주의사항

❌

조기 최적화 함정

"Premature optimization is the root of all evil" - 먼저 정확히 동작하는 코드를 작성하고, 프로파일링으로 병목을 확인한 후 최적화하세요. 실제 병목이 아닌 곳을 최적화하면 시간 낭비입니다.

❌

최악의 경우(Worst Case) 무시

평균 복잡도만 보면 위험합니다. 퀵 정렬은 평균 O(n log n)이지만 최악은 O(n^2)입니다. 실시간 시스템에서는 최악의 경우도 고려한 알고리즘 선택이 필요합니다.

✅

공간-시간 트레이드오프 이해

시간을 절약하려면 공간을 희생하고(캐싱, 메모이제이션), 공간을 절약하려면 시간이 더 걸립니다. 상황에 맞는 균형점을 찾으세요. 메모리가 충분하다면 해시 테이블로 O(1) 조회를 노리세요.

🔗 관련 용어

📚 더 배우기

🎬 VisuAlgo - 알고리즘 시각화 학습 📊 Big-O Cheat Sheet - 복잡도 참고표 💡 LeetCode - 알고리즘 문제 풀이 연습