애드혹 문제 풀이법에서 가장 중요한 것은 공식을 많이 아는 일이 아니라, 작은 입력을 적고 패턴을 세우고 바로 반례를 넣어보는 순서입니다. 이번 글에서는 규칙 찾기, 반례 만들기, 손 시뮬레이션이 왜 먼저여야 하는지 대표 예시와 함께 정리하겠습니다.
애드혹 문제 풀이법에서 왜 접근 순서가 먼저일까
애드혹 문제는 정렬, 그리디, 시뮬레이션 중 무엇으로 볼지부터 애매한 경우가 많습니다. 이때 가장 위험한 실수는 확신 없는 규칙을 바로 코드로 굳혀버리는 것입니다. 예제가 맞는 것과 규칙이 맞는 것은 다르기 때문에, 먼저 문제 구조를 손으로 드러내는 단계가 필요합니다.
즉, 애드혹 문제에서는 정답 코드를 빨리 쓰는 사람보다 생각을 검증하는 순서를 지키는 사람이 더 안정적으로 맞힙니다.
작은 입력부터
작은 입력은 단순해서 별 의미가 없어 보일 수 있습니다. 하지만 실제로는 규칙이 어디서 시작되는지, 내가 세운 가설이 어디서 깨지는지를 가장 빨리 보여주는 도구입니다.
문자열이나 배열 문제라면 0, 1, 01, 10, 0011, 0001110처럼 가장 작은 사례를 먼저 적어보면 좋습니다. 이렇게 써보면 문자 개수를 세는 문제인지, 값이 바뀌는 횟수를 세는 문제인지, 아니면 그룹 수를 세는 문제인지가 생각보다 빨리 드러납니다.
패턴은 한 문장으로
머릿속에서만 ‘왠지 이럴 것 같다’고 느끼는 상태로는 좋은 검증이 어렵습니다. 그래서 가설을 최대한 짧은 문장으로 쓰는 습관이 중요합니다.
- 정답은 0 그룹 수와 1 그룹 수 중 더 작은 값이다
- 현재 살아남는 위치는 이전 답에서 k만큼 밀린 자리다
- 한 턴마다 상태는 현재 위치, 방향, 방문 여부만 알면 된다
규칙이 문장이 되면 곧바로 반례를 만들 수 있습니다. 반대로 문장으로 못 쓰겠다면 아직 규칙이 아니라 느낌일 가능성이 큽니다.
반례로 의심하기
작은 입력으로 패턴이 보였더라도 바로 믿으면 성급한 일반화가 생깁니다. 그래서 규칙을 세운 직후에는 일부러 흔들어봐야 합니다.
- 가장 작은 입력
- 맨 앞이나 맨 뒤만 다른 입력
- 같은 값이 길게 반복되는 입력
- 순서를 뒤집은 입력
- 예외가 하나만 끼어 있는 입력
예를 들어 “값이 바뀌는 횟수만 세면 된다”는 규칙을 세웠다면 0, 1, 01, 001, 0001110을 넣어봐야 합니다. 0과 1에서는 변화 횟수는 0이지만 그룹 수는 1이므로, 내가 세고 있는 값이 정말 정답인지 다시 확인해야 합니다.
반례를 더 체계적으로 보는 방법은 애드혹 알고리즘 반례 찾는 법 글과 함께 보면 좋습니다.
문자열 그룹 예시
문자열 뒤집기 계열에서는 문자 개수보다 그룹 구조가 먼저 보일 때가 많습니다. 예를 들어 0001110을 손으로 적으면 000, 111, 0처럼 세 개의 그룹이 드러납니다.
여기서 중요한 질문은 “문자 개수를 줄이는 문제인가, 그룹을 줄이는 문제인가”입니다. 뒤집기 연산이 보통 문자 하나가 아니라 연속된 그룹에 영향을 주기 때문에, 숫자 개수보다 경계와 그룹을 먼저 보는 편이 문제 구조에 더 가깝습니다.
이 흐름은 문자열 뒤집기 최소 횟수, 왜 그룹 수의 최솟값이 답일까 글과도 그대로 이어집니다.
요세푸스 패턴 예시
요세푸스 문제는 작은 표에서 규칙이 보이는 대표 예시입니다. 처음부터 일반식을 외우기보다 작은 n을 손으로 적는 편이 훨씬 감각을 잘 만들어 줍니다.
- n = 1 → 1
- n = 2 → 1
- n = 3 → 3
- n = 4 → 1
- n = 5 → 3
- n = 6 → 5
이 표만 봐도 뭔가 규칙이 있다는 감이 옵니다. 중요한 것은 감이 왔다는 사실보다, 작은 표를 만들었기 때문에 관찰할 재료가 생겼다는 점입니다.
cp-algorithms의 Josephus problem 정리도 작은 값 표를 만든 뒤 이전 답과 현재 답의 관계를 관찰해 점화식으로 정리하는 흐름을 보여줍니다. 자세한 접근은 애드혹 알고리즘 대표문제 풀이: 요세푸스 문제는 왜 시뮬레이션보다 규칙 찾기가 중요할까 글과 연결해서 보면 좋습니다.
손 시뮬레이션
상태 변화가 있는 애드혹 문제는 손으로 2~3턴 먼저 돌려보는 것이 특히 중요합니다. 예를 들어 로봇이 격자에서 F, R, F, L 같은 명령을 따른다면, 코드보다 먼저 현재 위치, 현재 방향, 방문 여부 같은 상태를 적어보는 편이 훨씬 안전합니다.
- 명령을 읽는다
- 회전인지 이동인지 구분한다
- 다음 좌표를 계산한다
- 범위를 벗어나는지 본다
- 상태를 갱신한다
이렇게 손으로 먼저 써두면 어떤 값이 상태이고, 어떤 값이 임시 계산값인지 분명해집니다. 시뮬레이션 감각은 시뮬레이션 문제 풀이법: 상태 정의와 구현 순서 글과 함께 보면 더 잘 이어집니다.
코드로 옮기기 전 질문
- 내가 세는 값이 정확히 무엇인가
- 한 번의 연산이 무엇을 바꾸는가
- 예외 케이스는 어디서 생기는가
- 현재 상태와 다음 상태를 구분했는가
- 규칙을 한 문장으로 설명할 수 있는가
이 다섯 질문에 답이 되지 않은 상태에서 구현을 시작하면, 디버깅이 구현 실수와 사고 실수가 섞여버립니다. 그래서 손풀이 단계는 느린 우회가 아니라 오히려 가장 빠른 검증 단계입니다.
작은 표를 빨리 돌려보는 코드
아래 코드는 요세푸스 문제를 작은 입력으로 직접 돌려보는 가장 단순한 예시입니다. 핵심은 성능이 아니라 작은 표를 빨리 만들어 패턴을 보는 것입니다.
from collections import deque
def winner(n, k):
q = deque(range(1, n + 1))
while len(q) > 1:
q.rotate(-(k - 1))
q.popleft()
return q[0]
for n in range(1, 8):
print(n, winner(n, 2))이런 작은 출력은 정답 그 자체보다, 내가 세운 가설이 어떤 흐름을 보이는지 관찰하는 재료가 됩니다.
실전 체크리스트
- 가장 작은 입력 3~5개를 적는다
- 손으로 답을 구해 표를 만든다
- 규칙 후보를 한 문장으로 쓴다
- 반례 후보를 넣어 규칙을 흔든다
- 손으로 2~3턴 시뮬레이션한다
- 무엇을 세는지 한국어로 설명한다
- 그다음에 의사코드와 구현으로 간다
정리하면 작은 입력 → 패턴 가설 → 반례 검증 → 손 시뮬레이션 → 구현 순서가 잡히면, 애드혹 문제는 훨씬 덜 막힙니다.
마무리
애드혹 문제 풀이법의 핵심은 번뜩이는 직감이 아니라, 작은 입력을 먼저 적고 규칙을 문장으로 만들고 바로 의심해보는 습관입니다. 즉, 애드혹은 감으로 푸는 문제가 아니라 생각을 검증하는 순서로 푸는 문제에 가깝습니다.
이전 글인 애드혹 알고리즘 접근법: 그리디와 완전탐색 판단 기준, 애드혹 알고리즘 반례 찾는 법과 함께 읽으면 애드혹 문제를 볼 때의 사고 흐름이 더 단단해질 것입니다.
