2026-02-03 | 8 min read | 196 | 실전 알고리즘 예시

8-6. 코딩 테스트: 실전 문제 풀이 (종합)

1. 실전 문제 풀이의 중요성

코딩 테스트는 단순히 알고리즘 지식을 묻는 것을 넘어, 문제 해결 능력, 효율적인 코드 작성 능력, 그리고 실제 문제 상황에 대한 적응력을 평가하는 중요한 과정입니다. 그동안 우리는 그리디, 구현, 시뮬레이션, 완전 탐색, 이진 탐색 등 다양한 알고리즘과 문제 풀이 전략을 학습했습니다. 이제 이러한 지식들을 종합하여 실제 코딩 테스트에서 마주칠 수 있는 다양한 유형의 문제들을 해결하는 연습을 할 차례입니다.

2. 문제 분석과 알고리즘 선택

코딩 테스트 문제 풀이의 핵심은 문제 분석입니다. 문제를 정확히 이해하고, 요구사항을 파악하는 것이 성공적인 해결의 첫걸음입니다. 문제 분석 단계에서는 다음 질문들을 스스로에게 던져보세요.

어떤 입력을 받는가?
어떤 출력을 내야 하는가?
제한 조건은 무엇인가? (시간, 메모리)
어떤 알고리즘을 적용해야 할까? (그리디, DP, 그래프, 등)

문제 유형을 파악했다면, 적절한 알고리즘을 선택해야 합니다. 알고리즘 선택 시에는 시간 복잡도와 공간 복잡도를 고려해야 하며, 제한 조건에 맞는 효율적인 알고리즘을 선택하는 것이 중요합니다.

예를 들어, 최단 경로를 찾는 문제라면 다익스트라(Dijkstra)나 플로이드-워셜(Floyd-Warshall) 알고리즘을, 특정 조건을 만족하는 부분 집합을 찾는 문제라면 백트래킹(Backtracking)을 고려해볼 수 있습니다.

3. 문제 유형별 접근 방식

1) 그리디 (Greedy)

그리디 알고리즘은 각 단계에서 최적의 선택을 하여 전체 문제의 최적 해를 구하는 방식입니다. 하지만 모든 문제에 적용될 수 있는 것은 아니며, 탐욕 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure)를 만족해야 합니다.

탐욕 선택 속성: 각 단계에서 최적의 선택이 전체 문제의 최적 해로 이어진다는 것을 의미합니다.
최적 부분 구조: 문제의 최적 해가 부분 문제들의 최적 해로 구성된다는 것을 의미합니다.

그리디 알고리즘을 적용할 수 있는 대표적인 문제 유형으로는 거스름돈 문제, 활동 선택 문제, 최소 스패닝 트리 문제 등이 있습니다.

2) 구현 (Implementation)

구현 문제는 문제의 요구 사항을 코드로 정확하게 작성하는 문제입니다. 문제 해결을 위해 문제에서 제시된 조건들을 빠짐없이 코드로 옮기는 능력이 중요합니다. 문자열 처리, 배열 조작, 시뮬레이션 등이 주요 기술입니다.

구현 문제 해결 시 주의할 점은 다음과 같습니다.

꼼꼼하게 문제를 읽고 모든 조건을 파악해야 합니다.
예외 케이스를 고려하여 코드를 작성해야 합니다.
코드의 가독성을 높여 유지보수성을 향상시켜야 합니다.
테스트 케이스를 꼼꼼하게 만들어서 테스트해야 합니다.

3) 시뮬레이션 (Simulation)

시뮬레이션 문제는 문제에서 제시된 과정을 그대로 따라 코드를 작성하여 결과를 예측하는 문제입니다. 문제의 조건에 따라 복잡도가 증가할 수 있으며, 시간 관리가 중요합니다.

시뮬레이션 문제 해결 시에는 다음 사항에 유의해야 합니다.

