문제 구조에 맞는 알고리즘 설계 기법 선택

알고리즘 선택은 문제 모델링에서 갈린다

복잡한 최적화나 의사결정 문제는 같은 목표를 두고도 전혀 다른 풀이 전략을 요구한다. 국소적인 선택을 반복해도 되는지, 작은 문제가 서로 겹치는지, 하위 문제가 독립적인지, 제약을 만족하는 해를 끝까지 찾아야 하는지를 먼저 구분해야 한다.

대표적인 축은 탐욕 기법(Greedy), 분할 정복(Divide and Conquer), 동적 계획법(Dynamic Programming), 백트래킹(Backtracking)이다. 크루스칼(Kruskal), 다익스트라(Dijkstra), 병합 정렬(Merge Sort), 피보나치 수열(Fibonacci), N-Queen 문제는 각 기법의 적용 조건을 드러내는 사례다.

국소 선택부터 상태 탐색까지

탐욕 기법은 매 단계에서 국소적으로 가장 좋아 보이는 선택을 이어 붙여 해를 구성한다. 최적 부분 구조와 탐욕 선택 성질이 모두 충족될 때 최적해를 얻을 수 있다. 음수 가중치가 없는 다익스트라와 크루스칼이 대표적이다. 구현이 단순하고 실행 속도 면에서 유리하지만, 탐욕 성질이 성립하지 않으면 근사해나 반례에 머문다.

분할 정복은 문제를 독립적인 부분 문제로 나눈 뒤 각각을 재귀적으로 풀고, 결합 단계에서 최종 해를 만든다. 병합 정렬, 퀵 정렬, 최근접 점 쌍은 이 패턴을 따른다. 병렬화와 분산 처리에는 유리하지만, 결합 단계의 안정성과 메모리 사용량을 함께 관리해야 한다.

동적 계획법은 최적 부분 구조와 부분 문제 중복이 있을 때 상태공간을 관리하며 최적해를 구한다. 하향식(Top-down, 메모이제이션)과 상향식(Bottom-up, 테이블레이션)으로 구현할 수 있으며, 피보나치 수열·배낭 문제·편집 거리가 전형적인 사례다. 상태공간을 잘못 정의하거나 테이블이 과도해지면 공간 복잡도가 병목이 될 수 있다.

백트래킹은 제약을 위반하는 가지를 일찍 제거(pruning)하면서 해 공간을 줄이는 정확해 탐색 방식이다. CSP(제약 충족 문제), N-Queen, 스케줄링, 퍼즐에 사용할 수 있다. 변수와 값의 선택 순서, 전진점검, 산술적 경계 같은 정합성 검사는 가지치기 성능을 크게 좌우한다.

선택 전에 확인할 조건과 검증 기준

알고리즘을 고르기 전에는 최적 부분 구조, 부분 문제 중복, 탐욕 선택 성질, 부분 문제의 독립성, 제약 구조를 확인한다. 이후 목표함수·제약식·상태를 모델링하고, 반례를 포함해 조건을 검증한 뒤 패턴을 선택한다. 힙, 유니온파인드, 테이블 같은 자료구조와 전략을 정하고 복잡도와 정당성을 점검한다.

탐욕 기법은 교환 논법으로, 동적 계획법은 최적성 원리와 수학적 귀납법으로 검증할 수 있다. 루프 불변식, 반례 기반 테스트, 경계 조건과 퇴화 케이스도 함께 확인해야 한다. 시간·공간 복잡도, 병렬화·분산 가능성, 최적해 보장 여부, 입력 제약 위반 시의 동작, 구현과 디버깅의 난이도는 서로 맞바꾸는 요소다.

⤢✕

다익스트라는 음수 가중치를 허용하지 않는다. 음수 가중치가 있으면 벨만-포드 또는 존슨 알고리즘을 검토해야 한다. 탐욕 선택 성질을 확신할 수 없을 때는 반례 테스트를 거친 뒤, 필요하면 동적 계획법이나 백트래킹으로 전환한다.

성능과 운영 조건을 함께 비교하기

