알고리즘과 라이브 코딩 - 생각을 말하며 풀기

이 장에서 배우는 것

라이브 코딩(live coding)은 제한된 시간에 코드를 작성하면서 문제를 이해하고 해결하는 과정을 보여 주는 면접이다. 실행되는 코드는 중요한 결과물이지만, 면접관은 그 코드에 도달하는 판단도 확인한다. 조건을 잘못 이해한 채 빠르게 작성하는 지원자보다, 불확실한 조건을 확인하고 작은 예시로 풀이를 검증하는 지원자가 자신의 사고 과정을 더 잘 드러낸다.

앞 장에서 자료구조의 특징을 설명했다면, 여기서는 그 특징을 문제 해결에 연결한다. 가상의 중고 거래 서비스 팀 면접에서 두 상품의 가격 합을 검사하는 문제를 풀며, 처음 떠올린 풀이를 설명하고 개선하는 과정을 따라간다. 경험을 말하는 예시는 답변 구성용이므로, 실제 면접에서는 자신이 수행한 과제나 프로젝트 사실로 바꾸어야 한다.

문제를 자신의 말로 다시 설명하고, 입력·출력·제약을 확인한다.
단순한 풀이를 먼저 제시하고 중복 계산을 찾아 개선한다.
정렬·이분 탐색·투 포인터·너비 우선 탐색·동적 계획법을 검토할 신호를 구분한다.
경계 사례를 만들고, 막혔을 때 확인한 사실과 다음 시도를 말한다.
같은 문제의 O(N²) 풀이와 O(N) 풀이를 실행해 결과와 작업량을 비교한다.

문제 상황

중고 거래 서비스에 묶음 구매 후보를 보여 주는 기능을 검토하고 있다. 사용자가 예산을 입력하면, 등록된 상품 가운데 가격 합이 예산과 정확히 같은 두 상품의 조합 수를 계산하려 한다. 이번 면접에서는 상품 설명이나 판매 상태를 제외하고 정수 가격 목록만 다룬다.

면접관: 가격 목록과 목표 금액이 주어질 때, 서로 다른 두 상품의 가격 합이 목표 금액인 조합 수를 구하라. 목록의 서로 다른 위치는 서로 다른 상품이다. 같은 두 상품을 순서만 바꾸어 다시 세면 안 된다.

지원자는 바로 반복문을 작성하려다가 멈춘다. 가격이 같은 상품을 하나로 취급하는지, 같은 상품을 두 번 사용할 수 있는지부터 확인해야 하기 때문이다. 예를 들어 가격이 [4, 4, 4]이고 목표 금액이 8이면, 가격의 종류만 보면 한 가지지만 상품 조합은 세 가지다. 이 차이를 놓치면 빠른 알고리즘을 작성해도 다른 문제를 푼 셈이다.

실제 가격에는 음수가 없더라도, 면접의 입력 조건은 별도로 정해야 한다. 이 장의 연습에서는 검증 범위를 넓히기 위해 음수와 0도 허용하는 정수 목록으로 합의한다. 운영 기능에서 어떤 가격을 허용할지는 별개의 요구사항이며, 여기서는 주어진 수열에서 조합 수를 정확히 계산하는 데 집중한다.

면접관이 확인하는 사고 과정

소통은 생각나는 모든 말을 실시간으로 나열하는 일이 아니다. 현재 이해한 조건, 선택한 풀이의 근거, 검증 결과를 상대가 따라올 수 있게 전달하는 일이다. 테스트는 코드를 다 작성한 뒤 붙이는 절차에 그치지 않는다. 풀이를 고르는 동안 예시를 대입하는 것도 테스트다. 개선 역시 복잡한 기법의 이름을 말하는 것보다 어떤 작업을 줄였는지 설명하는 데 의미가 있다.