문제의 조건을 정확하게 이해하고, 각 단계를 코드로 구현해야 합니다.
시간 복잡도를 고려하여 효율적인 코드를 작성해야 합니다.
반복문과 조건문의 사용에 유의하여 코드의 흐름을 제어해야 합니다.
예외 처리를 고려하여 안전한 코드를 작성해야 합니다.

4) 완전 탐색 (Brute Force)

완전 탐색은 가능한 모든 경우의 수를 검사하여 해답을 찾는 방식입니다. 시간 복잡도가 높지만, 문제 해결을 위한 가장 기본적인 방법입니다.

완전 탐색에는 다음과 같은 방법들이 있습니다.

재귀(Recursion): 문제를 작은 부분 문제로 나누어 해결하는 방식입니다.
DFS(Depth-First Search): 깊이 우선 탐색은 그래프나 트리 구조에서 각 노드를 깊이 탐색하는 방식입니다.
BFS(Breadth-First Search): 너비 우선 탐색은 그래프나 트리 구조에서 각 노드를 너비 탐색하는 방식입니다.
순열(Permutation): 주어진 요소들의 모든 순서를 생성하는 방식입니다.
조합(Combination): 주어진 요소들 중에서 특정 개수를 선택하는 모든 경우의 수를 생성하는 방식입니다.

완전 탐색을 사용할 때는 시간 복잡도를 고려하여, 제한 시간 내에 해결 가능한지 확인해야 합니다.

5) 이진 탐색 (Binary Search)

이진 탐색은 정렬된 데이터에서 특정 값을 찾는 효율적인 알고리즘입니다. 시간 복잡도가 O(log n)으로 매우 효율적이며, 정렬된 데이터에만 적용할 수 있습니다.

이진 탐색은 다음과 같은 과정을 거칩니다.

탐색 범위를 반으로 나눕니다.
중간 값을 기준으로, 찾고자 하는 값과 비교합니다.
찾고자 하는 값이 중간 값보다 작으면 왼쪽 범위, 크면 오른쪽 범위에서 다시 탐색을 시작합니다.
탐색 범위를 좁혀가면서 값을 찾을 때까지 반복합니다.

이진 탐색은 정렬된 배열에서 특정 값을 찾는 문제뿐만 아니라, 최적화 문제에도 활용될 수 있습니다.

4. 실전 문제 풀이 예시

다음은 각 유형별 문제 풀이 예시입니다.

1) 그리디: 최소 회의실 수

문제: N개의 회의가 주어지고, 각 회의는 시작 시간과 종료 시간을 갖습니다. 모든 회의를 수용하기 위한 최소 회의실 수를 구하세요.

분석: 회의실을 효율적으로 사용하기 위해서는 겹치는 회의가 최소화되어야 합니다. 종료 시간이 빠른 회의를 먼저 배치하면, 더 많은 회의를 수용할 수 있습니다.

알고리즘:

모든 회의를 종료 시간 기준으로 정렬합니다.
회의실을 사용 중인 회의들의 종료 시간을 저장하는 우선순위 큐(Min-Heap)를 사용합니다.
정렬된 회의를 순회하면서,
- 현재 회의의 시작 시간이 우선순위 큐의 가장 작은 종료 시간보다 크거나 같으면, 해당 회의실을 사용합니다. (큐에서 제거)
- 그렇지 않으면, 새로운 회의실을 할당합니다.
- 현재 회의의 종료 시간을 우선순위 큐에 추가합니다.
우선순위 큐의 크기가 최소 회의실 수입니다.

코드 (Python):

import heapq

