왜 필요한가 — 시험 문제는 한 단원으로 끝나지 않는다

지금까지는 정렬(0609편), 탐색(10편), 그래프(1113편), 설계 기법(15~17편)을 각각 독립된 단원으로 배웠다. 하지만 실제 독학사 4단계 시험에서는 “정렬해 둔 다음 이진 탐색으로 찾아라”, “그래프의 최단경로를 구한 뒤 그 값을 동적계획법의 입력으로 써라”처럼 두세 개의 기법이 한 문제 안에서 이어지는 종합 문제가 자주 출제된다. 각 기법을 따로 알고 있어도, 어떤 순서로 어떻게 이어 붙여야 하는지 판단하지 못하면 풀 수 없다.

이 편은 새로운 알고리즘을 배우는 편이 아니라, 이미 배운 알고리즘들을 조합하는 감각을 기르는 편이다.

쉽게 말하면: 지금까지 배운 게 각 과목 시험이었다면, 이 편은 그 과목들을 섞어서 내는 “종합 모의고사”에 대비하는 편이다.

알고리즘 선택 흐름도 — 문제를 보고 무엇을 먼저 떠올릴까

문제를 처음 읽었을 때 어떤 기법을 검토해야 하는지 판단하는 대략적인 흐름은 다음과 같다. 이 흐름도는 절대적인 규칙이 아니라, 문제 유형을 빠르게 좁혀 가는 사고 순서다.

이 흐름도에서 중요한 것은 “탐욕이 맞는지 확신이 없으면 동적계획법을 먼저 검토한다”는 원칙이다(16편에서 다룬 탐욕 선택 속성·최적 부분 구조 판별과 이어진다). 탐욕은 증명 없이 적용하면 반례에 걸리기 쉽지만, 동적계획법은 항상 안전한 대신 시간·공간이 더 든다.

결합 예제 1 — 정렬 + 이진 탐색: “회의실 배정에서 겹치는 회의 찾기”

문제: 회의 10개의 (시작시간, 종료시간)이 주어진다. 각 회의에 대해 “이 회의가 끝난 직후 가장 빨리 시작하는 다른 회의”를 빠르게 찾고 싶다.

풀이 전략: 회의를 시작시간 기준으로 정렬(07편의 퀵·병합 정렬, O(n log n))해 두면, 특정 종료시간 이후 가장 빠른 시작시간을 찾는 문제가 “정렬된 배열에서 특정 값 이상인 첫 원소를 찾는” 문제로 바뀐다. 이는 이진 탐색의 변형(10편, O(log n))으로 풀 수 있다.

만약 정렬을 생략하고 매번 순차 탐색으로 조건에 맞는 회의를 찾는다면 회의 1개당 O(n)이 걸려 전체 O(n^2)이 된다. 먼저 정렬해서 탐색을 이진 탐색으로 바꾸는 것이 이 문제의 핵심 아이디어이며, “정렬 한 번의 비용(O(n log n))을 지불하고 이후 모든 탐색을 O(log n)으로 바꾸는” 교환은 탐색을 여러 번 반복하는 문제에서 특히 유리하다.

자주 틀리는 점: “정렬에 O(n log n)이 걸리니 전체도 O(n log n)이다”라고 성급히 결론짓지 말고, 정렬 이후 단계의 복잡도까지 더한 전체 식을 세워야 한다. 이 예제에서는 우연히 두 단계 모두 O(n log n)이라 합쳐도 O(n log n)이지만, 만약 두 번째 단계가 O(n^2)이었다면 전체 복잡도는 더 큰 쪽인 O(n^2)을 따른다(복잡도를 더할 때는 낮은 차수가 아니라 가장 큰 차수가 전체를 지배한다는 03편의 원칙이 그대로 적용된다).

결합 예제 2 — 그래프 최단경로 + 동적계획법: “환승 횟수 제한 최단경로”

