반례를 못 찾겠다면, 만들어라

"맞왜틀"이라는 단어가 존재하는 건, 그만큼 많은 사람이 그 고통을 겪고 있다는 증거다. 제출 버튼 누르고 70%에서 딱 멈추는 그 순간 — 코드를 위에서 아래로 열 번째 읽고 있는 자신을 발견한다.

#"생각해보기"는 왜 한계가 있나

반례를 찾으라고 하면 대부분 이렇게 한다. "음... 빈 배열? 0? 음수?" 머릿속에서 케이스를 하나씩 떠올린다. 경험이 쌓이면 감이 좀 생기긴 하는데, 이 방식은 구조적인 결함이 있다. 내가 이미 인지하고 있는 함정만 체크할 수 있다는 것. 내가 모르는 엣지 케이스는 아무리 골똘히 생각해도 안 나온다. 그래서 접근 자체를 바꿔야 한다.

#스트레스 테스트 — 무식하지만 가장 확실하다

원리는 놀랍도록 단순하다.

1. 정답이 확실한 브루트포스 솔루션을 하나 짠다. 느려도 상관없다.

2. 내가 최적화한 솔루션을 준비한다.

3. 랜덤 입력을 수천 개 생성해서 두 결과를 비교한다.

4. 결과가 다른 입력 — 그게 반례다.

import random

def brute_force(arr):
    # O(n²)이든 O(n³)이든, 확실히 맞는 풀이
    n = len(arr)
    best = arr[0]
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += arr[j]
            best = max(best, s)
    return best

def my_solution(arr):
    # 내가 짠 O(n) 카데인 알고리즘
    max_sum = 0  # 의도적으로 버그 넣은 버전
    current = 0
    for x in arr:
        current = max(x, current + x)
        max_sum = max(max_sum, current)
    return max_sum

for _ in range(10000):
    n = random.randint(1, 15)
    arr = [random.randint(-10, 10) for _ in range(n)]
    if brute_force(arr) != my_solution(arr):
        print(f"반례 발견: {arr}")
        print(f"정답={brute_force(arr)}, 내 답={my_solution(arr)}")
        break
else:
    print("10000번 돌렸는데 차이 없음 — 아마 맞는 듯")

이게 왜 강력하냐. 내 상상력 바깥에 있는 케이스를 기계가 대신 뒤져준다. 카카오가 2025년부터 전체 테스트케이스 점수를 안 보여주기 시작했는데, "어디서 틀리는지 힌트 없음" 상태에서 스트레스 테스트는 사실상 필수 스킬이 됐다. 연습할 때 이 템플릿을 미리 만들어두면, 시험장에서는 함수 두 개만 갈아끼우면 된다.

#경계값 체크리스트

스트레스 테스트가 "넓게 훑기"라면, 경계값 분석은 "좁게 찌르기"다. 입력 범위를 보면 답이 나온다:

매번 새로 생각하지 말고 이걸 어딘가에 적어두자. 시험장에서 머리를 쓸 곳은 여기가 아니다.

#작은 입력 전수조사

N이 3~5 정도로 작을 때, 가능한 모든 경우를 넣어보는 것도 방법이다. 순열이면 itertools.permutations, 부분집합이면 비트마스킹으로 전부 돌린다. "이 순서일 때 터지는구나"가 눈에 바로 보여서 디버깅 속도가 완전히 달라진다.

#아까 그 카데인 버그, 정확히 뭐가 문제였나

위 코드를 실제로 돌려보면 [-3, -5, -1] 같은 입력에서 바로 잡힌다. 정답은 -1인데 내 코드는 0을 뱉는다.

원인은 max_sum = 0 초기화. 모든 원소가 음수면 current가 양수가 될 일이 없으니 max_sum이 초기값 0에서 안 움직인다. 수정은 간단하다:

def my_solution_fixed(arr):
    max_sum = float('-inf')  # 또는 arr[0]
    current = float('-inf')
    for x in arr:
        current = max(x, current + x)
        max_sum = max(max_sum, current)
    return max_sum

"전부 음수인 경우"를 머리로 떠올릴 수도 있다. 근데 솔직히, 그게 매번 되나? 스트레스 테스트는 1분이면 짜고, 10초면 결과가 나온다.

#"그거 짤 시간이 어딨어?"

이 반론 많이 듣는다. 근데 비교해보자.

"맞왜틀" 상태에서 코드를 한 줄 한 줄 눈으로 훑으며 30분 소비하는 것과, 스트레스 테스트 5분 짜서 반례 바로 찾는 것. 5시간짜리 카카오 코테에서 이 5분이 1~2솔 차이를 만든다. 특히 3번, 4번처럼 엣지 케이스가 교묘한 문제일수록 눈으로는 못 찾고 기계로는 바로 찾는다.

코드를 더 짜는 게 귀찮은 게 아니다. 더 안 짜고 버티는 게 진짜 시간 낭비다. 연습 때 한 번만 익혀두면 시험장에서는 몸이 알아서 움직인다.