라이브 코딩에서 나올 수 있는 질문과 평가 의도
질문	의도	답변 핵심	꼬리 질문
문제를 자신의 말로 설명해 보라.	조건을 정확히 이해했는지 확인한다.	입력, 출력, 조합의 기준을 다시 말한다.	같은 가격이면 같은 상품인가?
직접 작은 예시를 만들어 보라.	추상적인 조건을 구체화하는지 본다.	정상 사례와 중복 가격 사례를 만든다.	답이 0인 예시는?
가장 단순한 풀이는 무엇인가?	실행 가능한 출발점을 찾는지 본다.	모든 i < j 쌍을 확인한다.	왜 j를 i + 1부터 시작하는가?
더 빠르게 만들 수 있는가?	반복 작업을 찾아 줄이는지 본다.	이전에 본 가격의 빈도를 저장한다.	집합으로도 충분한가?
정렬하면 무엇이 좋아지는가?	순서가 주는 이점을 이해하는지 본다.	양 끝에서 합을 조절할 수 있다.	중복 가격은 어떻게 세는가?
이분 탐색은 언제 검토하는가?	탐색 조건을 이해하는지 본다.	정렬된 범위나 단조로운 판정이 필요하다.	정렬되지 않은 목록이라면?
최소 이동 횟수를 구한다면?	문제 형태와 탐색 방법을 연결하는지 본다.	이동 비용이 같으면 너비 우선 탐색을 검토한다.	이동 비용이 다르면?
작은 문제의 답이 반복된다면?	상태와 점화 관계를 정의하는지 본다.	동적 계획법의 상태와 전이를 설명한다.	상태에 무엇을 저장해야 하는가?
어떤 경계 사례를 확인하겠는가?	실패 조건을 예상하는지 본다.	빈 목록, 원소 하나, 중복, 해 없음 등을 확인한다.	같은 원소를 두 번 쓰지 않는가?
풀이가 떠오르지 않으면 어떻게 하겠는가?	불확실한 상황에서의 대응을 본다.	막힌 지점을 구분하고 작은 입력으로 돌아간다.	힌트를 받은 뒤 무엇을 확인하는가?

깊게 보기: 문제를 자신의 말로 설명해 보라

같은 질문에 대한 답변의 차이
수준	답변 예시	드러나는 차이
나쁜 답	두 수를 더하면 되는 문제다. 바로 작성하겠다.	상품의 동일성과 중복 집계 기준을 생략한다.
보통 답	합이 목표 금액인 두 원소의 쌍을 센다. 이중 반복문으로 풀겠다.	목표는 이해했지만 모호한 조건을 남긴다.
좋은 답	서로 다른 위치 두 개를 고르고 순서를 무시해 센다. 같은 가격도 위치가 다르면 별도 상품으로 이해했다. [4, 4, 4]와 목표 8의 답이 3인지 확인하겠다.	판정 기준을 검증 가능한 예시로 바꾼다.

모범 답안: 서로 다른 위치의 두 원소를 골라 합이 목표 금액인 조합 수를 구하는 문제로 이해했다. 위치를 기준으로 해야 같은 가격의 상품도 구분할 수 있기 때문이다. 작은 예로 [4, 4, 4]에서 목표가 8이면 위치 조합은 세 개다. 이 기준으로 풀되, 가격 중복을 하나로 묶는 요구라면 출력의 의미와 집계 방법을 다시 정하겠다.

면접관: 같은 상품을 두 번 쓰는 것은 어떻게 막겠는가?

지원자: 단순한 풀이에서는 두 번째 위치를 첫 번째 위치 다음부터 고르겠다. 개선한 풀이에서는 현재 상품을 저장하기 전에 이전 상품들과의 조합만 계산하겠다.

이 답은 결론을 먼저 말하고, 위치를 구분하는 이유와 예시를 붙인 뒤, 요구가 달라질 때의 한계를 밝힌다. 질문을 되풀이하는 데서 끝나지 않고 자신이 어떤 입력에 어떤 출력을 낼지 약속한 것이다.

