문제 풀이 전략과 학습 계획 - 유형 판별에서 복습까지

이 장에서 배우는 것

알고리즘을 알고 있어도 처음 보는 문제 앞에서는 선택이 어렵다. 입력 크기는 큰데 어떤 조건을 이용해야 할지 보이지 않거나, 익숙한 풀이를 적용했다가 작은 반례에서 실패하기도 한다. 이때 필요한 것은 유형 이름을 더 외우는 일만이 아니다. 조건을 근거로 후보를 줄이고, 막힌 이유를 확인하며, 다음 시도에 쓸 기록을 남기는 과정이 필요하다.

앞 장에서 여러 상태를 나누고 점화식을 세우는 방법을 익혔다. 이 장에서는 이미 배운 도구를 언제 꺼낼지 정리한다. 두 개의 짧은 문제를 통해 풀이를 선택하는 순서를 살펴보고, 문제의 제약 정보를 받아 후보 알고리즘을 출력하는 프로그램을 만든다. 마지막에는 오답 기록을 재풀이 일정과 연결한다.

• 입력 크기와 구조적 조건을 함께 보고 알고리즘 후보를 고른다.
• 작은 예, 완전 탐색, 관찰, 최적화 순서로 막힌 풀이를 정리한다.
• 빠른 풀이를 느린 정답과 작은 입력에서 전수 대조한다.
• 오답 원인에 따라 재풀이 시점과 코딩 테스트 시간을 조정한다.

문제 상황

작은 물류팀에서 두 가지 업무를 자동화한다고 하자. 첫 번째는 포장할 물품 두 개의 무게 합이 지정한 값과 같은지 확인하는 일이다. 두 번째는 날짜별 입고량을 보고, 목표 수량을 채우는 가장 짧은 연속 기간을 찾는 일이다. 두 문제 모두 리스트를 입력받지만, 답을 만드는 방식은 다르다.

문제 A: 두 물품 묶음. 물품마다 정수 무게가 주어진다. 서로 다른 두 위치의 물품을 골라 합을 목표 무게와 같게 만들 수 있으면 참을 반환한다. 같은 무게의 물품이 여러 개 있을 수 있다. 연습용 반례를 만들 때는 음수도 허용하여 풀이가 특정 값의 범위에 기대고 있는지 확인한다. 실제 업무 데이터의 무게는 음수가 아니다.

문제 B: 입고 기간. 날짜별 입고량은 0 이상의 정수다. 합이 목표 수량 이상인 비어 있지 않은 연속 구간 중 가장 짧은 길이를 반환한다. 해당 구간이 없으면 0을 반환한다. 목표 수량은 양의 정수다. 날짜를 건너뛰어 고를 수 없다는 조건이 핵심이다.

팀은 비슷한 요청이 들어올 때마다 처음부터 고민하지 않도록 간단한 판별표도 만들고 싶다. 담당자가 목적, 최대 입력 크기, 음수 허용 여부를 적으면 검토할 풀이를 출력한다. 이 프로그램이 문제의 뜻을 이해하거나 정답 알고리즘을 보증하지는 않는다. 사람이 확인할 후보와 그 근거를 정리하는 도구다.

제약을 읽어 후보를 줄인다

제약은 최대 입력 개수만 뜻하지 않는다. 값의 범위, 정렬 여부, 음수 허용 여부, 같은 질문을 반복하는 횟수도 포함한다. 먼저 답의 형태를 한 문장으로 적는다. 이어서 그 답을 직접 구하는 가장 단순한 방법의 작업량을 계산한다. 마지막으로 작업량을 줄일 수 있는 조건을 찾는다.

입력 크기와 구조적 조건을 함께 읽는 후보 판별표

