코딩 테스트: 문제 풀이를 설명하는 6단계

코딩 면접에서 평가되는 것은 코드가 아닙니다

화이트보드나 공유 편집기에서 문제를 푸는 면접의 실제 평가 대상은 완성된 코드가 아니라 코드에 도달하는 과정입니다. 같은 정답을 냈어도, 문제를 다시 진술하고 제약을 확인한 뒤 후보를 비교하고 하나를 골라 검증한 사람과, 침묵하다가 갑자기 완성된 코드를 내놓은 사람은 다르게 기록됩니다. 후자는 정답을 외웠을 가능성과 구분되지 않기 때문입니다.

그래서 이 페이지는 알고리즘 자체보다 순서를 다룹니다. 문제를 받은 순간부터 코드를 다 쓰고 검증할 때까지 어떤 말을 어떤 순서로 하는지, 그리고 막혔을 때 어떻게 빠져나오는지를 하나의 문제로 끝까지 보여 드립니다.

진행 순서: 다섯 구간

1. 재진술과 확인. 문제를 자기 말로 한 문장으로 다시 말하고, 입력 형태와 반환값을 확정합니다. 여기서 어긋나면 뒤가 전부 무의미합니다.
2. 제약에서 목표 복잡도 도출. 입력 크기를 보고 어느 정도 복잡도까지 허용되는지 먼저 정합니다. 목표가 없으면 최적화의 기준도 없습니다.
3. 브루트포스 명시. 가장 단순한 정답을 말로 설명하고 그 비용을 계산합니다. 이것이 이후 개선의 기준선이 됩니다.
4. 병목 지목과 개선. 브루트포스에서 낭비되는 계산을 정확히 지목하고, 그것을 없애는 자료구조나 성질을 도입합니다.
5. 구현과 검증. 코드를 쓰고, 경계 입력을 손으로 통과시킵니다.

이 순서에서 가장 자주 생략되는 것이 3번입니다. 브루트포스가 부끄럽다고 생각해서 건너뛰는 경우가 많은데, 실제로는 반대입니다. 브루트포스를 말하지 않으면 개선안이 왜 개선인지 설명할 기준이 없어집니다.

연습 문제: 회의실 하나에 최대한 많은 회의 넣기

시작 시각과 종료 시각을 가진 회의 목록이 주어집니다. 회의실은 하나이고 시간이 겹치는 회의는 함께 넣을 수 없습니다. 최대 몇 개의 회의를 배정할 수 있습니까.

1구간 · 재진술과 확인

“구간 목록에서 서로 겹치지 않는 부분집합 중 크기가 가장 큰 것의 크기를 구하는 문제로 이해했습니다. 몇 가지 확인하겠습니다. 한 회의가 끝나는 시각과 다음 회의가 시작하는 시각이 같으면 겹치는 것으로 봅니까, 아니면 연달아 배치해도 됩니까? 시작이 종료보다 늦은 잘못된 입력이 들어올 수 있습니까? 회의 개수의 상한은 얼마입니까? 배정 개수만 필요합니까, 어떤 회의를 골랐는지도 필요합니까?”

경계 정의를 묻는 첫 질문이 특히 중요합니다. 이 문제에서 등호 처리는 단순한 세부사항이 아니라 비교 연산자를 결정하고, 나중에 만들 테스트의 절반을 좌우합니다. 여기서는 끝나는 시각과 시작 시각이 같으면 배치 가능하고, 개수만 반환하면 되며, 회의 수는 십만 규모라고 답을 받았다고 하겠습니다.

2구간 · 목표 복잡도

“회의 수가 십만이면 제곱은 백억이라 통과할 수 없고, n log n이나 n이면 여유가 있습니다. 그러면 정렬 한 번 정도는 예산 안에 들어옵니다.” 이 한 마디로 이후 탐색 범위가 확 좁아집니다. 목표를 먼저 정해 두면 “모든 부분집합을 보면 어떨까” 같은 방향을 스스로 빠르게 폐기할 수 있습니다.

3구간 · 브루트포스

