8-11. 코딩 테스트: 실전 문제 풀이 (정렬, 탐색, 그리디 복합)

1. 정렬, 탐색, 그리디 알고리즘의 융합: 코딩 테스트 핵심 전략

코딩 테스트에서 정렬, 탐색, 그리디 알고리즘은 각각 독립적으로도 자주 출제되지만, 이들을 복합적으로 활용해야만 해결할 수 있는 문제들이 존재합니다. 이러한 문제는 단순히 각 알고리즘의 지식을 아는 것을 넘어, 문제 해결 전략과 알고리즘 선택, 그리고 효율적인 구현 능력을 요구합니다. 본 챕터에서는 이러한 복합적인 문제 해결을 위한 핵심 전략과 구체적인 예시를 통해 실력 향상을 돕고자 합니다.

1) 왜 이 세 가지 알고리즘인가?

정렬, 탐색, 그리디 알고리즘은 문제 해결의 기본 도구이자, 다른 복잡한 알고리즘의 구성 요소로 자주 활용됩니다.

• 정렬(Sorting): 데이터를 특정 기준에 따라 순서대로 나열하는 작업입니다. 정렬된 데이터는 탐색과 그리디 알고리즘의 효율성을 극대화하는 기반이 됩니다.
• 탐색(Searching): 정렬된 데이터 또는 특정 조건에 부합하는 데이터를 찾는 작업입니다. 이진 탐색과 같은 효율적인 탐색 기법은 시간 복잡도를 획기적으로 줄여줍니다.
• 그리디(Greedy): 각 단계에서 가장 좋아 보이는 선택을 반복하여 최종 해답을 구하는 방식입니다. 그리디 알고리즘은 최적 해를 보장하지 못할 수 있지만, 특정 조건 하에서는 효율적인 해법을 제시합니다.

2) 복합 문제의 특징

정렬, 탐색, 그리디 알고리즘을 복합적으로 사용하는 문제는 다음과 같은 특징을 보입니다.

• 데이터 전처리: 정렬을 통해 데이터를 원하는 형태로 가공합니다.
• 해 공간 축소: 탐색 알고리즘을 활용하여 가능한 해의 범위를 줄입니다.
• 최적 해 선택: 그리디 알고리즘을 통해 각 단계에서 최적의 선택을 합니다.

이러한 문제들은 문제를 작은 조각으로 나누어 해결하는 분할 정복(Divide and Conquer) 방식과 유사한 접근 방식을 요구합니다. 각 조각을 해결하기 위해 적절한 알고리즘을 선택하고, 이를 조합하여 최종 해답을 도출해야 합니다.

2. 정렬과 탐색의 결합

정렬과 탐색을 함께 사용하는 대표적인 예시는 "이진 탐색을 위한 데이터 정렬"입니다. 정렬은 탐색의 효율성을 높이는 전처리 과정으로 작용합니다.

1) 이진 탐색의 기본 원리

이진 탐색은 정렬된 데이터에서 원하는 값을 빠르게 찾는 알고리즘입니다. 데이터의 중간 값을 기준으로 탐색 범위를 절반씩 줄여나가기 때문에, 시간 복잡도는 $O(\log n)$으로 매우 효율적입니다.

2) 활용 사례: 특정 범위 내 데이터 개수 찾기

문제: 정렬된 정수 배열 arr과 정수 K가 주어졌을 때, arr에서 K보다 작거나 같은 요소의 개수를 구하시오.

해결 전략:

1. 이진 탐색을 사용하여 K보다 작거나 같은 마지막 요소의 인덱스를 찾습니다.
2. 해당 인덱스 + 1이 답이 됩니다.

코드 예시 (Python):

def count_less_or_equal(arr, k):
    left, right = 0, len(arr) - 1
    result = -1  # 초기값: K보다 작거나 같은 요소가 없는 경우

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] <= k:
            result = mid  # 현재 요소가 K보다 작거나 같으면, result를 갱신
            left = mid + 1  # 더 오른쪽에서 K보다 작거나 같은 요소가 있는지 탐색
        else:
            right = mid - 1  # K보다 크므로, 왼쪽에서 탐색

    return result + 1 if result != -1 else 0  # 찾은 인덱스 + 1이 개수, 없으면 0 반환

