문제 풀이 절차

면접에서 문제를 받자마자 코드를 치기 시작하면 요구 사항을 잘못 이해했거나 더 나은 방법을 놓쳤다는 사실을 너무 늦게 알게 됩니다. 이 장에서는 여섯 단계로 이루어진 절차를 예제 하나에 적용해 봅니다. 순서는 질문으로 범위 확정 → 예시 만들기 → 무차별 대입 → 최적화 → 코드 작성 → 테스트입니다.

예제 문제는 다음과 같습니다. "양의 정수 배열 nums와 목표값 target이 주어질 때, 합이 target 이상인 연속 구간 가운데 가장 짧은 구간의 길이를 구하라. 그런 구간이 없으면 0을 돌려준다."

1단계: 질문으로 범위 확정

문제를 소리 내어 다시 말하고, 모호한 부분을 질문합니다. 이 단계에서 나온 답이 이후 알고리즘 선택을 바꿉니다.

• 원소가 모두 양수인가요? 음수가 있으면 구간을 늘릴 때 합이 줄어들 수 있어 다른 방법이 필요합니다.
• 배열이 비어 있을 수 있나요? 이때는 0을 돌려주면 되나요?
• 배열 길이와 값의 범위는 어느 정도인가요? n이 10만이라면 O(n²)은 위험합니다.
• 구간 길이만 필요한가요, 아니면 구간의 위치도 필요한가요?

여기서는 "모두 양수, n은 최대 10만, 길이만 필요"라는 답을 받았다고 가정합니다.

2단계: 예시 직접 만들기

주어진 예시만 믿지 말고 작은 예시를 직접 만들어 기대 결과를 손으로 구합니다. 일반적인 경우 하나와 경계 조건 두세 개가 적당합니다.

3단계: 무차별 대입

가장 단순한 풀이를 먼저 말합니다. 시작점마다 오른쪽으로 늘려 가며 합이 target 이상이 되는 순간의 길이를 기록합니다. 시간은 O(n²)입니다. 코드로 다 쓰지 않더라도 말로 설명하고 복잡도를 밝혀 두면, 최적화의 기준점이 생기고 나중에 테스트용 정답 함수로도 쓸 수 있습니다.

def shortest_at_least_brute(nums: list[int], target: int) -> int:
    best = 0
    for start in range(len(nums)):
        total = 0
        for end in range(start, len(nums)):
            total += nums[end]
            if total >= target:
                length = end - start + 1
                if best == 0 or length < best:
                    best = length
                break  # 더 늘려도 길어지기만 한다
    return best

4단계: 최적화

무차별 대입에서 반복되는 일을 찾습니다. 시작점이 한 칸 옮겨 갈 때마다 합을 처음부터 다시 구하고 있습니다. 그런데 원소가 모두 양수이므로 다음 성질이 성립합니다.

• 오른쪽 끝을 늘리면 합은 커지기만 합니다.
• 왼쪽 끝을 줄이면 합은 작아지기만 합니다.

따라서 오른쪽 끝을 하나씩 늘리다가 합이 target 이상이 되면, 조건이 깨지기 직전까지 왼쪽 끝을 당기며 가장 짧은 길이를 갱신하면 됩니다. 이것이 가변 크기 슬라이딩 윈도우입니다. 두 포인터가 각각 최대 n번만 움직이므로 전체 시간은 O(n)입니다. 이 결론을 면접관에게 먼저 말하고 동의를 얻은 뒤에 코드로 넘어갑니다.

nums = [3, 1, 2, 4, 1], target = 6으로 따라가 봅니다.

5단계: 코드 작성

생각한 대로 코드를 쓰면서, 각 줄이 왜 필요한지 짧게 말합니다. 변수 이름은 left, right, total처럼 역할이 드러나게 짓습니다.

def shortest_at_least(nums: list[int], target: int) -> int:
    left = 0
    total = 0
    best = float("inf")
    for right, value in enumerate(nums):
        total += value
        while total >= target:          # 조건을 만족하는 동안 창을 줄인다
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else int(best)

6단계: 테스트

코드를 다 썼다고 끝이 아닙니다. 2단계에서 만든 예시를 한 줄씩 따라가 보고, 경계 조건을 확인합니다. 시간이 남으면 무차별 대입 함수와 결과를 비교하는 무작위 테스트를 언급하면 좋은 인상을 줍니다.

cases = [
    ([3, 1, 2, 4, 1], 6, 2),
    ([1, 1, 1], 5, 0),
    ([7], 7, 1),
    ([], 1, 0),
]
for nums, target, expected in cases:
    assert shortest_at_least(nums, target) == expected
    assert shortest_at_least_brute(nums, target) == expected
print("all tests passed")

45분 면접의 시간 배분

정리

여섯 단계는 순서대로 밟는 의식이라기보다 실수를 막는 안전장치입니다. 질문으로 조건을 확정하면 알고리즘이 정해지고, 무차별 대입은 기준점과 테스트 도구가 되며, 최적화 아이디어를 먼저 합의하면 코드를 고쳐 쓰는 일이 줄어듭니다. 다음 장에서는 자주 쓰는 패턴을 실제 코드로 구현해 봅니다.