깊게 보기: 가장 단순한 풀이에서 어떻게 개선하겠는가

먼저 i보다 뒤에 있는 j를 모두 확인하면 된다. 검사하는 쌍은 N(N−1)/2개다. N이 커지면 작업량이 대략 N의 제곱에 비례하므로 시간 복잡도는 O(N²)다. 별도 저장 공간은 입력 크기와 무관한 몇 개의 변수뿐이므로 보조 공간은 O(1)이다. 단순한 풀이를 제시하는 목적은 머무르기 위해서가 아니라, 정답의 기준과 줄일 작업을 명확하게 만드는 데 있다.

모범 답안: 먼저 모든 서로 다른 위치 쌍을 확인하는 풀이를 작성한 뒤, 이전 가격의 빈도를 저장해 반복 탐색을 줄이겠다. 현재 가격이 x이면 필요한 가격은 목표 금액에서 x를 뺀 값이고, 이전에 그 가격이 나온 횟수만큼 새 조합이 생긴다. 예를 들어 이전 가격이 [1, 1]이고 현재 가격이 7이라면 목표 8에 대해 두 조합을 더한다. 다만 해시 기반 사전의 조회·갱신이 평균적으로 O(1)이라는 전제에서 전체 기대 시간은 O(N)이며, 서로 다른 가격을 저장하는 공간은 최대 O(N)이 든다.

면접관: 집합에 이전 가격을 넣으면 더 간단하지 않은가?

지원자: 조합의 존재 여부만 묻는다면 집합을 검토할 수 있다. 여기서는 조합 수를 세므로 이전에 1이 두 번 나왔다는 정보가 필요하다. 집합은 이 횟수를 보존하지 못한다.

한 번의 순회라는 설명만으로 정확성이 증명되지는 않는다. 각 단계에서 유지되는 조건도 말해야 한다. 현재 원소를 처리하기 직전 사전에는 앞선 위치의 가격별 개수만 들어 있다. 따라서 더하는 모든 조합은 서로 다른 위치로 구성되고, 각 조합은 뒤쪽 원소를 처리할 때 한 번만 계산된다. 이 조건이 갱신 순서를 결정한다.

이전 가격의 빈도를 조회한 다음 현재 가격을 저장하면 자기 자신과의 조합을 막을 수 있다

풀이를 고르는 신호와 검증 방법

알고리즘 이름을 먼저 정하고 문제를 끼워 맞추면 조건을 놓치기 쉽다. 입력의 구조와 필요한 출력부터 보고 후보를 좁힌다. 아래의 신호는 검토를 시작할 근거이며, 적용을 확정하는 규칙은 아니다.

정렬: 상대적인 크기나 인접 관계가 중요하고, 원래 순서를 바꾸어도 되거나 별도로 보존할 수 있을 때 검토한다. 정렬 비용과 복사 공간까지 포함해 판단한다.
이분 탐색(binary search): 정렬된 범위에서 위치를 찾거나, 후보 값을 늘릴 때 가능 여부가 한 방향으로만 바뀌는 경우에 검토한다. 매 단계에서 정답 후보 구간을 줄일 수 있어야 한다.
투 포인터(two pointers): 두 위치를 이동시키며 후보를 안전하게 제외할 수 있을 때 검토한다. 정렬된 수열의 양 끝 합이나, 조건을 유지하며 움직이는 연속 구간이 예다.
너비 우선 탐색(BFS): 상태 사이를 한 번 이동하는 비용이 같고, 시작점에서 최소 이동 횟수를 구할 때 검토한다. 방문 처리를 통해 같은 상태의 중복 확장을 막는다.
동적 계획법(DP): 같은 작은 문제의 답이 반복해서 필요하고, 그 답을 조합해 더 큰 문제의 답을 구할 수 있을 때 검토한다. 상태의 의미, 전이, 시작값과 계산 순서를 먼저 정한다.