보이는 조건	검토할 후보	추가 확인	흔한 오해
입력이 작고 선택 조합을 검사한다	완전 탐색	조합 수와 후보당 검사 비용	입력 개수만 작으면 충분하다고 생각한다
정렬된 값에서 경계를 찾는다	이분 탐색	찾는 조건의 참·거짓이 한 번만 바뀌는가	정렬만 되어 있으면 모든 질문에 적용한다
이전에 본 값의 존재나 개수를 묻는다	해시	키와 중복의 의미	값이 같으면 같은 원소라고 본다
음수 없는 연속 구간의 합을 다룬다	슬라이딩 윈도	확장·축소할 때 조건 변화의 방향	음수가 있어도 같은 축소 규칙을 쓴다
간선 비용이 모두 같은 최소 이동 횟수다	너비 우선 탐색	상태와 간선의 정의	비용이 다른 경우도 그대로 처리한다
음수 없는 간선 비용의 최소 합이다	다익스트라	정점·간선 수와 자료구조	음수 간선 조건을 확인하지 않는다
겹치는 부분 문제와 선택의 누적이 보인다	동적 계획법	상태 수, 전이 수, 계산 순서	점화식만 맞으면 자원도 충분하다고 본다

이 표는 출발점이다. 예를 들어 입력이 크다는 사실만으로 해시를 선택할 수는 없다. 이전에 본 값의 존재를 다시 묻는 구조가 있어야 한다. 동적 계획법도 입력이 작다는 이유만으로 적합해지지 않는다. 어떤 정보를 상태로 남겨야 이후의 선택을 계산할 수 있는지 먼저 설명해야 한다.

작업량 기준도 실행 시간의 보증으로 읽으면 안 된다. 이번 프로그램은 완전 탐색 후보를 표시할 때 비교 횟수 2,000,000회를 임의의 검토 기준으로 사용한다. 이는 연습용 정책이다. 같은 횟수라도 정수 비교와 긴 문자열 처리의 비용은 다르며, 실행 환경과 구현에 따라서도 시간이 달라진다. 실제 문제에서는 제한 시간과 연산 내용을 함께 판단한다.

두 예제의 직접적인 풀이는 모두 두 겹의 반복으로 시작할 수 있다. 두 물품 묶음은 서로 다른 위치의 쌍을 검사하고, 입고 기간은 시작점과 끝점을 정해 구간을 검사한다. 다만 구간 합을 매번 처음부터 더하면 반복이 하나 더 생긴다. 느린 정답도 현재 합을 누적하면 두 겹의 반복으로 작성할 수 있다.

두 예제에서 제약이 후보 선택에 미치는 영향

문제	직접 검사 수	이용할 관찰	빠른 후보
두 물품 묶음	n(n−1)/2개 쌍	현재 값의 짝이 이전에 있었는가	해시 집합
입고 기간	n(n+1)/2개 구간	음수가 없어 확장하면 합이 줄지 않는다	슬라이딩 윈도

막히면 작은 예에서 다시 출발한다

막혔을 때는 작은 예 → 완전 탐색 → 관찰 → 최적화 순서로 돌아간다. 작은 예를 만든다는 것은 임의의 숫자를 줄여 적는 데서 끝나지 않는다. 빈 입력, 원소 하나, 같은 값의 반복, 답이 없는 경우처럼 판단을 갈라놓는 예를 고른다. 완전 탐색은 그 예에서 무엇을 빠짐없이 검사해야 하는지 드러내는 역할을 한다.

두 물품 묶음에서 무게가 [4, 1, 6, 3]이고 목표가 7이라고 하자. 모든 쌍을 확인하는 대신 현재 무게가 6이면 필요한 짝은 1이라고 바꾸어 생각할 수 있다. 필요한 짝이 이전에 등장했는지만 확인하면 된다.

목표 합 7인 두 물품 묶음을 손으로 따라가기

현재 값	필요한 짝	검사 직전의 집합	판단
4	3	비어 있음	없으므로 4를 저장한다
1	6	{4}	없으므로 1을 저장한다
6	1	{1, 4}	짝이 있으므로 참이다