“가장 단순한 정답은 모든 부분집합을 만들어 겹침이 없는지 확인하고 가장 큰 것을 고르는 것입니다. 부분집합이 2의 n제곱 개라 십만에서는 불가능하지만, 정답의 정의를 확정해 준다는 점에서 의미가 있습니다. 이 완전 탐색이 낭비하는 지점은 명확합니다. 어떤 회의를 넣을지 정할 때, 이미 확정된 앞부분과 무관하게 남은 시간 구간만 보면 되는데도 조합 전체를 다시 만들고 있습니다.”

4구간 · 병목 제거

“핵심은 이겁니다. 앞에서 어떤 회의를 골랐든, 남은 선택에 영향을 주는 유일한 정보는 회의실이 언제 비는가입니다. 그러면 매 시점에서 회의실이 가장 빨리 비도록 고르는 것이 항상 최소한 손해는 아닙니다. 즉 종료 시각이 가장 이른 회의를 먼저 고르는 그리디입니다.

교환 논증으로 정당화하겠습니다. 어떤 최적해가 종료 시각이 가장 이른 회의 e를 포함하지 않는다고 합시다. 그 최적해에서 첫 번째 회의를 e로 바꿔치기해도 e의 종료 시각이 더 이르거나 같으므로 뒤따르는 회의들과 여전히 겹치지 않고, 개수도 그대로입니다. 따라서 e를 포함하는 최적해가 반드시 존재합니다. 같은 논증을 남은 문제에 반복하면 그리디가 최적임이 나옵니다.

구현은 종료 시각 오름차순 정렬 후 한 번 훑기이므로 O(n log n) 시간, O(1) 추가 공간입니다. 시작 시각 기준 정렬을 버린 이유는, 시작이 이른 긴 회의 하나가 짧은 회의 여러 개를 막을 수 있어 최적성이 깨지기 때문입니다.”

약한 답과의 차이

약한 답은 이렇습니다. “정렬해서 앞에서부터 겹치지 않으면 넣으면 됩니다. 그리디로 풀립니다. O(n log n)입니다.” 결론은 같습니다. 그런데 무엇으로 정렬하는지 말하지 않았고, 왜 그 기준이어야 하는지 근거가 없으며, 그리디가 왜 최적인지도 없습니다. 면접관이 “시작 시각으로 정렬하면 안 되나요”라고 물으면 그 자리에서 무너집니다.

강한 답이 우월한 이유는 어휘가 아니라 순서입니다. 재진술로 문제를 고정하고, 제약에서 예산을 뽑고, 브루트포스로 기준선을 세우고, 낭비를 지목하고, 대안을 도입하면서 근거를 붙이고, 버린 후보를 왜 버렸는지 말했습니다. 이 순서가 있으면 면접관이 조건을 바꿔도 같은 순서를 다시 돌리기만 하면 됩니다. 순서가 없으면 조건이 바뀔 때마다 처음부터 헤맵니다.

def max_meetings(meetings):
    """meetings: [(start, end), ...]  겹치지 않게 배정 가능한 최대 개수"""
    if not meetings:
        return 0

    # 종료 시각 오름차순. 종료가 같으면 시작이 늦은 쪽이 짧으므로 먼저 둔다.
    meetings.sort(key=lambda m: (m[1], m[0]))

    count = 0
    last_end = float('-inf')
    for start, end in meetings:
        # 확인한 규칙: 끝나는 시각 == 시작 시각이면 연달아 배치 가능
        if start >= last_end:
            count += 1
            last_end = end
    return count


# 손으로 통과시키는 경계 입력
assert max_meetings([]) == 0                      # 빈 입력
assert max_meetings([(1, 2)]) == 1                # 원소 하나
assert max_meetings([(1, 5), (1, 5), (1, 5)]) == 1  # 전부 동일
assert max_meetings([(1, 3), (3, 5), (5, 7)]) == 3  # 맞닿는 경계
assert max_meetings([(1, 10), (2, 3), (4, 5)]) == 2 # 긴 회의의 함정
assert max_meetings([(5, 6), (1, 2), (3, 4)]) == 3  # 정렬 안 된 입력

마지막에서 두 번째 케이스가 이 문제의 핵심 반례입니다. 시작 시각으로 정렬했다면 (1, 10)을 먼저 잡아 답이 1이 나옵니다. 이런 케이스를 스스로 만들어 놓고 “제 풀이가 이 입력에서 어떻게 동작하는지 확인하겠습니다”라고 말하면서 돌려 보는 것이, 코드를 다 쓴 뒤 “맞는 것 같습니다”로 끝내는 것보다 훨씬 강하게 읽힙니다.