기법	성능(전형 복잡도 예)	확장성	일관성(최적해 보장)	안정성	운영 편의
탐욕(Greedy)	O(E log V) 다익스트라, O(E log E) 크루스칼	높음(단순 구조)	조건 충족 시 보장, 미충족 시 불보장	입력 제약 위반 시 오답 위험	구현 용이
분할 정복	O(n log n) 병합정렬	높음(병렬화 용이)	독립성 가정하 보장	결합 단계 오류 민감	중간버퍼 관리 필요
동적 계획법	O(nW) 배낭 등 상태 의존	중간(메모리 한계 영향)	보장(상태 정의 적절 시)	테이블 설계 오류 민감	디버깅 난이도 중
백트래킹	최악 지수시간, 가지치기로 평균 단축	낮음(분산 어려움)	보장(완전 탐색 기반)	휴리스틱 의존	구현 난이도 중상

네트워크·데이터 처리·제약 탐색에 적용하는 방식

네트워크 설계에서는 크루스칼 기반 최소 신장 트리로 링크 임차 비용을 줄이고 冗長 경로를 구성할 수 있다. 유니온파인드를 사용하면 O(E log E)를 달성한다. 지리정보나 데이터센터 네트워크의 최단 경로는 다익스트라로 계산할 수 있으며, 음수 가중치가 있을 때는 벨만-포드로 대체한다.

대용량 정렬과 ETL에서는 외부 병합 정렬을 이용해 디스크 기반 정렬 파이프라인을 구성한다. 이때 스트리밍 윈도우와 백프레셔를 고려해야 한다. 가격·재고·스케줄링 문제에는 동적 계획법을 적용해 수요 불확실성 하의 재고 정책(S,S)을 근사하고, 편집 거리로 로그를 정합하며, 배낭 계열로 자원을 배분할 수 있다.

시험 배치, 근무 스케줄, 좌석 배치처럼 제약이 중심인 문제는 백트래킹으로 탐색한다. N-Queen은 가지치기 전략을 검증하기 좋은 문제다.

메모이제이션으로 피보나치 상태를 재사용하기

Python 3.10+ 환경에서 외부 라이브러리 없이 실행할 수 있다.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

if __name__ == "__main__":
    print([fib(i) for i in range(10)])  # 검증: 0,1,1,2,3,5,8,13,21,34

시간 복잡도는 O(n), 공간 복잡도는 O(n)이며 음수 입력은 예외 처리한다.

충돌한 배치를 즉시 되돌리는 N-Queen 탐색

def solve_n_queens(n: int) -> int:
    if n < 1:
        return 0
    cols, diag1, diag2 = set(), set(), set()
    count = 0

    def backtrack(r: int):
        nonlocal count
        if r == n:
            count += 1
            return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            backtrack(r + 1)
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)

    backtrack(0)
    return count

if __name__ == "__main__":
    for n in range(4, 9):
        print(n, solve_n_queens(n))

열과 대각선의 충돌은 즉시 제외한다. 최악 시간은 지수적이며, 실무에서는 최소 남은 값과 대각선 우선 같은 휴리스틱을 병행한다.

선택 기준을 표준화했을 때의 변화

문제 구조가 충족된다는 가정에서 탐욕 기법을 동적 계획법으로 대체하면 평균 실행 시간이 10~~100배 단축될 수 있다. 분할 정복 기반 병렬화는 코어 수 대비 서브선형 오버헤드 조건에서 처리량을 3~~8배 높일 수 있다. DP 테이블링은 재귀 중복을 제거해 호출 수를 O(φ^n)에서 O(n)으로 축소한다.

알고리즘 선택 기준을 표준화하면 분석·리뷰 시간을 30% 이상 줄일 수 있다. 가중치 부호 검사 같은 입력 제약 검증은 오류 재처리 건수를 50% 감소시키며, 분할·결합·상태 정의를 모듈화하면 테스트 커버리지가 높아지고 회귀 결함이 줄어든다.

문제의 최적 부분 구조, 독립성, 중복 여부, 제약 강도를 먼저 진단하고 그 결과를 선택 기준으로 남겨야 한다. 반례와 경계 조건 검증을 공정에 포함하고, 입력 제약·자료구조 적합성·증명 가능성을 체크리스트로 관리하는 방식이 성능과 정확성을 함께 지키는 기반이 된다.