정확성 근거는 반복문이 유지하는 불변식으로 적는다. 현재 원소를 검사하기 직전의 집합에는 이전 위치에서 읽은 값만 들어 있다. 따라서 집합에서 짝을 찾으면 서로 다른 두 위치를 골랐다는 조건을 만족한다. 반대로 정답 쌍이 존재한다면 그중 뒤쪽 원소를 읽을 때 앞쪽 값이 집합에 있으므로 발견한다. 현재 값을 집합에 넣는 시점은 검사 이후여야 한다.

입고 기간은 [2, 0, 3, 1, 2], 목표 수량 5로 살펴본다. 오른쪽 끝을 한 칸씩 늘려 합이 목표 이상이 되면 왼쪽 끝을 줄여 본다. 목표를 만족하는 동안에는 길이를 기록하고 계속 줄인다. 한 번만 줄이는 것으로 끝내면 같은 오른쪽 끝에서 더 짧은 답을 놓칠 수 있다.

목표 수량 5인 입고 기간을 손으로 따라가기

오른쪽 위치	확장 직후 구간	축소 중 검사	현재 최단 길이
0	[2]	합 2이므로 기다린다	없음
1	[2, 0]	합 2이므로 기다린다	없음
2	[2, 0, 3]	길이 3을 기록하고 2를 뺀다	3
3	[0, 3, 1]	합 4이므로 기다린다	3
4	[0, 3, 1, 2]	길이 4, 3을 검사한 뒤 합이 3이 된다	3

이 풀이가 왼쪽 끝을 되돌리지 않아도 되는 이유는 음수가 없기 때문이다. 목표를 만족해서 버린 왼쪽 위치는 이미 그때의 길이로 검사했다. 이후 오른쪽 끝이 더 멀어져도 같은 왼쪽 위치의 구간 길이는 더 길어질 뿐이므로 새 최단 답이 되지 않는다. 각 오른쪽 끝에서는 합이 목표 미만이 될 때까지 축소하므로, 아직 남아 있는 유효한 시작점을 건너뛰지도 않는다.

음수를 허용하면 축소를 멈추는 근거가 사라진다. 예를 들어 [1, -1, 5]에서 목표가 5라면, 전체 합 5에서 첫 값을 빼는 순간 합은 4가 된다. 여기서 멈추면 뒤의 [5]를 발견하지 못한다. 조건 하나가 달라졌을 때 같은 코드를 계속 쓰지 않아야 하는 이유다.

두 물품의 느린 풀이는 시간 O(n²), 추가 공간 O(1)이다. 해시 집합을 쓰는 풀이는 집합 연산이 평균적으로 일정한 비용이라는 가정에서 평균 시간 O(n), 추가 공간 O(n)이다. 입고 기간의 느린 풀이는 시간 O(n²), 추가 공간 O(1)이다. 빠른 풀이는 각 원소가 한 번 들어오고 한 번 빠지므로 시간 O(n), 추가 공간 O(1)이다. 여기서 추가 공간은 이미 주어진 입력 리스트를 제외한다.

검증과 복습을 하나의 과정으로 묶는다

빠른 풀이를 작성한 뒤 예제 두세 개가 맞았다는 이유로 마무리하지 않는다. 짧고 직접적인 느린 정답을 남겨 두고 작은 입력 전체에서 비교한다. 두 풀이가 다르면 어느 쪽이 맞는지 작은 반례를 손으로 확인한다. 느린 정답도 실수할 수 있으므로, 문제 정의와 바로 대응하도록 단순하게 작성한다.

이번 전수 대조에서는 길이 0부터 5까지를 사용한다. 두 물품 묶음은 값이 -1, 0, 1인 모든 수열과 목표 -2부터 2까지를 검사한다. 입고 기간은 값이 0, 1, 2인 모든 수열과 목표 1부터 5까지를 검사한다. 각 문제의 비교 횟수는 (1+3+9+27+81+243)×5=1,820회다. 난수를 사용하지 않으므로 실행할 때마다 같은 입력을 검사한다.