막혔을 때 빠져나오는 법

실제 면접에서 가장 위험한 순간은 모르는 문제를 만났을 때가 아니라 아는 척하며 침묵하는 순간입니다. 막혔을 때는 다음 세 가지를 소리 내어 시도하십시오.

첫째, 문제를 축소합니다. n이 3일 때 손으로 풀어 보고 규칙을 찾습니다. 둘째, 제약 하나를 제거합니다. “회의실이 무한개라면”, “모든 회의 길이가 같다면” 같은 완화된 문제를 풀고 원래 조건을 다시 붙입니다. 셋째, 자기 브루트포스가 어디서 같은 계산을 반복하는지 찾습니다. 대부분의 최적화는 중복 계산 제거이거나 정렬로 만든 성질의 활용, 둘 중 하나입니다.

그리고 막혔다는 사실 자체를 말해도 됩니다. “지금 이 부분에서 겹침 판정 비용을 줄이는 방법이 안 떠오릅니다. 정렬로 순서를 만들면 왼쪽만 보면 될 것 같은데 이 방향으로 더 보겠습니다”는 완전히 정상적인 발화이고, 침묵보다 훨씬 좋은 정보를 줍니다.

면접관이 이어서 묻는 것들

이 과정에서 자주 나오는 실수

가장 흔한 것은 문제를 다 듣기 전에 코드를 시작하는 것입니다. 반환값이 개수인지 목록인지도 확정하지 않고 짜기 시작하면 중간에 갈아엎게 되고, 그 모습은 요구사항 확인을 안 하는 사람으로 기록됩니다.

두 번째는 복잡도를 자신 있게 틀리게 말하는 것입니다. 정렬을 쓰고도 O(n)이라고 하거나, 이중 루프 안에서 리스트를 매번 새로 만들면서 그 비용을 세지 않는 경우가 많습니다. 모르면 “정렬이 지배해서 n log n으로 보이는데, 안쪽에서 슬라이스를 만들면 그만큼 더 붙습니다”처럼 불확실성을 드러내는 편이 낫습니다.

세 번째는 검증 생략입니다. 코드를 다 쓰고 “맞을 것 같습니다”로 끝내면, 앞의 좋은 과정이 마지막에 깎입니다. 예시 하나를 처음부터 끝까지 변수 값을 말하며 통과시키는 데 1분이면 충분합니다.

네 번째는 힌트를 무시하는 것입니다. 면접관이 “정렬을 하면 뭐가 편해질까요”라고 물으면 그것은 방향 제시입니다. 자기 접근을 고수하면서 힌트를 흘려보내는 태도는 협업 신호로 나쁘게 읽힙니다. 디버깅과 문제 추적을 순서로 다루는 감각은 디버깅은 재능이 아니라 순서다에서 더 볼 수 있습니다.

문제를 받은 순간 확인할 것

• 문제를 내 말로 한 문장으로 다시 말했는가
• 입력 형태, 반환값, 경계 규칙을 확정했는가
• 입력 크기에서 목표 복잡도를 먼저 정했는가
• 브루트포스를 말하고 그 비용을 계산했는가
• 브루트포스의 낭비 지점을 한 문장으로 지목했는가
• 고른 접근이 왜 맞는지 근거나 반례를 댔는가
• 버린 후보를 왜 버렸는지 말했는가
• 경계 입력 여섯 개를 코드로 통과시켰는가

연습 설계

새 문제를 많이 푸는 것보다 한 문제로 다섯 구간을 소리 내어 말하는 훈련이 효과가 큽니다. 타이머를 재고, 재진술 30초, 복잡도 목표 20초, 브루트포스 1분, 개선 2분, 구현과 검증 6분으로 끊어 보십시오. 어느 구간에서 계속 시간이 새는지 금방 드러납니다. 대개는 4구간에서 근거 없이 방황하는 경우가 많고, 그 원인은 3구간을 건너뛴 데 있습니다.

기본기가 흔들린다면 파이썬 기초 가이드로 손을 풀고, 자료구조 선택 감각은 자료구조 선택, 상태 정의는 DP와 탐색에서 이어 보시기 바랍니다. 전체 학습 경로는 심층 가이드에 정리되어 있습니다.

관련 언어 학습으로 복습하기