3) 성능 분석

• 정렬된 배열을 가정하기 때문에 별도의 정렬 과정은 필요하지 않습니다.
• 이진 탐색의 시간 복잡도는 $O(\log n)$입니다.

3. 정렬과 그리디 알고리즘의 결합

정렬은 그리디 알고리즘의 핵심 전처리 단계로, 최적 선택을 위한 데이터를 구성하는 데 사용됩니다.

1) 그리디 알고리즘의 기본 원리

그리디 알고리즘은 각 단계에서 가장 좋은 선택을 하는 방식으로 문제를 해결합니다. 부분 문제에 대한 최적해가 전체 문제의 최적해로 이어진다는 전제 하에 작동합니다. 하지만, 항상 최적해를 보장하지는 않습니다.

2) 활용 사례: 최소 회의실 개수

문제: 여러 개의 회의 시간이 주어졌을 때, 모든 회의를 수용하기 위한 최소 회의실 개수를 구하시오. 각 회의는 시작 시간과 종료 시간으로 표현됩니다.

해결 전략:

1. 회의 시작 시간을 기준으로 회의들을 정렬합니다.
2. 각 회의를 순회하면서, 현재 회의실의 종료 시간보다 늦게 시작하는 회의가 있는지 확인합니다.
3. 만약 있다면, 해당 회의실을 사용하고, 없다면 새로운 회의실을 할당합니다.
4. 회의실 개수를 갱신합니다.

코드 예시 (Python):

def min_meeting_rooms(meetings):
    # 1. 회의 시작 시간을 기준으로 정렬
    meetings.sort(key=lambda x: x[0])
    rooms = [] # 회의실 종료 시간 저장

    for start, end in meetings:
        # 2. 현재 회의실의 종료 시간보다 늦게 시작하는 회의가 있는지 확인
        if rooms and rooms[0] <= start:
            import heapq
            heapq.heapreplace(rooms, end)  # 회의실 갱신 (종료 시간 업데이트)
        else:
            import heapq
            heapq.heappush(rooms, end) # 새로운 회의실 할당

    return len(rooms) # 회의실 개수 반환

3) 성능 분석

• 회의 시작 시간 정렬: $O(n \log n)$
• 각 회의에 대한 처리: $O(n \log k)$ ( k는 회의실의 개수, 보통 n보다 작음)
• 전체 시간 복잡도: $O(n \log n)$

4. 탐색과 그리디 알고리즘의 결합

탐색과 그리디 알고리즘은 특정 조건 하에서 문제를 효율적으로 해결하기 위해 함께 사용될 수 있습니다.

1) 활용 사례: 배낭 문제 (Knapsack Problem)

문제: 배낭의 최대 용량 W가 주어지고, 각 물건은 무게 w와 가치 v를 가집니다. 배낭에 담을 수 있는 물건들의 최대 가치를 구하시오. (단, 분할 가능한 배낭 문제)

해결 전략:

1. 가치/무게 비율 (v/w)을 기준으로 물건들을 내림차순으로 정렬합니다. 이는 그리디 기준입니다.
2. 정렬된 순서대로 물건을 배낭에 담을 수 있을 때까지 담습니다. (그리디)
3. 마지막 물건은 배낭의 남은 용량에 따라 일부만 담을 수 있습니다.

코드 예시 (Python):

def fractional_knapsack(items, W):
    # 1. 가치/무게 비율을 기준으로 정렬
    items.sort(key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0
    remaining_capacity = W

    for weight, value in items:
        if remaining_capacity >= weight:
            # 물건 전체를 담을 수 있는 경우
            total_value += value
            remaining_capacity -= weight
        else:
            # 물건의 일부만 담을 수 있는 경우
            fraction = remaining_capacity / weight
            total_value += value * fraction
            remaining_capacity = 0
            break  # 배낭이 꽉 찼으므로 종료

    return total_value

2) 성능 분석