작은 범위의 전수 대조는 구현 실수를 찾는 도구이며, 모든 크기의 정확성을 대신 증명하지는 않는다. 큰 입력에서의 정당성은 앞에서 정리한 불변식과 이동 규칙으로 설명한다. 반대로 논리 설명이 맞아도 코드의 갱신 순서나 반환값은 틀릴 수 있으므로 실제 비교가 필요하다.

오답 노트에는 문제 풀이 전체를 베껴 쓰기보다 다음에 행동을 바꿀 정보를 남긴다. ‘해시 문제였다’보다 ‘현재 값을 먼저 넣어 같은 위치를 두 번 사용했다’가 유용하다. 아래처럼 실패 원인과 재현 입력을 함께 적는다.

다음 시도에서 확인할 행동이 드러나는 오답 기록

기록 항목	기록 예	다음 행동	재풀이 통과 기준
놓친 조건	서로 다른 두 위치를 골라야 한다	집합에 넣는 순서를 점검한다	[3], 목표 6을 거짓으로 처리한다
잘못된 관찰	음수가 있어도 구간 축소가 된다고 봤다	합의 변화 방향을 먼저 적는다	적용 조건을 말로 설명한다
구현 실수	축소를 한 번만 수행했다	반복 종료 조건을 확인한다	전수 대조를 통과한다
진행 판단	한 문제에서 근거 없는 수정만 반복했다	현재 가설과 반례를 적고 전환한다	제한 시간 안에 다음 문제로 이동한다

재풀이 일정은 개인의 기억 상태에 맞추어 조정한다. 시작안으로는 풀이를 정리한 다음 날, 3일 뒤, 7일 뒤를 잡을 수 있다. 이는 기억을 보장하는 공식이 아니라 일정을 빠뜨리지 않기 위한 예시다. 코드를 보지 않고 조건, 관찰, 복잡도를 설명한 뒤 다시 구현한다. 실패하면 원인을 덧붙이고 가까운 날짜에 다시 배치한다.

시간 배분도 고정 규칙보다 전환 기준이 중요하다. 연습용으로 전체 시간이 90분이라면 처음 10분은 모든 문제를 읽고, 다음 60분은 풀 수 있는 문제를 구현하며, 마지막 20분은 경계 입력과 제출 상태를 확인하는 계획을 세울 수 있다. 문제마다 배점이나 부분 점수가 다르면 그 조건도 반영한다.

한 문제에서 약 10분 동안 새로운 관찰도 반례도 얻지 못했다면 현재 상태를 짧게 적고 다른 문제로 이동하는 연습을 한다. ‘풀이 후보는 있으나 증명하지 못함’과 ‘구현만 남음’은 다른 상태다. 전환 전에는 남은 작업을 구체적으로 적어야 돌아왔을 때 같은 생각을 반복하지 않는다. 종료 직전에는 검증되지 않은 큰 변경보다 이미 작성한 코드의 입력 처리, 경계 조건, 출력 형식을 확인한다.

완성 코드

다음 코드를 main.py로 저장한다. 예시 제약 데이터는 이름, 목적, 최대 입력 크기, 음수 없음 표시의 순서다. 목적은 pair 또는 segment이며, 마지막 값 1은 음수가 없다는 뜻이다. 문자열을 파일처럼 읽어 코딩 테스트식 입력 처리를 흉내 낸다.

판별 함수는 두 목적만 지원한다. 입고 기간은 목표가 양수이고 비어 있지 않은 연속 구간을 구한다는 문제 정의가 이미 확인되었다고 가정한다. 후보 출력에 이어 두 예제의 빠른 풀이를 작은 입력에서 전수 대조한다.

import io
from itertools import product

PAIR_BUDGET = 2_000_000

EXAMPLE_INPUT = """2
묶음검사 pair 12 1
입고기간 segment 200000 1
"""