문제: 가중치 그래프에서 정점 A에서 F까지 가는데, 간선을 최대 k번만 사용해서 갈 수 있는 최단 거리를 구하라.

풀이 전략: 일반적인 다익스트라 알고리즘(13편)은 “간선 사용 횟수 제한”이라는 조건을 표현하지 못한다. 이럴 때는 동적계획법의 틀로 다시 세운다. 상태를 dp[i][v] = “간선을 정확히 i번 사용해서 정점 v에 도달하는 최단 거리”로 정의하면, 그래프 문제를 DP 테이블 문제로 바꿀 수 있다.

• $i$: 지금까지 사용한 간선 수
• $v$: 현재 도달한 정점
• $weight(u, v)$: 정점 u에서 v로 가는 간선의 가중치
• $\min$: 정점 v로 들어오는 모든 간선 (u, v) 중 가장 작은 값을 선택

작은 그래프로 직접 값을 채워 보자. 정점이 A, B, C, F이고 간선이 A→B(2), A→C(5), B→C(1), B→F(6), C→F(2)이며 A에서 F까지 간선을 최대 2번만 써서 가는 최단 거리를 구한다고 하자.

dp[2][F] = 7이 나왔으므로, 간선을 최대 2번 써서 A에서 F까지 가는 최단 거리는 7이다. 경로를 직접 되짚어 보면 A→B(2)→F(6)로 가는 값은 8이고, A→C(5)→F(2)로 가는 값은 7이므로 후자가 더 짧다. dp[2][F]를 구하는 식 min(dp[1][B]+6, dp[1][C]+2)에서 dp[1][B]=2이므로 2+6=8, dp[1][C]=5이므로 5+2=7이 되어 min(8, 7)=7이 선택된 것이다.

이 예제의 핵심은 “그래프 문제인데 다익스트라를 바로 못 쓰는 조건(횟수 제한)이 붙으면, 상태에 그 제한 변수를 추가한 DP 테이블로 바꿔 푼다”는 결합 패턴이다. 이는 16편에서 배운 “DP 테이블 설계”를 그래프 위에서 응용한 것이다.

쉽게 말하면: 다익스트라는 “최단 거리”만 상태로 들고 다니지만, 이 문제는 “최단 거리이면서 몇 번 만에 왔는지”까지 같이 들고 다녀야 하므로 DP 테이블의 행 하나(i)를 더 만들어 그 조건을 표현한 것이다.

결합 예제 3 — 그래프 + 탐욕: “MST를 활용한 근사 배치 문제”

문제: 여러 사무실을 광케이블로 모두 연결하되 총 케이블 길이를 최소화하고 싶다. 단, 이미 일부 구간은 공사가 끝나 반드시 사용해야 한다.

풀이 전략: 이 문제는 기본적으로 최소 신장 트리(MST, 12편) 문제다. 다만 “일부 간선은 반드시 포함해야 한다”는 조건이 추가되었다. 크루스칼 알고리즘(정렬 후 유니온-파인드로 사이클을 피하며 간선을 하나씩 추가하는 탐욕 알고리즘, 12편)의 절차를 다음과 같이 바꿔 적용한다.

이 절차가 여전히 최적(총 길이 최소)임을 보장하는 이유는, 필수 간선을 먼저 확정해도 MST의 탐욕 선택 속성(매 순간 사이클을 만들지 않는 가장 싼 간선을 고르면 전체 최적이 된다는 성질)이 깨지지 않기 때문이다. 필수 간선을 유니온-파인드에 미리 반영해 두면, 이후 단계는 원래 크루스칼 알고리즘과 정확히 같은 논리로 진행된다.

결합 예제 4 — 의사코드 통합 추적 연습

다음 의사코드는 정렬과 그래프 탐색을 한 함수 안에서 결합한 예다. 입력은 정점 n개짜리 그래프의 간선 목록 edges(각 원소는 (u, v, weight))이며, 가중치가 작은 간선부터 순서대로 하나씩 그래프에 추가했을 때 처음으로 정점 0과 정점 n-1이 연결되는 순간의 가중치를 구하는 코드다.