이번 문제도 정렬 후 양 끝에서 합을 조절하는 풀이가 가능하다. 그러나 중복 가격이 있으면 양쪽 가격의 개수를 묶어 조합 수를 계산해야 한다. 정렬 비용까지 포함하면 일반적으로 O(N log N)이다. 사전 풀이와 비교할 때는 시간뿐 아니라 추가 공간, 입력 순서 보존, 중복 처리의 설명 난이도를 함께 살펴야 한다.

양 끝의 합이 작으면 왼쪽을 오른쪽으로 옮겨도 되는 이유는 정렬에 있다. 현재 왼쪽 값과 현재 오른쪽 이하의 어떤 값을 더해도 목표에 미치지 못하므로, 현재 왼쪽 값으로 만들 조합을 제외할 수 있다. 반대로 정렬되지 않은 목록에서는 이 판단이 성립하지 않는다. 기법의 이름보다 후보를 버려도 되는 근거가 먼저다.

깊게 보기: 어떤 경계 사례를 확인하겠는가

모범 답안: 입력 크기와 중복 조건을 나누어 확인하겠다. 빈 목록과 원소 하나는 두 상품을 고를 수 없어 0이어야 한다. 같은 가격이 여러 개면 개수 정보가 보존되는지 확인해야 한다. 예를 들어 [0, 0, 0]의 목표 0은 세 조합이며, [4]의 목표 8은 0이다. 이 사례들이 모든 오류를 증명하지는 못하므로, 작성 후에는 작은 입력들을 단순한 풀이와 대조하겠다.

면접관: 두 풀이의 결과가 같으면 정답이라고 할 수 있는가?

지원자: 일치 검사는 오류를 찾는 데 도움이 되지만 둘 다 같은 조건을 잘못 이해할 수 있다. 손으로 계산한 기대값도 함께 확인하고, 각 쌍을 한 번씩 센다는 근거를 설명하겠다.

경계 사례는 길게 나열하기보다 우려하는 오류와 연결하면 좋다. 빈 목록은 반복문이 실행되지 않는 경우를, 원소 하나는 자기 자신을 쓰는 오류를, 반복 가격은 빈도를 잃는 오류를 드러낸다. 음수 사례는 양수라는 가정을 몰래 사용했는지 확인한다. 해가 없는 사례는 초기값과 반환값을 점검한다.

깊게 보기: 막혔을 때 어떻게 하겠는가

모범 답안: 현재 막힌 부분을 구분해서 말하고, 손으로 계산할 수 있는 입력으로 돌아가겠다. 문제 이해가 불확실한지, 개선 방법이 안 보이는지, 작성한 코드가 틀리는지에 따라 다음 행동이 다르기 때문이다. 이 문제에서 개선이 떠오르지 않으면 이중 반복문을 기준으로 각 현재 가격이 이전 목록에서 무엇을 찾는지 적어 보겠다. 그래도 진전이 없다면 확인한 접근과 막힌 이유를 설명하고 힌트를 요청하겠다.

면접관: 이전 값을 저장해 보라는 힌트를 주겠다.

지원자: 이전 가격의 존재뿐 아니라 횟수가 필요하므로 빈도 사전을 검토하겠다. 먼저 [4, 4, 4]로 조회와 저장 순서를 손으로 확인한 뒤 코드에 반영하겠다.

힌트를 받은 뒤 곧바로 정답 코드를 쓰는 것보다, 힌트가 어떤 반복 작업을 없애는지 설명하는 편이 이해를 드러낸다. 구현 중 오류가 나면 실패 입력을 줄이고 예상 상태와 실제 상태를 비교한다. 시간이 부족하다면 현재 실행 가능한 풀이, 남은 문제, 개선 방향을 분리해 전달한다. 풀지 못한 부분을 해결한 것처럼 말할 필요는 없다.