def read_cases(text):
    stream = io.StringIO(text)
    count = int(stream.readline())
    cases = []
    for _ in range(count):
        name, goal, n_text, flag_text = stream.readline().split()
        n = int(n_text)
        flag = int(flag_text)
        if n < 0 or flag not in (0, 1):
            raise ValueError("제약 데이터가 올바르지 않다")
        if goal not in ("pair", "segment"):
            raise ValueError("지원하지 않는 목적이다")
        cases.append((name, goal, n, flag == 1))
    return cases


def recommend(goal, n, nonnegative):
    candidates = []
    if goal == "pair":
        checks = n * (n - 1) // 2
        if checks <= PAIR_BUDGET:
            candidates.append("완전 탐색")
        candidates.append("해시 집합")
        reason = f"쌍 {checks}개; 서로 다른 위치 확인"
    elif goal == "segment":
        checks = n * (n + 1) // 2
        if checks <= PAIR_BUDGET:
            candidates.append("완전 탐색")
        if nonnegative:
            candidates.append("슬라이딩 윈도")
        else:
            candidates.append("추가 분석 필요")
        condition = "음수 없음" if nonnegative else "음수 허용"
        reason = f"구간 {checks}개; {condition}"
    else:
        raise ValueError("지원하지 않는 목적이다")
    return ", ".join(candidates), reason


def pair_slow(values, target):
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] + values[j] == target:
                return True
    return False


def pair_fast(values, target):
    seen = set()
    for value in values:
        if target - value in seen:
            return True
        seen.add(value)
    return False


def segment_slow(values, target):
    best = len(values) + 1
    for left in range(len(values)):
        total = 0
        for right in range(left, len(values)):
            total += values[right]
            if total >= target:
                best = min(best, right - left + 1)
    return 0 if best == len(values) + 1 else best


def segment_fast(values, target):
    left = 0
    total = 0
    best = len(values) + 1
    for right, value in enumerate(values):
        total += value
        while total >= target:
            best = min(best, right - left + 1)
            total -= values[left]
            left += 1
    return 0 if best == len(values) + 1 else best


def verify():
    pair_count = 0
    segment_count = 0
    for size in range(6):
        for values in product((-1, 0, 1), repeat=size):
            for target in range(-2, 3):
                expected = pair_slow(values, target)
                actual = pair_fast(values, target)
                if actual != expected:
                    raise AssertionError(
                        ("pair", values, target, expected, actual)
                    )
                pair_count += 1
        for values in product((0, 1, 2), repeat=size):
            for target in range(1, 6):
                expected = segment_slow(values, target)
                actual = segment_fast(values, target)
                if actual != expected:
                    raise AssertionError(
                        ("segment", values, target, expected, actual)
                    )
                segment_count += 1
    return pair_count, segment_count


def main():
    cases = read_cases(EXAMPLE_INPUT)
    print("문제 | 최대 n | 후보 | 근거")
    for name, goal, n, nonnegative in cases:
        candidates, reason = recommend(goal, n, nonnegative)
        print(f"{name} | {n} | {candidates} | {reason}")

    print("예제 A:", pair_fast([4, 1, 6, 3], 7))
    print("예제 B:", segment_fast([2, 0, 3, 1, 2], 5))
    pair_count, segment_count = verify()
    print(f"두 물품 전수 대조: {pair_count}회 통과")
    print(f"입고 기간 전수 대조: {segment_count}회 통과")


if __name__ == "__main__":
    main()

줄별 해설

import io는 문자열을 입력 스트림처럼 읽기 위해 사용한다. product는 지정한 값으로 만들 수 있는 모든 수열을 생성한다. 외부 패키지가 필요하지 않으며, 입력을 기다리는 input() 호출도 없다.

PAIR_BUDGET은 후보를 표시하는 정책값이다. 이름에 쌍이 들어 있지만 구간 개수 판단에도 같은 기준을 사용한다. EXAMPLE_INPUT의 첫 줄은 데이터 행 수다. 이어지는 두 줄은 실제 리스트가 아니라 문제의 최대 제약을 나타낸다. 판별표를 만들기 위해 물품 12개나 날짜 200,000개의 실제 값을 생성하지는 않는다.

