애드혹 문제 케이스 분리를 어려워하는 이유는 보통 두 가지입니다. 나눠야 할 때 안 나누는 경우와, 안 나눠도 될 때 억지로 분기를 늘리는 경우입니다. 이번 글에서는 구간 안팎과 원형 거리 같은 쉬운 예시부터 시작해서, 경우를 나눠야 하는 순간과 반례 검증법을 intuition-first로 정리하겠습니다.
예시 1: 점이 구간 안에 있느냐 밖에 있느냐
수직선에 점 a, b, x가 있고 a <= b라고 하겠습니다. x에서 출발해서 구간 [a, b] 전체를 한 번은 지나야 할 때, 최소 이동 거리를 구하는 상황을 떠올려보면 케이스 분리의 감각이 잘 보입니다.
- x = 2, a = 5, b = 9면 오른쪽으로만 가면 되니 답은 7
- x = 12, a = 5, b = 9면 왼쪽으로만 가면 되니 답은 7
- x = 6, a = 5, b = 9면 이미 구간 안에 있으니 답은 4
여기서 핵심은 숫자 자체가 아니라 위치 관계입니다. x < a, a <= x <= b, x > b에 따라 답을 만드는 방식이 실제로 달라집니다. 이건 예외를 덧붙인 억지 분기가 아니라, 답의 구조가 바뀌는 경계를 따라 자연스럽게 나눈 경우입니다.
좋은 케이스 분리는 왜 식이 달라지는지가 먼저 설명됩니다.
예시 2: 원형에서는 직선 거리와 답이 달라진다
원형 배열이나 시계 문제에서는 abs(a – b)만 보면 자주 틀립니다. 길이가 12인 원에서 1과 11의 거리는 직선 차이로는 10이지만, 실제로는 반대 방향으로 2만 가면 됩니다.
이때도 결국은 두 경우가 숨어 있습니다. 직선으로 가는 편이 짧은 경우와, 반대 방향으로 도는 편이 짧은 경우입니다. 구현은 min(diff, n – diff) 한 줄로 정리할 수 있지만, 그 한 줄이 나오기 전에는 먼저 두 경우를 분리해서 봐야 합니다.
이런 흐름은 원형 배열 문제 풀이를 볼 때도 그대로 이어집니다. 겉보기에는 분기를 없앤 것처럼 보여도, 실제로는 필요한 케이스를 먼저 본 뒤 압축한 것입니다.
애드혹 문제 케이스 분리가 필요한 신호
1. 순서 관계가 바뀌는 순간
a < b < x인지, a < x < b인지에 따라 식이 달라지는 문제들이 있습니다. 이때는 숫자보다 누가 앞에 있고 누가 사이에 있는지가 더 중요합니다. 그래서 정렬 후 스캔이 통하는 순간 같은 유형에서 casework가 자주 등장합니다.
2. 경계값을 넘는 순간
길이 차이가 절반을 넘는가, 인덱스가 배열 끝을 넘는가, 어떤 값이 임계값 이상이 되는가처럼 경계값을 넘는 순간 규칙이 바뀌는 문제들이 많습니다. 이때 좋은 분기는 if x == 7 같은 숫자 암기가 아니라, 왜 그 경계가 의미 있는지를 설명할 수 있어야 합니다.
3. 상태가 바뀌는 순간
홀수와 짝수, 방문 전과 방문 후, 방향 전환 전과 후처럼 상태가 바뀌면 같은 식을 밀어붙이기 어려워집니다. 특히 애드혹 문제 parity 보는 법처럼 상태 변화 자체가 규칙의 핵심일 때는 상태 기반 분기가 자연스럽습니다.
4. 연산의 의미가 달라지는 순간
문제의 연산이 어느 구간에서는 같은 효과를 내지만, 다른 구간에서는 전혀 다른 효과를 낼 때가 있습니다. 문자열 뒤집기 문제에서 문자 개수보다 그룹 경계를 먼저 보는 이유도 비슷합니다. 연산이 문자 하나가 아니라 연속 구간에 작용하기 때문입니다. 이 감각은 문자열 뒤집기 최소 횟수 글과도 자연스럽게 이어집니다.
억지 분기와 좋은 분기의 차이
좋은 분기는 문제를 단순하게 만들고, 억지 분기는 코드를 늘립니다. 두 분기의 차이는 설명 가능성에서 가장 잘 드러납니다.
- 좋은 분기: 조건이 분명하고, 왜 식이 달라지는지 설명할 수 있고, 경계값 반례를 바로 만들 수 있다
- 억지 분기: 예제 몇 개 맞춘 뒤 뒤늦게 예외를 붙이고, 특정 숫자만 찍는 분기가 계속 늘어난다
- 좋은 분기: 구현 후 else가 찝찝하지 않다
- 억지 분기: 분기를 추가할수록 오히려 더 불안해진다
케이스 분리는 원래 복잡한 문제를 몇 개의 단순한 문제로 나누는 도구입니다. 그런데 억지 분기는 반대로 단순한 규칙 하나를 놓친 채, 복잡도를 계속 늘리는 방향으로 갑니다.
좋은 케이스를 만드는 가장 쉬운 방법
실전에서는 케이스 표를 먼저 그려보면 좋습니다. 예를 들어 구간 예시라면 x < a, a <= x <= b, x > b를 먼저 쓰고, 각 줄마다 “왜 답이 이렇게 계산되는가”와 “경계 바로 옆 입력은 무엇인가”를 적어봅니다.
이렇게만 해도 억지 분기가 많이 줄어듭니다. 분기를 만들기 전에 근거를 먼저 쓰게 되기 때문입니다.
반례는 경계 옆에서 만든다
케이스 분리가 맞는지 확인할 때는 큰 랜덤 입력보다 경계 옆 입력이 더 잘 듣습니다. 구간 예시라면 x = a – 1, x = a, x = a + 1, x = b – 1, x = b, x = b + 1처럼 바로 옆 값을 먼저 넣어봐야 합니다.
이렇게 보면 케이스가 빠짐없이 덮였는지, 경계에서 식이 갑자기 틀어지지 않는지를 한 번에 확인할 수 있습니다. 반례를 더 체계적으로 보는 흐름은 애드혹 문제 풀이법: 규칙 찾기와 반례 글과 함께 보면 더 잘 잡힙니다.
구현은 분기보다 식을 줄이는 방향으로 끝나야 한다
케이스 분리는 출발점이지, 항상 최종 형태는 아닙니다. 처음에는 경우를 나눠서 이해하고, 마지막에는 하나의 식이나 더 짧은 규칙으로 합칠 수 있는지 꼭 봐야 합니다. 원형 거리에서 min(diff, n – diff)가 나오는 과정이 딱 그렇습니다.
좋은 풀이의 최종 모습이 짧다고 해서, 처음 사고 과정까지 한 줄이었던 것은 아닙니다.
작은 예시를 코드로 옮기면 이렇게 된다
아래 코드는 구간 예시를 그대로 옮긴 것입니다. 핵심은 코드 자체보다, 분기 조건이 숫자 암기가 아니라 위치 관계를 반영하고 있다는 점입니다.
def cover_interval_distance(a, b, x):
if x < a:
return b - x
if x > b:
return x - a
return b - a
이 코드는 짧지만 예외를 생략해서 짧은 것이 아닙니다. 필요한 케이스만 남겼기 때문에 짧아진 것입니다. 반대로 아직도 if x == a – 1 같은 코드가 보인다면, 케이스 분리가 아니라 반례 봉합일 가능성이 큽니다.
Josephus처럼 작은 표가 먼저인 문제도 있다
모든 케이스 분리가 바로 식으로 보이는 것은 아닙니다. 어떤 문제는 작은 값을 적으면서 구조 변화를 먼저 관찰해야 합니다. Josephus 문제를 다룬 cp-algorithms의 Josephus problem 정리도 작은 표를 먼저 만든 뒤, 이전 답과 현재 답의 관계를 점화식으로 정리하는 흐름을 보여줍니다.
이 과정이 중요한 이유는 같습니다. 정답 공식을 외우기 전에 어디서 구조가 바뀌는지를 먼저 보게 해주기 때문입니다.
애드혹 문제 케이스 분리 체크리스트
- 답의 구조가 바뀌는 경계가 있는지 찾는다
- 순서 관계, 경계값, 상태 변화, 연산 의미 변화를 먼저 의심한다
- 각 케이스를 한 문장으로 설명해본다
- 경계 바로 옆 입력으로 반례를 만든다
- 구현 후에는 더 짧게 합칠 수 있는지 다시 본다
이 순서를 지키면 경우를 나누는 일이 훨씬 덜 불안해집니다. 분기가 늘어나도 왜 필요한지 설명할 수 있게 되기 때문입니다.
마무리
애드혹 문제에서 케이스를 나누는 순간은 보통 답의 구조가 바뀌는 순간입니다. 그래서 좋은 케이스 분리는 예외 처리의 흔적이 아니라, 문제를 제대로 읽었다는 흔적에 가깝습니다. 반대로 분기가 계속 늘어나는데도 설명이 안 된다면, 아직 좋은 경계를 찾지 못한 것일 수 있습니다.
그럴 때는 코드를 더 고치기 전에 작은 예시와 경계값으로 다시 돌아가는 편이 빠릅니다. 결국 casework의 핵심은 많이 나누는 것이 아니라, 왜 여기서 나뉘는지 아는 것입니다.
