애드혹 문제란 무엇인가를 한 줄로 말하면, 딱 맞는 대표 공식을 바로 꺼내기보다 문제의 규칙을 읽고 그 자리에서 풀이 방식을 세우는 문제입니다. 코딩테스트에서는 공식 암기보다 조건을 잘게 읽고 상태를 추적하는 판단력이 더 중요할 때가 있는데, 바로 그 감각을 요구하는 대표 유형이 애드혹 문제입니다.
이번 글에서는 애드혹 문제가 무엇인지, 브루트포스와 구현형과는 무엇이 다른지, 그리고 문제에서 애드혹 냄새를 어떻게 맡아야 하는지 단계적으로 정리하겠습니다. 코드보다 먼저 직관 예시를 두고, 마지막에 짧은 시뮬레이션 코드 한 개만 붙여 감을 잡을 수 있게 구성했습니다.
애드혹 문제란 무엇인가
애드혹 문제는 보통 대표 알고리즘 이름이 바로 떠오르지 않고, 문제의 조건을 읽으면서 규칙을 먼저 발견해야 풀리는 경우가 많습니다. 그래서 흔히 말하는 그래프, DP, 이분 탐색처럼 이름표가 강한 문제와 느낌이 다릅니다.
- 대표 알고리즘 이름보다 규칙 관찰이 먼저 필요하다
- 예시를 손으로 따라가 보면 풀이 방향이 보이는 경우가 많다
- 예외 조건 하나가 전체 로직을 바꾸기도 한다
- 문제를 사람이 먼저 번역한 뒤 코드로 옮겨야 한다
중요한 점은 애드혹이 아무렇게나 푸는 문제가 아니라는 것입니다. 오히려 작은 규칙과 예외를 정확히 읽고, 필요한 상태를 나눈 뒤, 그 순서를 코드로 옮기는 문제에 가깝습니다.
왜 어렵게 느껴질까
- 이름표가 약해서 무엇부터 떠올려야 할지 막막하다
- 예외 조건이 부수적인 장식이 아니라 핵심 로직인 경우가 많다
- 손으로 시뮬레이션해 보기 전까지 문제 구조가 잘 안 보인다
대표 알고리즘 문제는 큰 틀을 잡은 뒤 예외를 붙이는 경우가 많습니다. 반대로 애드혹 문제는 예외를 놓치면 큰 틀 자체가 틀어지기 쉽습니다. 그래서 문제를 읽는 단계가 유난히 중요하게 느껴집니다.
브루트포스와 차이
브루트포스는 가능한 경우를 넓게 시도해 보는 접근에 가깝습니다. 반면 애드혹은 문제 속 규칙을 읽고, 쓸데없는 경우를 애초에 만들지 않는 판단에 더 무게가 있습니다.
- 경우를 거의 다 돌려 본다 → 브루트포스 성격이 강하다
- 규칙을 읽고 흐름을 직접 만든다 → 애드혹 성격이 강하다
예를 들어 방향 전환 규칙이 있는 이동 문제에서 모든 상태를 넓게 탐색하면 브루트포스 쪽에 가깝습니다. 하지만 방향이 언제 바뀌는지, 같은 패턴이 반복되는지 먼저 발견해서 계산을 줄이면 애드혹 감각이 들어간 것입니다.
브루트포스는 많이 시도하는 힘이고, 애드혹은 어떻게 읽어야 덜 시도할 수 있는지 찾는 힘이라고 기억하면 실전에서 구분이 쉬워집니다.
구현형과 차이
많은 애드혹 문제는 구현 코드로 풀립니다. 그래서 구현형과 거의 같은 말처럼 느껴질 수 있습니다. 하지만 둘의 초점은 미묘하게 다릅니다.
- 구현형: 규칙은 비교적 분명하고, 그것을 실수 없이 코드로 옮기는 힘이 중요하다
- 애드혹: 무엇을 규칙으로 봐야 하는지 먼저 읽어내는 힘이 중요하다
즉, 구현형은 번역 정확도에 무게가 있고, 애드혹은 번역하기 전에 무엇을 먼저 번역해야 하는지 판단하는 힘에 무게가 있습니다. 현실 문제는 둘이 자주 섞이므로, 칼같이 나누기보다 판단의 중심이 어디에 있는지 보는 편이 좋습니다.
애드혹 신호
코딩테스트에서 아래 신호가 보이면 애드혹 가능성을 먼저 떠올려 볼 만합니다.
- 공식 이름이 바로 안 붙는데, 문제는 분명 풀 수 있을 것 같다
- 예시를 손으로 따라가면 특정 순서나 주기가 보인다
- 조건 문장이 길고 세세한데, 그 문장 하나하나가 로직이 될 것 같다
- 자료구조보다 상태 변화와 예외 처리가 먼저 중요해 보인다
- 반례가 쉽게 떠오르고, 그 반례 정리가 곧 풀이가 될 것 같다
이때는 내가 알고리즘을 모르는 것이 아니라, 규칙 관찰이 먼저 필요한 문제일 수 있다고 생각해 보는 편이 훨씬 도움이 됩니다.
직관 예시
방향 전환 로봇
로봇이 일직선 칸 위를 움직인다고 해 보겠습니다. 평소에는 오른쪽으로 한 칸씩 가는데, 숫자가 3의 배수인 칸에 올라가면 방향을 바꾸고, 벽에 닿으면 한 턴 쉬고 반대로 움직입니다.
이 문제를 보자마자 대표 알고리즘이 떠오르지는 않습니다. 대신 현재 위치, 현재 방향, 벽 충돌 여부처럼 상태 두세 개를 적고 순서대로 갱신하면 풀립니다. 자료구조보다 상태 갱신 순서가 핵심인 전형적인 애드혹 예시입니다.
문자열 압축 흉내
문자열을 왼쪽부터 읽다가 같은 문자가 2개 연속이면 하나로 줄이고, 3개 이상이면 개수를 적는다고 해 보겠습니다. 그런데 숫자는 그대로 두고, 대문자와 소문자는 합치지 않는다는 예외가 붙습니다.
이때 먼저 해야 할 일은 공식을 찾는 것이 아닙니다. 무엇을 같은 문자로 볼지, 그룹이 어디서 끊기는지, 길이가 1, 2, 3 이상일 때 출력을 어떻게 바꿀지부터 정리해야 합니다. 즉 애드혹 문제는 종종 문제를 먼저 사람이 번역한 뒤 코드로 옮기는 작업입니다.
접근 순서
- 문제를 상태로 바꾼다. 예: 현재 위치, 방향, 점수, 보고 있는 문자
- 규칙을 사건 단위로 자른다. 예: 매 턴, 문자를 하나 읽을 때마다
- 예외를 처음부터 분리한다. 예: 시작점, 마지막 그룹, 벽 충돌 직후
- 작은 예시를 손으로 돌리며 상태 변화가 맞는지 확인한다
- 그다음에 코드로 옮긴다
애드혹 문제는 코딩 실수보다 해석 실수가 더 무섭습니다. 그래서 코드는 마지막에 쓰는 편이 오히려 더 빠른 경우가 많습니다.
짧은 코드 예시
아래 코드는 방향 전환 로봇 아이디어를 아주 단순하게 옮긴 예시입니다. 핵심은 화려한 알고리즘이 아니라, 상태를 정하고 순서대로 갱신하는 방식입니다.
position = 0
direction = 1
limit = 10
trace = []
for _ in range(12):
next_position = position + direction
if next_position < 0 or next_position > limit:
direction *= -1
trace.append((position, "turn-at-wall"))
continue
position = next_position
if position % 3 == 0:
direction *= -1
trace.append((position, direction))
print(trace)이 예시는 애드혹 문제의 본질을 잘 보여 줍니다. 상태를 정하고, 순서를 정하고, 예외를 분기하고, 직접 추적해 보는 것. 결국 애드혹의 본질은 대단한 공식보다 해석 순서에 있습니다.
자주 하는 오해
- 애드혹은 운 좋으면 푸는 문제다 → 아니다. 감이 아니라 상태 분해와 예외 정리가 핵심이다
- 애드혹은 브루트포스보다 항상 쉽다 → 아니다. 경우의 수보다 예외가 더 까다로울 수 있다
- 구현만 잘하면 된다 → 아니다. 먼저 어떤 규칙을 세워야 하는지 보는 눈이 필요하다
- 대표 알고리즘이 없으면 공부할 수 없다 → 아니다. 상태 나누기, 손 시뮬레이션, 반례 정리 습관을 훈련하면 된다
정리
애드혹 문제란 무엇인가를 다시 짧게 정리하면, 정형화된 대표 공식을 바로 적용하기 어려운 대신 문제 속 규칙과 예외를 읽어 내는 과정이 핵심인 문제입니다. 브루트포스가 많이 시도하는 힘이라면, 애드혹은 잘 읽어서 덜 시도하는 힘에 가깝습니다.
코딩테스트에서 애드혹 문제를 만나면 먼저 알고리즘 이름이 안 떠오른다고 조급해할 필요는 없습니다. 상태를 적고, 예시를 손으로 돌리고, 예외를 분리해 보세요. 그 순간부터 문제는 훨씬 덜 추상적으로 보이기 시작합니다.
관련해서 범위를 줄여 가는 판단이 필요한 문제는 투 포인터 알고리즘이란 무엇인가: 언제 완전탐색 대신 범위를 줄여야 할까를 함께 보면 좋습니다. 또 조건을 만족하는 값의 경계를 찾는 사고는 이분탐색(binary search) 총정리 – lower bound, upper bound, parametric search까지 한 번에 이해하기와도 자연스럽게 연결됩니다. 외부 참고로는 USACO Guide의 Simulation 자료가 문제를 그대로 따라가는 감각을 잡는 데 도움이 됩니다.