read_cases()는 각 행의 네 항목을 분리한다. 입력 크기를 정수로 바꾸고 음수 크기나 잘못된 표시값을 거부한다. 목적도 허용된 두 값인지 확인한다. flag == 1은 숫자 표시를 참·거짓 값으로 바꾸므로 이후 함수에서는 의미가 더 분명해진다.

recommend()의 첫 분기는 서로 다른 두 위치의 쌍 수를 계산한다. // 2는 정수 나눗셈이며 쌍 수 계산에 소수가 필요하지 않음을 드러낸다. 검사 수가 기준 이하면 완전 탐색을 후보에 넣고, 해시 집합도 함께 넣는다. 작은 입력에서 빠른 풀이만 남겨야 할 이유는 없다. 단순한 풀이가 검증과 구현 면에서 편할 수 있다.

두 번째 분기의 구간 개수는 n * (n + 1) // 2다. 이는 길이가 1 이상인 모든 연속 구간의 수다. 음수가 없을 때만 슬라이딩 윈도를 추가한다. 음수를 허용하면 ‘추가 분석 필요’를 남긴다. 이 문구는 알고리즘 이름이 아니라, 현재 정보로는 같은 최적화의 정확성을 설명할 수 없다는 판단이다.

pair_slow()는 두 번째 위치를 i + 1부터 검사한다. 같은 위치를 쓰지 않고 각 쌍을 한 번씩 확인한다. pair_fast()는 필요한 짝을 먼저 찾고 현재 값을 나중에 저장한다. 집합은 중복 개수를 보관하지 않지만 이 문제에서는 이전 위치에 짝이 하나라도 있었는지만 알면 충분하다.

segment_slow()는 시작점을 고정할 때마다 합을 0으로 되돌린다. 끝점을 늘리는 동안 합을 누적하므로 각 구간을 일정한 추가 비용으로 검사한다. best의 초기값인 입력 길이보다 1 큰 수는 실제 구간 길이가 될 수 없는 표시값이다. 끝까지 바뀌지 않으면 정답이 없다는 뜻으로 0을 반환한다.

segment_fast()는 오른쪽 끝을 늘린 뒤 조건을 만족하는 동안 왼쪽 끝을 이동한다. 길이를 기록한 다음 왼쪽 값을 빼는 순서다. 이 함수의 계약은 값이 모두 0 이상이고 목표가 양수라는 것이다. 입력 검증까지 넣는다면 함수 시작에 이를 확인할 수 있지만, 여기서는 제약이 보장되는 풀이 함수로 작성했다.

verify()는 생성된 수열을 저장하지 않고 하나씩 비교한다. 길이 0에서는 빈 튜플 하나가 만들어지므로 빈 입력도 검사한다. 결과가 다르면 문제 종류, 입력, 목표, 기대값, 실제값을 함께 예외에 담는다. main()은 판별표, 예제 답, 전수 대조 결과를 정해진 순서로 출력한다.

판별 함수 자체는 문제 하나당 일정한 수의 계산을 한다. 일반적인 코딩 테스트 크기에서 이를 O(1)로 볼 수 있다. 매우 큰 정수까지 엄밀히 다루면 정수 자릿수에 따른 계산 비용도 고려해야 한다. 문제 수를 m이라 하면 입력 목록을 보관하는 공간은 O(m)이다. 후보를 계산하는 일과 추천된 알고리즘을 실행하는 일의 비용을 혼동하지 않아야 한다.

전수 대조는 운영 데이터 처리를 위한 절차가 아니다. 최대 길이를 k, 값 종류를 a개로 늘리면 수열 수가 1+a+…+aᵏ으로 증가한다. 여기에 목표 개수와 느린 풀이의 비용이 곱해진다. 따라서 작은 범위에서 실행하고, 큰 입력의 성능은 복잡도 분석과 별도 실행으로 확인한다.

실행 결과