막혔을 때는 문제 이해, 풀이 개선, 구현 오류 중 어디에서 막혔는지 구분하고 다음 행동을 정한다

완성 코드

다음 코드를 main.py로 저장한다. Python 3.12 이상 표준 환경에서 외부 패키지 없이 실행한다. 입력은 모두 고정되어 있으며 난수와 현재 시각을 사용하지 않는다. 두 함수는 조합 수와 작업 횟수를 반환한다.

작업 횟수의 단위는 의도적으로 구분한다. 단순한 풀이는 검사한 위치 쌍을, 개선한 풀이는 처리한 원소를 센다. 서로 같은 비용의 명령어를 센 값은 아니므로 실제 속도 비율로 해석하면 안 된다. 입력 크기에 따라 각 풀이가 수행하는 핵심 작업이 얼마나 늘어나는지 확인하는 실험이다.

def count_pairs_quadratic(
    prices: list[int], target: int
) -> tuple[int, int]:
    pairs = 0
    checks = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            checks += 1
            if prices[i] + prices[j] == target:
                pairs += 1
    return pairs, checks


def count_pairs_linear(
    prices: list[int], target: int
) -> tuple[int, int]:
    seen: dict[int, int] = {}
    pairs = 0
    steps = 0
    for price in prices:
        steps += 1
        needed = target - price
        pairs += seen.get(needed, 0)
        seen[price] = seen.get(price, 0) + 1
    return pairs, steps


def verify(
    prices: list[int], target: int, expected: int
) -> tuple[int, int, int]:
    slow_pairs, checks = count_pairs_quadratic(prices, target)
    fast_pairs, steps = count_pairs_linear(prices, target)
    if slow_pairs != fast_pairs or slow_pairs != expected:
        raise AssertionError(
            f"mismatch: slow={slow_pairs}, "
            f"fast={fast_pairs}, expected={expected}"
        )
    return slow_pairs, checks, steps


def main() -> None:
    cases = [
        ("empty", [], 8, 0),
        ("single", [4], 8, 0),
        ("duplicates", [4, 4, 4, 4], 8, 6),
        ("mixed", [1, 7, 3, 5, 7], 8, 3),
        ("zeros", [0, 0, 0], 0, 3),
        ("negative", [-2, 6, 1, 3, 4], 4, 2),
        ("no_match", [2, 4, 6], 9, 0),
    ]
    print("cases: name pairs pair_checks item_steps")
    for name, prices, target, expected in cases:
        pairs, checks, steps = verify(prices, target, expected)
        print(f"{name}: {pairs} {checks} {steps}")
    print("all 7 cases: OK")

    print("growth: n pairs pair_checks item_steps")
    for n in (10, 100, 1000):
        prices = [4] * n
        expected = n * (n - 1) // 2
        pairs, checks, steps = verify(prices, 8, expected)
        print(f"{n}: {pairs} {checks} {steps}")


if __name__ == "__main__":
    main()

줄별 해설

count_pairs_quadratic의 선언부는 정수 목록과 목표 금액을 받고 두 정수를 반환한다고 표시한다. 반환값의 첫째는 조합 수, 둘째는 검사 횟수다. 타입 표기는 설명과 도구의 분석을 돕지만, 실행 중 입력을 자동으로 검사하지는 않는다.

pairs = 0과 checks = 0은 정답과 실험용 계수를 분리한다. 조합이 없는 입력에서도 반환할 값이 정해진다. 두 변수를 섞으면 검사한 모든 쌍을 정답으로 세는 실수가 생길 수 있다.

바깥 반복문의 i는 첫 상품의 위치다. range(i + 1, len(prices))는 그 뒤의 위치만 선택한다. 따라서 같은 위치를 두 번 사용하지 않으며, 위치 쌍 (0, 1)과 (1, 0)을 중복 검사하지 않는다.