def min_meeting_rooms(meetings):
    """
    최소 회의실 수를 계산합니다.

    Args:
        meetings: 회의 시작 시간과 종료 시간의 리스트 (예: [[0, 30], [5, 10], [15, 20]])

    Returns:
        최소 회의실 수
    """
    # 1. 종료 시간 기준으로 정렬
    meetings.sort(key=lambda x: x[1])

    # 2. 회의실 종료 시간 저장하는 우선순위 큐 (Min-Heap)
    rooms = []

    # 3. 회의 순회
    for meeting in meetings:
        start, end = meeting

        # 현재 회의 시작 시간이 회의실 종료 시간보다 크거나 같으면
        if rooms and start >= rooms[0]:
            heapq.heappop(rooms)  # 해당 회의실 제거

        # 새로운 회의실 할당
        heapq.heappush(rooms, end)  # 현재 회의 종료 시간 추가

    # 4. 최소 회의실 수 반환
    return len(rooms)

이미지:

회의실 배정 알고리즘 설명 뒤

2) 구현: 문자열 압축

문제: 문자열을 압축하여 가장 짧은 길이를 구하세요. 압축은 같은 문자가 k개 반복될 경우, k + "문자" 형태로 표현됩니다. (k는 2 이상)

분석: 문자열을 1개, 2개, 3개, ... 단위로 압축해보고, 가장 짧은 길이를 선택합니다.

알고리즘:

문자열을 1부터 문자열 길이/2까지의 단위로 압축을 시도합니다. (압축 단위가 절반을 넘어가면 압축 효과가 없으므로)
각 단위로 문자열을 자르고, 같은 문자열이 반복되는 횟수를 셉니다.
압축된 문자열의 길이를 계산하고, 최솟값을 업데이트합니다.

코드 (Python):

def compress_string(s):
    """
    문자열을 압축하여 가장 짧은 길이를 구합니다.

    Args:
        s: 압축할 문자열

    Returns:
        압축된 문자열의 최소 길이
    """
    n = len(s)
    min_length = n  # 초기 값은 원본 문자열 길이

    for unit in range(1, n // 2 + 1):  # 압축 단위
        compressed = ""
        count = 1  # 반복 횟수
        prev = s[:unit]  # 이전 문자열

        for i in range(unit, n, unit):
            curr = s[i:i + unit]  # 현재 문자열
            if curr == prev:
                count += 1
            else:
                compressed += (str(count) if count > 1 else "") + prev
                prev = curr
                count = 1
        compressed += (str(count) if count > 1 else "") + prev  # 마지막 문자열 처리
        min_length = min(min_length, len(compressed))

    return min_length

3) 시뮬레이션: 2차원 배열 회전

문제: 2차원 배열을 시계 방향으로 90도 회전시키는 코드를 작성하세요.

분석: 배열의 행과 열을 바꾸고, 각 행을 반전시키면 됩니다.

알고리즘:

새로운 배열을 생성하고, 원본 배열의 열을 새로운 배열의 행으로, 행을 열으로 복사합니다.
새로운 배열의 각 행을 반전시킵니다.

코드 (Python):

def rotate_matrix(matrix):
    """
    2차원 배열을 시계 방향으로 90도 회전시킵니다.

    Args:
        matrix: 회전할 2차원 배열

    Returns:
        회전된 2차원 배열
    """
    rows = len(matrix)
    cols = len(matrix[0])

    # 1. 새로운 배열 생성 및 전치
    rotated_matrix = [[0] * rows for _ in range(cols)]
    for r in range(rows):
        for c in range(cols):
            rotated_matrix[c][rows - 1 - r] = matrix[r][c]  # 전치 및 행 반전

    return rotated_matrix

이미지:

2차원 배열 회전 설명 뒤

4) 완전 탐색: 조합 (Combination)

문제: 주어진 숫자 리스트에서 k개의 숫자를 선택하는 모든 조합을 구하세요.

분석: 각 숫자를 선택하거나 선택하지 않는 경우를 재귀적으로 탐색합니다.

알고리즘:

재귀 함수를 사용하여 숫자를 선택하거나 선택하지 않는 경우를 탐색합니다.
현재 선택된 숫자의 개수가 k개이면, 해당 조합을 결과에 추가합니다.
모든 숫자에 대해 탐색을 완료하면 결과를 반환합니다.

코드 (Python):