macOS 또는 Linux에서 Python 3.12 이상으로 다음 명령을 실행한다. 문법 컴파일 명령은 성공하면 별도 내용을 출력하지 않는다. 프로그램은 예시 데이터를 처리한 뒤 종료한다.

python3 -W error -m py_compile main.py
python3 main.py

프로그램의 예상 출력은 다음과 같다.

문제 | 최대 n | 후보 | 근거
묶음검사 | 12 | 완전 탐색, 해시 집합 | 쌍 66개; 서로 다른 위치 확인
입고기간 | 200000 | 슬라이딩 윈도 | 구간 20000100000개; 음수 없음
예제 A: True
예제 B: 3
두 물품 전수 대조: 1820회 통과
입고 기간 전수 대조: 1820회 통과

실무에서 자주 틀리는 것

입력 크기만 보고 알고리즘을 정한다

큰 입력이라는 사실은 느린 후보를 제외할 근거가 되지만, 특정 풀이의 정확성을 보장하지는 않는다. 다음 코드는 음수 허용 여부를 확인하지 않는다. 두 조각은 판별 함수 안의 후보 선택 부분이다.

if n > 1000:
    candidates.append("슬라이딩 윈도")

문제의 목적과 합의 변화 조건을 함께 검사한다. 실제 추천 함수에서는 완전 탐색의 검사 수도 따로 판단한다.

if goal == "segment" and nonnegative:
    candidates.append("슬라이딩 윈도")
elif goal == "segment":
    candidates.append("추가 분석 필요")

현재 값을 먼저 넣어 같은 위치를 다시 쓴다

다음 순서에서는 [3], 목표 6을 참으로 판단한다. 값이 두 번 필요한 것과 물품이 두 개 존재하는 것은 다르다.

seen.add(value)
if target - value in seen:
    return True

이전에 읽은 위치만 집합에 들어 있도록 검사와 저장의 순서를 바꾼다.

if target - value in seen:
    return True
seen.add(value)

구간을 한 번만 줄인다

다음 코드는 오른쪽 끝 하나에 대해 시작점을 한 번만 옮긴다. [1, 1, 5], 목표 5에서는 길이 3을 기록한 뒤 더 짧은 길이를 확인하지 못한다.

if total >= target:
    best = min(best, right - left + 1)
    total -= values[left]
    left += 1

합이 목표 이상인 동안 계속 줄여야 한다. 목표가 양수이고 값이 음수가 없다는 계약도 함께 유지한다.

while total >= target:
    best = min(best, right - left + 1)
    total -= values[left]
    left += 1

복습 기록에 정답 코드만 남긴다

정답 코드만 저장하면 어떤 판단을 고쳐야 했는지 다시 추측하게 된다. 다음 기록은 재풀이 날짜는 있지만 통과 기준이 없다.

note = {
    "topic": "해시",
    "status": "정답 코드 저장",
}

실패 원인과 반례를 넣고, 날짜를 미루는 조건도 정한다. 날짜는 풀이를 정리한 날로부터의 간격이다.

note = {
    "cause": "검사 전에 값을 넣어 같은 위치를 재사용했다",
    "counterexample": ([3], 6, False),
    "review_after_days": [1, 3, 7],
    "pass_rule": "코드 없이 설명하고 전수 대조 통과",
}

한눈에 보기

풀이 선택부터 재풀이까지 이어지는 판단 기준

단계	확인할 질문	남길 결과	다음 단계 조건
문제 읽기	무엇을 고르고 무엇을 출력하는가	입력·출력·제약의 짧은 설명	작은 예의 답을 손으로 구한다
완전 탐색	무엇을 모두 검사하면 되는가	느린 정답과 작업량	빠짐없이 검사함을 설명한다
관찰	어떤 조건으로 중복 작업을 줄이는가	불변식과 적용 조건	조건을 깨는 반례도 확인한다
최적화	시간과 공간이 제약에 맞는가	빠른 풀이와 복잡도	작은 입력 대조를 통과한다
시간 관리	새로운 근거 없이 수정만 반복하는가	현재 가설과 남은 작업	계속할지 전환할지 결정한다
복습	같은 실패를 스스로 설명할 수 있는가	원인·반례·재풀이 일정	도움 없이 다시 구현한다

