애드혹 알고리즘 반례 찾는 법은 맞왜틀을 줄이는 데 아주 중요합니다. 이번 글에서는 내가 세운 규칙이 어디서 깨지는지, 그리고 반례를 어떤 순서로 찾아야 하는지 실제 예시 중심으로 정리해보겠습니다.
반례는 무엇을 깨뜨리는 입력일까
반례는 한 문장으로 말하면 내가 믿고 있는 규칙이 틀렸다는 것을 보여주는 입력입니다. 즉, 반례는 희귀한 예외가 아니라 내가 세운 규칙이 버티지 못하는 지점입니다.
왜 애드혹 문제는 반례에서 자주 무너질까
애드혹 문제는 조건을 보고 스스로 규칙을 세우는 경우가 많습니다. 그래서 애드혹 문제에서는 정답을 찾는 것만큼 내가 세운 규칙을 의심하는 과정이 중요합니다.
반례를 찾을 때 가장 먼저 봐야 하는 패턴
- 가장 작은 입력
- 경계값
- 같은 값이 반복될 때
- 순서를 뒤집었을 때
- 예외가 하나만 끼어 있을 때
반례를 찾는 첫걸음은 특이한 입력을 무작정 만들기보다 규칙이 흔들릴 만한 패턴부터 보는 것입니다.
예시 1: 항상 가장 큰 수부터 고르면 된다는 규칙은 왜 깨질까
예를 들어 수열에서 서로 인접하지 않은 원소만 골라 합을 최대로 만들고 싶다고 해봅시다. 이 문제를 처음 보면 많은 사람이 가장 큰 수부터 고르면 되는 거 아닌가라고 생각합니다. 큰 수가 중요해 보이기 때문입니다.
하지만 입력이 [4, 5, 4]라면 이 규칙은 바로 깨집니다. 가장 큰 값 5를 먼저 고르면 양옆 4를 함께 고를 수 없어 합이 5가 됩니다. 반면 첫 번째 4와 마지막 4를 고르면 합이 8입니다. 즉, 항상 가장 큰 수부터라는 규칙은 이 작은 입력 하나에서 무너집니다.
이 예시는 반례가 거창할 필요가 없다는 것을 보여줍니다. 중요한 것은 규칙을 한 문장으로 쓰고, 그 규칙이 가장 흔들릴 작은 입력을 직접 만들어보는 것입니다.
예시 2: 앞에서부터 처리하면 된다는 가정은 왜 경계에서 깨질까
문자열 문제나 배열 문제에서는 그냥 앞에서부터 차례대로 처리하면 되겠지라는 생각이 자주 듭니다. 하지만 이 규칙은 마지막 구간이나 길이가 아주 짧은 입력에서 자주 흔들립니다.
문자열 0001110을 보겠습니다. 이 문자열은 000, 111, 0처럼 3개의 구간으로 나뉩니다. 그런데 값이 바뀌는 순간만 세면 충분하다고 생각하면 마지막 0 구간을 어떻게 해석해야 하는지에서 실수가 생기기 쉽습니다.
이걸 더 작은 입력으로 줄여보면 0, 01, 001, 0001110 같은 입력이 나옵니다. 이런 입력은 길이 1, 마지막만 다른 경우, 구간 수가 늘어나는 경우를 보여주기 때문에 경계값 반례를 찾는 데 아주 좋습니다.
즉, 앞에서부터 처리하면 된다는 규칙은 맞을 수도 있지만, 마지막 구간을 어떻게 처리하는지까지 포함해서 맞아야 합니다.
예시 3: 코드가 틀린 게 아니라 count의 의미 해석이 틀릴 수 있다
구현형 문제에서는 코드가 얼핏 맞아 보이는데 사실은 그 코드가 세는 값을 내가 잘못 해석하는 경우도 많습니다. 예를 들어 이런 코드를 생각해봅시다.
var count = 0
for (i in 0 until arr.size - 1) {
if (arr[i] != arr[i + 1]) {
count++
}
}이 코드가 세는 것은 정확히 말하면 인접한 두 값이 바뀌는 횟수입니다. 그런데 문제에서 내가 원하는 것이 구간 개수인지, 연산 횟수인지, 뒤집어야 하는 그룹 수인지에 따라 해석은 달라집니다.
예를 들어 [1]에서는 변화 횟수가 0이지만 구간 개수는 1일 수 있습니다. [1, 1, 1]도 마찬가지입니다. 또 [1, 2, 1]에서는 변화 횟수는 2지만 구간 개수는 3입니다. 즉, 이 코드는 맞게 실행되지만 내가 원하는 값을 직접 세고 있는지는 별개입니다.
구현형 문제에서는 코드가 돌아간다는 사실보다 그 코드가 무엇을 세고 있는지 한국어로 설명할 수 있어야 합니다. 설명이 막히면 반례가 있을 가능성이 큽니다.
코드로 반례를 점검하는 습관
val tests = listOf(
listOf(1),
listOf(1, 1, 1),
listOf(1, 2, 1),
listOf(2, 1, 2, 1)
)
for (test in tests) {
println("$test -> ${solve(test)}")
}이 코드의 핵심은 자동화 자체가 아닙니다. 중요한 것은 반례 후보를 의식적으로 모아놓고 확인하는 습관입니다.
이 다이어그램은 반례를 찾을 때 어떤 질문 순서로 들어가면 좋은지 정리한 것입니다. 규칙을 하나 세웠다면 바로 믿지 말고, 작은 입력과 패턴을 이용해 흔들어보는 습관이 중요합니다.
반례를 찾는 실전 질문
- 가장 작은 입력에서도 맞을까
- 같은 값만 나오면 어떻게 될까
- 순서를 뒤집으면 여전히 맞을까
- 맨 앞/맨 뒤에서만 달라지면 어떨까
- 내가 세운 규칙이 왜 항상 맞는지 설명할 수 있을까
이 질문들을 반복하다 보면 반례 찾기는 감이 아니라 습관이 됩니다.
이번 글에서 꼭 기억하면 좋은 한 문장
반례는 특별한 입력이 아니라, 내가 세운 규칙이 버티지 못하는 입력이다. 이 관점이 잡히면 반례 찾기가 훨씬 쉬워집니다.
마무리
애드혹 알고리즘 문제는 코드보다 사고가 먼저 틀리는 경우가 많습니다. 그래서 구현이 맞는지 확인하는 것만큼 내가 세운 규칙이 정말 항상 맞는지도 같이 확인해야 합니다.
다음 글에서는 여기서 한 걸음 더 나아가 시뮬레이션 문제는 어떻게 설계해야 할까를 이어서 다뤄보겠습니다. 이전 글인 애드혹 알고리즘 접근법: 그리디와 완전탐색 판단 기준도 함께 읽어보면 흐름이 더 잘 잡힙니다.