def combinations(nums, k):
    """
    주어진 숫자 리스트에서 k개의 숫자를 선택하는 모든 조합을 구합니다.

    Args:
        nums: 숫자 리스트
        k: 선택할 숫자의 개수

    Returns:
        모든 조합의 리스트
    """
    result = []

    def backtrack(index, current_combination):
        if len(current_combination) == k:
            result.append(current_combination.copy())  # 값 복사
            return

        if index >= len(nums):
            return

        # 현재 숫자를 선택하지 않는 경우
        backtrack(index + 1, current_combination)

        # 현재 숫자를 선택하는 경우
        current_combination.append(nums[index])
        backtrack(index + 1, current_combination)
        current_combination.pop()  # 백트래킹

    backtrack(0, [])
    return result

5) 이진 탐색: 숫자 찾기

문제: 정렬된 숫자 리스트에서 특정 숫자를 찾는 알고리즘을 구현하세요.

분석: 이진 탐색 알고리즘을 활용하여 효율적으로 숫자를 찾습니다.

알고리즘:

탐색 범위를 리스트 전체로 설정합니다.
중간 인덱스를 계산합니다.
중간 값과 찾고자 하는 값을 비교합니다.
- 중간 값이 찾고자 하는 값보다 작으면, 왼쪽 절반을 탐색 범위로 설정합니다.
- 중간 값이 찾고자 하는 값보다 크면, 오른쪽 절반을 탐색 범위로 설정합니다.
- 중간 값과 찾고자 하는 값이 같으면, 해당 인덱스를 반환합니다.
탐색 범위가 유효할 때까지 3단계를 반복합니다.
값을 찾지 못하면 -1을 반환합니다.

코드 (Python):

def binary_search(nums, target):
    """
    정렬된 숫자 리스트에서 특정 숫자를 이진 탐색으로 찾습니다.

    Args:
        nums: 정렬된 숫자 리스트
        target: 찾고자 하는 숫자

    Returns:
        찾는 숫자의 인덱스. 없으면 -1 반환
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

5. 문제 풀이 연습 및 전략

1) 꾸준한 연습

코딩 테스트는 꾸준한 연습을 통해 실력을 향상시킬 수 있습니다. 매일 꾸준히 문제를 풀고, 다양한 유형의 문제에 도전하세요.

2) 문제 풀이 사이트 활용

백준, 프로그래머스, LeetCode 등 다양한 문제 풀이 사이트를 활용하여 연습하세요.

3) 오답노트 작성

틀린 문제는 오답노트에 정리하고, 왜 틀렸는지 분석하여 같은 실수를 반복하지 않도록 합니다.

4) 시간 관리 연습

코딩 테스트는 제한 시간 내에 문제를 해결해야 합니다. 시간 관리를 위해, 문제 풀이 시간을 정해놓고 연습하고, 시간 복잡도를 고려하여 효율적인 코드를 작성하는 연습을 해야 합니다.

5) 코드 스타일 일관성 유지

코드의 가독성은 매우 중요합니다. 일관된 코드 스타일을 유지하고, 주석을 사용하여 코드의 의미를 명확하게 전달합니다.

6) 동료와의 협력

다른 사람들과 함께 문제를 풀고, 코드 리뷰를 통해 서로의 실력을 향상시킬 수 있습니다.

6. 결론

코딩 테스트는 문제 해결 능력과 알고리즘 지식을 종합적으로 평가하는 중요한 과정입니다. 문제 분석, 적절한 알고리즘 선택, 효율적인 코드 작성, 그리고 꾸준한 연습을 통해 코딩 테스트에서 좋은 결과를 얻을 수 있습니다. 다양한 유형의 문제를 풀어보면서 실전 감각을 익히고, 꾸준한 노력을 통해 코딩 실력을 향상시키세요.

실패를 두려워하지 말고, 끊임없이 배우고 성장하는 자세로 코딩 테스트에 임한다면, 원하는 목표를 달성할 수 있을 것입니다.