유형 판별의 목표는 문제에 이름표를 빨리 붙이는 데 있지 않다. 선택한 풀이가 왜 적용되는지 설명하고, 구현 결과를 확인하는 데 있다. 판별표에 후보가 여러 개 남아 있어도 괜찮다. 제약을 만족하는 후보 중 증명과 구현이 명료한 것을 선택하면 된다.

연습 문제

1. 예시 데이터에 조정기간 segment 8 0을 추가하고 첫 줄의 행 수를 수정한다. 이 행의 후보와 근거가 어떻게 출력되는지 구한다. 음수를 허용할 때 슬라이딩 윈도를 자동 추천하지 않는 이유도 적는다.
2. 두 물품 묶음에서 [3], 목표 6과 [3, 3], 목표 6의 답을 각각 구한다. 집합이 중복 개수를 저장하지 않는데도 두 입력을 올바르게 구별하는 이유를 설명한다.
3. 입고 기간 전수 대조의 값 종류를 0, 1 두 개로 줄이고, 길이를 0부터 6까지, 목표를 1부터 4까지 검사하도록 바꾼다. 비교 횟수를 계산하고, 이 검사가 모든 입력에 대한 정확성 증명이 될 수 있는지 설명한다.
4. 90분 연습에서 처음 10분 동안 전체 문제를 읽었다. 이후 한 문제에 25분을 썼지만 최근 10분 동안 새 관찰을 얻지 못했다. 마지막 20분의 검증 시간을 유지하려면 남은 풀이 시간은 얼마인가. 다른 문제로 옮기기 전에 남길 기록 두 가지와 다음 날 재풀이의 통과 기준을 적는다.

정답과 해설

1. 첫 줄을 3으로 바꾼다. 입력 크기 8의 비어 있지 않은 구간 수는 8×9÷2=36이다. 기준 이하이므로 완전 탐색이 포함되고, 음수가 허용되므로 추가 분석이 필요하다는 표시가 붙는다.

   조정기간 | 8 | 완전 탐색, 추가 분석 필요 | 구간 36개; 음수 허용
   

   음수가 있으면 왼쪽 값을 제거했을 때 합이 증가할 수도 있다. 합이 목표 미만이 되었다는 이유만으로 더 줄일 가능성을 버릴 수 없으므로 같은 축소 규칙을 적용하지 않는다.

2. [3]의 답은 거짓이고 [3, 3]의 답은 참이다. 첫 번째 3을 검사할 때 집합은 비어 있으므로 자신과 짝을 만들지 않는다. 두 번째 3이 있으면 그 위치를 검사할 때 집합에 이전 위치의 3이 들어 있다. 필요한 것은 이전 위치에 해당 값이 존재한다는 사실이므로 이 문제에서는 개수를 저장하지 않아도 된다.

3. 수열 수는 1+2+4+8+16+32+64=127개다. 목표가 네 가지이므로 비교 횟수는 508회다. 코드에서는 range(7), product((0, 1), repeat=size), range(1, 5)를 사용한다. 정해진 작은 범위에서는 모든 경우를 검사하지만 길이가 7 이상이거나 다른 값이 있는 입력은 검사하지 않는다. 일반적인 정확성 근거는 별도로 필요하다.

4. 현재 35분이 지났으므로 전체 남은 시간은 55분이다. 마지막 검증 20분을 남기면 구현과 풀이에 쓸 시간은 35분이다. 이동 전에는 현재 후보와 아직 설명하지 못한 조건을 적고, 작성한 코드의 통과 입력 또는 실패 반례를 남긴다. 다음 날에는 풀이를 보지 않고 적용 조건과 복잡도를 설명한 뒤 구현하여 작은 입력 대조를 통과하는 것을 기준으로 삼는다.