checks += 1은 조건을 만족하는지와 무관하게 실행된다. 이어지는 조건문은 두 가격의 합을 검사하고, 일치할 때만 pairs를 늘린다. N개 입력에서 checks는 N(N−1)/2가 된다.

count_pairs_linear의 seen은 지금까지 처리한 가격을 키로, 등장 횟수를 값으로 저장한다. 전체 입력을 미리 세지 않는 이유는 현재 위치보다 앞선 상품만 조합 대상으로 삼기 위해서다.

steps += 1은 원소 하나를 처리할 때마다 실행된다. needed = target - price는 현재 가격과 짝을 이룰 가격을 계산한다. seen.get(needed, 0)은 해당 가격이 없으면 0을 반환하므로 별도의 존재 검사 없이 조합 수에 더할 수 있다.

seen[price]를 갱신하는 줄은 조합 수를 더한 다음에 온다. 이 순서를 바꾸면 현재 상품이 사전에 먼저 들어가 자기 자신과 짝을 이룰 수 있다. 특히 목표 금액이 현재 가격의 두 배일 때 오류가 드러난다.

verify는 두 구현의 결과와 미리 계산한 기대값을 함께 검사한다. 오류가 나면 두 결과와 기대값을 담은 예외로 실행을 중단한다. 명시적인 조건문을 사용했으므로 최적화 실행 옵션에서도 검증을 생략하지 않는다.

cases의 각 항목에는 이름, 입력 목록, 목표 금액, 기대 조합 수를 저장한다. mixed에서는 첫 번째 1과 두 개의 7이 각각 짝을 이루고, 3과 5도 짝을 이루어 답이 3이다. negative에서는 −2와 6, 1과 3이 각각 목표 4를 만든다.

크기 증가 실험은 모든 가격을 4로 고정한다. 목표가 8이므로 서로 다른 위치 쌍이 모두 정답이다. 기대값을 조합 공식으로 계산해 두 함수와 비교한다. 마지막 실행 조건은 파일을 직접 실행할 때 main을 호출한다.

실행 결과

파일이 있는 디렉터리에서 다음 명령을 실행한다.

python3 main.py

예상 출력은 다음과 같다.

cases: name pairs pair_checks item_steps
empty: 0 0 0
single: 0 0 1
duplicates: 6 6 4
mixed: 3 10 5
zeros: 3 3 3
negative: 2 10 5
no_match: 0 3 3
all 7 cases: OK
growth: n pairs pair_checks item_steps
10: 45 45 10
100: 4950 4950 100
1000: 499500 499500 1000

N이 100에서 1000으로 열 배가 되면 위치 쌍 검사는 4,950회에서 499,500회로 약 백 배 늘어난다. 원소 처리 횟수는 100회에서 1,000회로 열 배 늘어난다. 유한한 입력에서는 −N 항의 영향이 있으므로 검사 횟수가 정확히 백 배가 되는 것은 아니다.

이 출력만으로 개선한 코드가 실제 시간에서 몇 배 빠르다고 말할 수는 없다. 사전 조회와 정수 덧셈의 비용이 같지 않고, 사전은 추가 메모리도 사용한다. 다만 입력이 커질 때 두 풀이의 작업량 증가 양상이 다르다는 점은 직접 확인할 수 있다. 면접에서는 이 관찰을 시간 복잡도 설명과 연결하면 된다.

실무에서 자주 틀리는 것

현재 가격부터 저장해 자기 자신을 세는 경우

다음은 함수 본문에 들어갈 수 있는 잘못된 조각이다. prices가 [4]이고 target이 8이면 조합이 없어야 하는데 1을 더한다.

seen[price] = seen.get(price, 0) + 1
pairs += seen.get(target - price, 0)

조회할 때 사전에 이전 원소만 있도록 순서를 고친다.

pairs += seen.get(target - price, 0)
seen[price] = seen.get(price, 0) + 1

