알고리즘

우리는 일상 속에서 수많은 문제를 해결하며 살아간다. 컴퓨터도 마찬가지다. 다양한 문제를 해결하기 위해 존재하며, 이를 위해 단순한 문법이나 언어 지식만으로는 부족하다. 문제를 해결하는 절차적 사고, 즉 알고리즘이 필요하다.

알고리즘은 주어진 문제를 해결하거나 특정 함수를 계산하기 위한 유한한 명령어들의 순서적 집합이다. 이는 코드로 작성되기 전, 해결 방법 자체를 논리적으로 정의한 것이라 볼 수 있다. 문제의 구조와 제약 조건에 따라 적절한 설계 전략을 선택하고 적용함으로써, 효율적인 프로그램을 구현할 수 있다.

알고리즘의 필요 조건

1. 입출력 (Input/Output): 최소 하나 이상의 출력이 존재해야 한다.
2. 명확성 (Definiteness): 각 단계는 명확하고 모호하지 않아야 한다.
3. 유한성 (Finiteness): 유한한 단계 내에 종료되어야 한다.
4. 유효성 (Effectiveness): 각 단계는 실제 실행 가능한 명령어여야 한다.
5. 효율성 (Efficiency): 제한된 시간과 자원 내에 실행 가능해야 한다.

알고리즘 설계 절차

1. 문제 정의 및 요구 분석
2. 해결 전략 수립 (의사코드, 순서도, 수학적 모델 등)
3. 정확성 검증 (모든 입력에 대해 기대한 결과 도출 여부)
4. 효율성 분석 (시간 복잡도, 공간 복잡도 평가)
5. 코드 구현 및 테스트

알고리즘 설계 기법

문제를 푸는 방식에는 여러 전략이 존재하며, 대표적으로 아래 세 가지가 많이 사용된다.

1. Greedy Algorithm (탐욕 기법)

전략

• 매 단계마다 가장 최선이라고 판단되는 선택을 한다.
• 전체 최적해를 보장하지는 않지만, 빠르게 근사해를 구할 수 있다.

장점

• 구현이 단순하고 빠르다.

단점

• 항상 최적의 해를 보장하지 않는다.

예시: 거스름돈 문제

문제: 780원을 최소 개수의 동전으로 바꾸기 (동전: 500, 100, 50, 10)

→ 가장 큰 동전부터 greedy하게 선택  
→ 500 × 1 + 100 × 2 + 50 × 1 + 10 × 3 = 7개

단, 동전 종류가 [500, 120, 100, 10]일 경우 greedy 전략은 비효율적일 수 있다.

예시: Fractional Knapsack (물건 쪼갤 수 있음)

items = [(15, 3), (20, 5), (14, 4), (9, 3)]  # (이익, 무게)
items.sort(key=lambda x: x[0]/x[1], reverse=True)  # 단위 무게당 이익 기준 정렬

물건을 쪼갤 수 없는 경우(0/1 Knapsack)에는 부적합하다.

2. Divide and Conquer (분할 정복)

전략

• 문제를 작게 나누어 푼 다음, 결과를 결합한다.
• 하위 문제들은 서로 독립적이어야 한다.

장점

• 재귀적 접근이 자연스럽고, 병렬 처리가 가능하다.

단점

• 하위 문제 간 중복이 많으면 비효율적이다.

예시: 이진 탐색