procedure minConnectingWeight(n, edges):
    edges를 weight 기준 오름차순 정렬          // 1단계: 정렬, O(E log E)
    parent[0..n-1] = 각자 자신을 부모로 초기화   // 유니온-파인드 초기화
    for (u, v, w) in edges:                    // 2단계: 정렬된 순서로 순회, O(E)
        union(u, v)                             // u, v를 같은 그룹으로 합침
        if find(0) == find(n-1):                // 0과 n-1이 같은 그룹인지 확인
            return w                             // 이 순간의 가중치가 답
    return "연결 불가능"

이 코드는 크루스칼 알고리즘의 골격(정렬 + 유니온-파인드)을 그대로 쓰면서도, MST 전체를 만드는 대신 “두 특정 정점이 언제 처음 연결되는가”만 확인하도록 목적을 바꾼 응용이다. 전체 복잡도는 정렬 O(E log E)와 순회 O(E)(유니온-파인드 연산은 사실상 상수 시간에 가깝다고 근사)를 더해 **O(E log E)**로, 여전히 정렬 단계가 전체 복잡도를 지배한다.

자주 틀리는 점

• 한 문제에 하나의 기법만 있다고 단정하는 실수: “그래프 문제니까 다익스트라만 쓰면 된다”처럼 성급히 단정하지 말고, 조건(횟수 제한, 필수 포함 등)이 추가되면 다른 기법(DP, 탐욕 변형)과의 결합이 필요한지 항상 재검토해야 한다.
• 결합 시 복잡도를 이전 단계에서 멈추는 실수: 정렬 후 탐색, 그래프 후 DP처럼 단계가 이어지는 문제는 각 단계의 복잡도를 모두 구한 뒤 가장 큰 차수를 전체 복잡도로 삼아야 한다.
• 탐욕이 통하는 조건을 확인하지 않고 적용하는 실수: 탐욕 알고리즘을 결합할 때는 반드시 16편의 탐욕 선택 속성이 그 변형된 조건에서도 여전히 성립하는지 근거를 대야 한다(예제 3에서 필수 간선을 먼저 확정해도 성립하는 이유를 설명한 것처럼).
• DP 상태에 필요한 변수를 빠뜨리는 실수: 예제 2처럼 제한 조건(횟수)이 있으면 그 조건을 DP 상태의 차원에 반드시 포함해야 한다. 상태를 dp[v]로만 두면 “몇 번 만에 왔는지”를 구분할 수 없어 문제를 풀 수 없다.

핵심 정리

• 종합 문제를 만나면 먼저 알고리즘 선택 흐름도로 어떤 기법이 필요한지 후보를 좁히고, 여러 기법이 조합되어야 하는지 판단한다.
• 정렬 + 이진 탐색 결합은 “반복되는 탐색을 정렬 한 번으로 빠르게 만드는” 패턴이며 전체 복잡도는 두 단계 중 더 큰 차수를 따른다.
• 그래프 문제에 조건(간선 사용 횟수 제한 등)이 추가되면, 그 조건을 상태 변수로 추가한 DP 테이블로 바꿔 풀 수 있다.
• MST에 “필수 포함 간선” 조건이 붙어도, 그 간선들을 유니온-파인드에 먼저 반영하면 크루스칼의 탐욕 선택 속성이 그대로 유지되어 최적성이 보장된다.
• 여러 기법을 결합한 문제는 전체 복잡도를 각 단계별로 따로 구한 뒤 가장 큰 차수를 최종 답으로 삼아야 한다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 학습정보  — 4단계 알고리즘 과목의 종합·응용 문제 출제 경향 확인.
• 대학 알고리즘 강의노트 — Design Techniques  — 분할정복·동적계획법·탐욕 결합 응용 문제의 표준적인 접근 방식 정리.