이 수정은 예외 조건을 덧붙이는 대신, 자료구조가 유지해야 할 조건을 코드 순서로 표현한다.

빈도 대신 존재 여부만 저장하는 경우

다음 코드는 이전에 필요한 가격이 몇 번 나왔는지 잃는다. [1, 1, 7]의 목표 8에서 두 조합을 세지 못한다.

seen = set()
pairs = 0
for price in prices:
    if target - price in seen:
        pairs += 1
    seen.add(price)

조합 수를 구한다면 이전 가격의 빈도를 저장해야 한다.

seen = {}
pairs = 0
for price in prices:
    pairs += seen.get(target - price, 0)
    seen[price] = seen.get(price, 0) + 1

집합이 잘못된 자료구조라는 뜻은 아니다. 답이 존재하는지만 묻는 문제와 답의 개수를 묻는 문제에서 보존할 정보가 달라진다.

정렬하지 않고 투 포인터를 적용하는 경우

양 끝의 합이 작다는 이유로 왼쪽을 옮기는 다음 코드는 정렬되지 않은 입력에서 유효한 조합을 건너뛸 수 있다. 이 조각은 조합 개수가 아니라 존재 여부를 검사하는 예다.

ordered = prices
left, right = 0, len(ordered) - 1
while left < right:
    total = ordered[left] + ordered[right]
    if total == target:
        return True
    if total < target:
        left += 1
    else:
        right -= 1
return False

원본을 보존해야 한다면 정렬된 복사본을 만든다. 빈 목록에서도 반복문에 들어가지 않고 False를 반환한다.

ordered = sorted(prices)
left, right = 0, len(ordered) - 1
while left < right:
    total = ordered[left] + ordered[right]
    if total == target:
        return True
    if total < target:
        left += 1
    else:
        right -= 1
return False

이제 위치 이동의 근거는 생겼지만, 완성 코드와 같은 조합 수 계산은 아니다. 조합 수까지 구하려면 중복 가격을 별도로 처리해야 한다. 풀이를 바꿀 때 출력의 의미도 유지되는지 확인해야 한다.

두 결과가 같다는 것만 확인하는 경우

다음 검사는 두 구현이 같은 오류를 내면 통과한다. 예를 들어 둘 다 같은 가격을 하나로 취급했다면 서로 일치하면서도 요구사항에는 어긋날 수 있다.

if slow_pairs != fast_pairs:
    raise AssertionError("results differ")

손으로 계산한 기대값도 함께 확인한다.

if slow_pairs != fast_pairs or slow_pairs != expected:
    raise AssertionError("unexpected result")

기대값 자체도 틀릴 수 있으므로 작은 사례의 위치 쌍을 직접 적어 보는 과정이 필요하다. 테스트와 정확성 설명은 서로 보완한다.

한눈에 보기

면접 중 판단과 설명을 연결하는 기준
단계	해야 할 일	이번 문제의 예	주의점
이해	입력·출력·제약을 다시 말한다.	서로 다른 위치의 조합을 센다.	가격 종류와 상품 수를 구분한다.
출발	단순하고 검증 가능한 풀이를 제시한다.	모든 i < j 쌍을 확인한다.	같은 쌍을 두 번 세지 않는다.
개선	반복해서 찾는 정보를 저장한다.	이전 가격의 빈도를 조회한다.	조회 후 현재 가격을 저장한다.
기법 선택	적용 조건을 설명한다.	정렬 후에는 양 끝 이동을 검토한다.	기법 이름만으로 정당화하지 않는다.
검증	경계 사례와 기대값을 비교한다.	원소 하나, 중복, 0, 음수를 검사한다.	결과 일치가 증명을 대신하지 않는다.
복잡도	측정 단위와 전제를 밝힌다.	쌍 검사는 O(N²), 원소 처리는 N회다.	사전 풀이의 기대 시간과 추가 공간을 말한다.
막힘 대응	막힌 지점을 좁혀 다음 행동을 말한다.	작은 예시로 빈도 갱신 순서를 추적한다.	확인하지 않은 가정을 사실처럼 말하지 않는다.