def binary_search(arr, key, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == key:
        return mid
    elif key < arr[mid]:
        return binary_search(arr, key, left, mid - 1)
    else:
        return binary_search(arr, key, mid + 1, right)

• 분할: 배열을 절반으로 나눔
• 정복: 절반 중 하나만 탐색
• 결합: 결과를 반환 (병합 과정 없음)

예시: 정렬 알고리즘

• 퀵 정렬 (Quick Sort)
• 병합 정렬 (Merge Sort)

3. Dynamic Programming (동적 계획법)

전략

• 작은 문제의 결과를 저장하여 중복 계산을 피한다.
• 하위 문제가 중복되며, 최적 부분 구조를 가질 때 적합하다.

장점

• 시간 효율이 높고, 최적의 결과를 보장한다.

단점

• 상태 정의와 점화식 설계가 복잡할 수 있다.

예시: 최장 공통 부분 수열 (LCS)

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(m):
        for j in range(n):
            if X[i] == Y[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    return dp[m][n]

대표 문제

• 피보나치 수열 (memoization)
• 플로이드-워셜 (모든 정점 간 최단 거리)
• 행렬 곱셈 최적화

알고리즘 분석

효율적인 알고리즘을 설계하고 선택하기 위해서는 두 가지 관점에서 알고리즘을 분석해야 한다.

정확성 분석

정확성(Accuracy)은 유효한 입력이 주어졌을 때 알고리즘이 올바른 결과를 생성하는지를 확인하는 과정이다. 일반적으로 수학적 기법(귀납법 등)을 사용하여 증명한다.

효율성 분석

알고리즘을 수행하는 데 필요한 자원의 양을 측정하고 평가하는 것을 효율성(Efficiency) 분석이라 한다.

• 시간 복잡도(Time Complexity): 알고리즘의 실행부터 완료까지 걸리는 시간
• 공간 복잡도(Space Complexity): 알고리즘 수행에 필요한 메모리의 양 (정적 공간 + 동적 공간)

시간 복잡도 측정 방법

실제 컴퓨터로 측정한 시간은 하드웨어, 운영체제 등 외부 요인의 영향을 받기 때문에 일반적인 성능 분석에는 적합하지 않다. 따라서 알고리즘의 수행 시간을 기본 연산의 수행 횟수로 모델링하여 평가한다.

영향을 미치는 요인

• 입력 크기 n: 입력이 클수록 반복이나 연산이 많아진다.
• 입력 데이터의 상태: 최선, 평균, 최악의 경우가 존재하며, 일반적으로 최악의 수행 시간을 기준으로 시간 복잡도를 표현한다. 이는 알고리즘 간 우열을 비교하고, 안정성을 확보하기 위해서이다.

시간 복잡도 예시

def sum_average(A, n):            # 입력: 리스트 A, 크기 n
    sum_ = 0                      # 1
    i = 0                         # 1
    while i < n:                  # n+1
        sum_ += A[i]              # n
        i += 1                    # n
    average = sum_ / n            # 1
    print("sum:", sum_, "average:", average)  # 1

• 총 수행 횟수: 3n + 5
• 시간 복잡도: O(n)

점근 성능 분석 (Asymptotic Performance)

입력 크기 n이 커질수록 알고리즘 성능의 변화 추세를 분석한다. 다음은 두 알고리즘의 수행 시간 함수 예시다:

• f₁(n) = 10n + 9
• f₂(n) = n² / 2 + 3n

입력 크기가 작을 땐 f₁과 f₂의 차이가 미미하지만, n이 커질수록 f₂는 훨씬 느려진다. 따라서 수행 시간 함수에서 가장 큰 영향을 미치는 최고차항만으로 성능을 분석한다.

예시

• 3n + 5 → O(n)
• 2n² + 5n + 200 → O(n²)

점근 표기법 (Asymptotic Notation)

예시: O(n), Ω(n), Θ(n)

• Big-O 표기에서 g(n)은 f(n)을 상한으로 감쌀 수 있는 최소 차수의 함수를 넣는다.
• Big-Ω에서는 f(n)을 하한으로 감쌀 수 있는 최대 차수의 함수를 넣는다.

시간 복잡도 크기 비교

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)

• O(1): 입력과 무관하게 일정한 시간
• O(log n): 이진 탐색처럼 로그 시간
• O(n): 단일 반복문
• O(n²): 이중 반복문
• O(2ⁿ): 지수적 증가 → 매우 비효율적

실용적인 시간 복잡도 계산법

• 기본 연산의 총 수행 횟수 f(n)을 계산한다.
• 점근 표기법으로 표현: f(n) = O(g(n))

# 예시 1 - O(n)  
i = 1
x = 0
while i <= n:  # n  
    x += 1
    i += 1


# 예시 2 - O(n²)  
count = 0
for i in range(n):          # n  
    for j in range(n):      # n  
        count += 1

순환(재귀) 알고리즘 분석

순환 알고리즘이란?

자기 자신을 호출하는 알고리즘으로, 보통 점화식(재귀식)으로 성능을 표현한다.

예시: 이진 탐색

def binary_search(arr, key, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == key:
        return mid
    elif key < arr[mid]:
        return binary_search(arr, key, left, mid - 1)
    else:
        return binary_search(arr, key, mid + 1, right)

• 점화식: T(n) = T(n/2) + c
• 폐쇄형: T(n) = Θ(log n)

점화식: 알고리즘의 재귀적 구조를 수식으로 표현한 것
폐쇄형: 위와같은 점화식을 단순한 함수 형태로 풀어낸 것

대표 점화식과 폐쇄형

• T(n) = T(n-1) + Θ(1) → Θ(n): 매 단계마다 상수 연산
• T(n) = T(n-1) + Θ(n) → Θ(n²): 매 단계마다 선형 연산
• T(n) = T(n/2) + Θ(1) → Θ(log n): 절반씩 줄이며 상수 연산
• T(n) = T(n/2) + Θ(n) → Θ(n): 절반씩 줄이며 매 단계 n만큼 처리
• T(n) = 2T(n/2) + Θ(1) → Θ(n): 두 개의 하위 문제, 상수 병합
• T(n) = 2T(n/2) + Θ(n) → Θ(n log n): 두 개의 하위 문제, 선형 병합

기호 해석

최종적으로 우리는 Big-O 또는 Θ 표기법으로 복잡도를 나타낸다.
분할정복 기법이 적용된 알고리즘은 대체로 재귀 구조이며, 점화식으로 정의된다.

효율적인 알고리즘의 중요성

입력 크기에 따라 알고리즘 성능은 기하급수적으로 차이 날 수 있다.

작은 입력에선 차이가 적지만, 입력이 커질수록 효율적인 알고리즘 선택이 필수적이다.