• 가치/무게 비율 정렬: $O(n \log n)$
• 물건 선택: $O(n)$
• 전체 시간 복잡도: $O(n \log n)$

5. 실전 문제 해결을 위한 전략

실제 코딩 테스트 문제에서 정렬, 탐색, 그리디 알고리즘을 효과적으로 활용하기 위한 전략은 다음과 같습니다.

1) 문제 분석

• 문제의 요구사항을 정확하게 이해합니다. 어떤 데이터를 입력으로 받고, 어떤 결과를 출력해야 하는지 명확히 파악합니다.
• 제약 조건을 주의 깊게 확인합니다. (예: 시간 제한, 메모리 제한, 입력 데이터의 크기) 제약 조건은 알고리즘 선택에 중요한 영향을 미칩니다.

2) 알고리즘 선택 및 설계

• 문제의 특성에 맞는 알고리즘을 선택합니다. 정렬이 필요한지, 탐색이 필요한지, 그리디가 적용 가능한지 등을 판단합니다.
• 문제를 작은 부분 문제로 나누어 해결하는 방식을 고려합니다. (분할 정복, 동적 계획법 등)
• 선택한 알고리즘을 어떻게 조합할지 결정합니다. 예를 들어, 정렬 후 이진 탐색, 그리디 선택 전에 정렬 등을 고려합니다.

3) 구현 및 최적화

• 선택한 알고리즘을 코드로 구현합니다. 코드는 가독성이 좋고, 유지보수가 용이하도록 작성합니다.
• 시간 복잡도와 공간 복잡도를 고려하여 코드를 최적화합니다. 불필요한 연산을 줄이고, 효율적인 자료구조를 사용합니다.
• 테스트 케이스를 통해 코드를 검증합니다. 예시 케이스, 경계 조건, 예외 상황 등을 포함한 다양한 테스트 케이스를 사용합니다.

4) 디버깅

• 코드가 예상대로 동작하지 않을 경우, 디버깅을 통해 문제를 해결합니다.
• 디버깅 도구 (IDE의 디버거, print 문 등)를 활용하여 코드의 실행 흐름을 추적하고, 변수의 값을 확인합니다.
• 오류 메시지를 통해 문제의 원인을 파악합니다.

6. 추가 팁

1) 자료구조 활용

효율적인 문제 해결을 위해 적절한 자료구조를 선택하는 것이 중요합니다.

• 배열: 순차적인 데이터 접근에 효율적입니다.
• 연결 리스트: 데이터의 삽입/삭제가 빈번한 경우에 유용합니다.
• 힙: 우선순위 큐를 구현하는데 사용되며, 그리디 알고리즘에 자주 활용됩니다.
• 해시 테이블: 빠른 탐색을 위해 사용됩니다.

2) 문제 풀이 연습

다양한 코딩 테스트 문제를 풀어보면서 문제 해결 능력을 향상시키는 것이 중요합니다.

• 온라인 저지: 백준, Codeforces, LeetCode 등의 온라인 저지를 통해 문제를 풀어보고, 다른 사람들의 풀이를 참고합니다.
• 문제 유형별 연습: 정렬, 탐색, 그리디 알고리즘 관련 문제들을 집중적으로 연습합니다.
• 모의 코딩 테스트: 실제 코딩 테스트와 유사한 환경에서 문제를 풀어봅니다.

7. 결론

정렬, 탐색, 그리디 알고리즘을 복합적으로 사용하는 문제는 코딩 테스트에서 흔히 출제되는 유형입니다. 이 세 가지 알고리즘의 원리를 이해하고, 문제 해결 전략을 숙지하며, 꾸준한 연습을 통해 실력을 향상시킬 수 있습니다. 특히, 각 알고리즘의 장단점을 파악하고, 문제의 특성에 맞게 적절히 조합하는 능력이 중요합니다. 본 챕터에서 제시된 예시와 전략을 바탕으로, 코딩 테스트에서 좋은 결과를 얻기를 바랍니다.