알고리즘 설계 기법

왜 배우는가: 알고리즘 설계 기법은 문제를 풀이하는 전략을 선택하는 기초이며, 소프트웨어 설계와 성능 분석의 출발점이다. 백트래킹, 분할정복, 탐욕법, 동적계획법은 기술사 시험에서 개념 비교와 사례 연결을 묻는 문항으로 반복 출제되었다.

출제 이력: 제122회 1교시 9번, 제116회 1교시 12번

1. 한 줄 정의와 핵심 키워드

알고리즘 설계 기법은 문제를 작은 부분으로 나누거나 선택 순서를 정하는 일반적 풀이 전략으로, 백트래킹·분할정복·탐욕법·동적계획법이 대표적이다.

• 키워드: 상태공간 트리, 가지치기(Pruning), 분할(Divide), 정복(Conquer), 병합(Combine), 탐욕 선택 조건, 최적 부분 구조, 중복 부분 문제, 메모이제이션(Memoization)

2. 개념 풀이

쉽게 말하면 큰 문제를 한꺼번에 풀지 않고 전략을 골라 단계적으로 푸는 방법이다. 네 가지 기법은 문제를 나누는 방식과 선택을 되돌리는 방식이 서로 다르다.

백트래킹(Backtracking)은 가능한 모든 경우를 상태공간 트리(State-space Tree)로 펼쳐 깊이우선탐색(DFS)으로 훑는 기법이다. 해가 될 수 없는 노드는 가지치기(Pruning)로 그 하위 트리 전체를 건너뛴다. 예를 들어 N-Queens 문제에서는 같은 열이나 대각선에 퀸이 놓이면 그 아래 경로를 버린다.

분할정복(Divide and Conquer)은 문제를 서로 독립된 소문제로 나누고, 각각을 같은 방법으로 풀어 얻은 결과를 병합(Combine)하는 기법이다. 소문제가 서로 겹치지 않는다는 점이 동적계획법과 구분되는 특징이다. 재귀 구현이 자연스럽다.

탐욕법(Greedy Algorithm)은 매 단계에서 그 순간 지역적으로 최적인 선택을 하고 다시 돌아보지 않는 기법이다. 선택 결과를 모아 전역 해를 만들지만, 전역 최적임을 보장하려면 탐욕 선택 조건과 최적 부분 구조가 함께 성립해야 한다.

동적계획법(Dynamic Programming, DP)은 소문제가 중복해서 나타날 때 각 소문제의 해를 한 번만 계산해 저장하고 재사용하는 기법이다. 저장 방식은 메모이제이션(Memoization)이나 테이블링(Tabulation)으로 나뉜다. 최적 부분 구조와 중복 부분 문제가 모두 있어야 적용할 수 있다.

백트래킹은 가지치기, 분할정복은 독립 분할과 병합, 탐욕법은 지역 최적 선택, 동적계획법은 중복 소문제의 저장 재사용이 핵심 차이다.

3. 등장 배경과 필요성

모든 경우를 전수 탐색하는 방법은 문제 크기가 커지면 조합적으로 시간이 폭증한다. 설계 기법은 문제의 구조를 이용해 탐색 범위를 줄이는 방법으로 등장했다. 백트래킹은 제약 조건이 많은 탐색 문제에서 불필요한 경로를 조기에 잘라낸다.

분할정복은 정렬과 탐색처럼 큰 입력을 반으로 나눌 때 시간 복잡도를 줄이는 데 쓰인다. 병합정렬은 n개 원소를 절반씩 나누어 정렬 구조를 가진다. 탐욕법은 정확한 해를 찾기 어려운 대규모 문제에서 빠른 근사해를 얻기 위해 쓰였고, 최적해 보장 조건이 성립하는 문제에서는 가장 효율적인 방법이 된다.

동적계획법은 피보나치 수열처럼 재귀 호출에서 같은 값이 반복 계산되는 문제를 해결하려고 등장했다. 중복 계산을 저장으로 바꾸면 지수 시간이 다항 시간으로 줄어든다.