좋은 답변은 결론, 근거, 확인 가능한 예시, 한계와 대안으로 이어진다. 이 구조는 긴 설명을 위한 틀이 아니라 판단을 짧고 분명하게 전달하는 도구다. 코드를 쓰는 동안에도 “지금은 정확한 기준 풀이를 만들고 있다”, “이 조회가 이전 탐색을 대신한다”처럼 현재 선택의 이유를 전달하면 된다.

연습 문제

가격이 [2, 2, 2, 6, 6]이고 목표 금액이 8일 때 조합 수를 손으로 구하라. 개선한 풀이에서 각 원소를 처리하기 직전 필요한 가격의 빈도를 순서대로 적어라.
현재 가격을 저장한 뒤 필요한 가격을 조회하도록 두 줄을 바꾸었다. 이 오류를 드러내는 가장 짧은 입력과 목표 금액을 만들고, 잘못된 출력과 올바른 출력을 설명하라.
순간 이동 지점으로 연결된 장소들에서 모든 이동 비용이 한 번으로 같다. 출발점에서 도착점까지 최소 이동 횟수를 구하려 한다. 어떤 탐색을 먼저 검토할지, 방문 처리를 언제 할지 설명하라. 이어 장소마다 이동 비용이 달라지면 무엇을 다시 검토해야 하는지 말하라.
길이가 N인 진열대에 한 칸 또는 두 칸짜리 덮개를 놓아 빈틈없이 덮는 방법 수를 구한다고 하자. N = 0인 경우도 한 가지 방법으로 정한다. 동적 계획법의 상태·시작값·전이를 정하고, N = 4의 답을 구하라.

정답과 해설

답은 6이다. 세 개의 2 각각이 두 개의 6과 짝을 이룬다. 앞의 세 원소는 필요한 가격 6이 아직 없으므로 조회값이 각각 0이다. 첫 번째 6을 처리할 때 이전 2의 빈도는 3이고, 두 번째 6을 처리할 때도 3이다. 따라서 더하는 값은 0, 0, 0, 3, 3이다. 가격 종류만 세면 이 여섯 조합을 보존할 수 없다.
입력 [4], 목표 8이면 충분하다. 먼저 4를 저장하면 사전의 4 빈도가 1이 되고, 필요한 가격 4를 조회해 잘못된 출력 1을 만든다. 올바른 출력은 0이다. 서로 다른 위치 두 개를 고를 수 없기 때문이다. 조회 후 저장하면 현재 위치를 조합 대상으로 넣지 않는다.
너비 우선 탐색을 먼저 검토한다. 시작점을 거리 0으로 두고 가까운 상태부터 탐색하면, 이동 비용이 같을 때 처음 발견한 거리가 최소 이동 횟수가 된다. 이 방식에서는 큐에 넣을 때 방문 표시를 하여 같은 장소가 중복으로 들어가는 것을 막는다. 비용이 서로 다르면 이동 횟수와 총비용이 일치하지 않는다. 비음수 비용이라면 다익스트라 알고리즘 같은 비용 기반 탐색을 검토하고, 음수 비용이 가능한지도 확인해야 한다.
dp[n]을 길이 n을 덮는 방법 수로 정의한다. 시작값은 dp[0] = 1, dp[1] = 1이다. 마지막 덮개가 한 칸이면 앞의 길이는 n−1이고, 두 칸이면 n−2다. 두 경우는 마지막 덮개의 길이가 달라 겹치지 않으므로 n이 2 이상일 때 dp[n] = dp[n−1] + dp[n−2]다. 값은 1, 1, 2, 3, 5로 이어져 N = 4의 답은 5다. 직전 두 값만 보관하면 전체 배열 없이도 계산할 수 있다.