애드혹 문제와 구현 문제 차이는 코딩테스트 입문자가 가장 자주 헷갈리는 부분 중 하나입니다. 어떤 문제는 구현처럼 보여도 실제로는 규칙을 먼저 찾아야 하고, 어떤 문제는 애드혹처럼 무서워 보여도 사실은 차분하게 규칙만 옮기면 끝나는 경우가 있습니다.
이번 글에서는 구현, 시뮬레이션, 애드혹을 추상 정의로만 나누지 않고 문제를 읽은 직후 무엇을 먼저 해야 하는가라는 기준으로 비교해보겠습니다. 결론부터 말하면, 구현은 규칙을 정확히 옮기는 힘이 중요하고, 시뮬레이션은 상태와 순서를 설계하는 힘이 중요하며, 애드혹은 규칙을 스스로 발견하는 발상이 더 먼저 필요합니다.
먼저 결론: 어디서부터 발상이 필요한가
- 구현 문제: 문제에 적힌 규칙이 비교적 분명하고, 핵심은 빠뜨리지 않고 정확히 옮기는 일이다
- 시뮬레이션 문제: 규칙은 주어졌지만 상태와 처리 순서를 먼저 정리해야 한다
- 애드혹 문제: 어떤 규칙으로 풀어야 할지 내가 먼저 관찰하고 정리해야 한다
즉, 세 유형의 차이는 코드 길이보다 정답에 도달하기 전에 머릿속에서 무엇을 먼저 해야 하느냐에 있습니다.
구현 문제: 규칙은 이미 있다
구현 문제는 보통 문제에서 해야 할 일이 꽤 명확하게 주어집니다. 입력을 읽고, 조건대로 처리하고, 출력하면 됩니다. 이때 핵심은 기발한 아이디어보다 조건을 빠뜨리지 않는 정확성입니다.
예를 들어 문자열에서 숫자만 골라 더하라거나, 주어진 형식대로 날짜를 변환하라거나, 명세대로 점수를 계산하라는 문제는 구현형에 가깝습니다. 문제를 읽고 나면 ‘무슨 원리로 풀지?’보다 ‘예외를 어떻게 놓치지 않을까?’가 먼저 떠오릅니다.
구현형 문제를 읽었을 때 보이는 신호
- 규칙이 문장으로 이미 자세히 주어져 있다
- 정답 아이디어를 새로 발명할 느낌이 비교적 적다
- 실수 포인트는 예외 처리, 인덱스, 형식 처리에 몰린다
- 손으로 두세 줄 따라가 보면 바로 코드 구조가 보인다
이런 문제에서는 보통 발상보다 꼼꼼함이 점수를 가릅니다. 그래서 구현 문제를 어려워하는 이유도 아이디어 부족보다 명세를 끝까지 안 읽거나, 중간 예외를 놓치는 습관에 있는 경우가 많습니다.
시뮬레이션 문제: 규칙은 있는데 순서가 중요하다
시뮬레이션 문제는 겉으로는 구현 문제처럼 보입니다. 문제에 규칙도 써 있고, 결국 코드를 짜야 하기 때문입니다. 하지만 실제로는 한 단계가 더 있습니다. 현재 상태를 무엇으로 둘지, 한 턴을 어떤 순서로 처리할지를 먼저 정리해야 합니다.
예를 들어 격자에서 캐릭터가 움직이고, 벽을 만나면 멈추고, 아이템을 먹으면 점수가 오르고, 같은 턴에 적도 움직이는 문제를 생각해보겠습니다. 이 문제는 규칙 자체는 주어져 있지만, 바로 구현에 들어가면 현재 상태와 다음 상태가 섞이기 쉽습니다.
시뮬레이션에서 먼저 적어야 하는 것
- 무엇이 상태인가
- 무엇이 한 턴마다 바뀌는가
- 무엇을 즉시 반영하고 무엇을 나중에 반영해야 하는가
- 한 턴의 처리 순서는 무엇인가
그래서 시뮬레이션은 구현과 겹치지만, 단순 구현과는 질문이 다릅니다. 구현형 문제에서는 ‘조건을 정확히 옮겼는가’가 중요하고, 시뮬레이션 문제에서는 ‘상태와 순서를 제대로 설계했는가’가 더 먼저 중요합니다.
이 부분은 이전 글인 애드혹 알고리즘 반례 찾는 법과도 연결됩니다. 시뮬레이션은 아이디어보다 구현 같아 보여도, 실제로는 처리 순서 하나만 어긋나도 맞왜틀이 쉽게 발생합니다.
애드혹 문제: 규칙을 내가 먼저 찾아야 한다
애드혹 문제는 여기서 결이 확 달라집니다. 규칙을 그대로 옮기면 되는 것이 아니라, 어떤 관찰을 해야 문제가 단순해지는지를 먼저 찾아야 하는 경우가 많기 때문입니다.
예를 들어 문자열을 최소 횟수로 뒤집는 문제를 본다고 해보겠습니다. 문제를 읽자마자 문자를 하나씩 바꾸는 시뮬레이션을 떠올릴 수도 있습니다. 하지만 실제 핵심은 문자를 하나씩 뒤집는 과정이 아니라, 0 구간과 1 구간이 몇 덩어리로 나뉘는지를 관찰하는 데 있습니다.
즉, 애드혹 문제에서는 구현 자체보다 먼저 무엇을 세어야 하는지, 무엇을 관찰해야 하는지를 찾아야 합니다. 이 단계가 잡히지 않으면 코드는 아무리 열심히 짜도 방향이 틀릴 수 있습니다.
애드혹형 문제를 읽었을 때 보이는 신호
- 문제에 정해진 알고리즘 이름이 바로 떠오르지 않는다
- 작은 입력을 손으로 써보면 패턴이나 규칙이 보일 것 같다
- 무엇을 세야 하는지부터 결정해야 한다
- 구현보다 먼저 반례와 경우 나누기가 중요하다
이런 문제에서는 성급하게 구현부터 시작하면 거의 항상 손해입니다. 작은 입력을 써보고, 규칙을 말로 설명하고, 반례를 흔들어보는 과정이 먼저 와야 합니다. 관련해서는 애드혹 알고리즘 접근법: 그리디와 완전탐색 판단 기준 글도 함께 읽어보면 흐름이 잘 이어집니다.
같은 수준의 예시로 세 유형을 나란히 비교해보자
정의를 따로 외우는 것보다, 비슷한 난이도의 예시를 나란히 놓고 보면 차이가 더 선명해집니다. 아래 세 예시는 모두 입문 수준이지만, 머리를 써야 하는 위치가 다릅니다.
예시 1: 구현형
문자열에서 대문자는 소문자로, 소문자는 대문자로 바꾸고 숫자는 그대로 둔다고 해보겠습니다. 이 문제에서는 해야 할 규칙이 이미 분명합니다. 필요한 것은 아이디어보다 문자 판별과 변환을 빠뜨리지 않는 정확성입니다.
def convert(text):
result = []
for ch in text:
if ch.isupper():
result.append(ch.lower())
elif ch.islower():
result.append(ch.upper())
else:
result.append(ch)
return ''.join(result)이 문제에서 중요한 질문은 ‘어떤 규칙을 발견할까?’가 아니라 ‘예외 없이 정확히 처리했는가?’입니다.
예시 2: 시뮬레이션형
로봇이 L, R, F 명령을 받아 격자 위를 움직인다고 해보겠습니다. 이 문제는 이동 규칙 자체는 명확하지만, 현재 방향과 위치를 어떤 순서로 갱신할지 먼저 설계해야 실수가 줄어듭니다.
def simulate(commands, n, m):
row, col, direction = 0, 0, 1
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
for command in commands:
if command == 'L':
direction = (direction + 3) % 4
elif command == 'R':
direction = (direction + 1) % 4
else:
next_row = row + dr[direction]
next_col = col + dc[direction]
if 0 <= next_row < n and 0 <= next_col < m:
row, col = next_row, next_col
return row, col이 예시의 핵심은 이동 공식이 아니라 방향을 먼저 바꾸는지, 다음 위치를 먼저 계산하는지, 범위를 언제 검사하는지입니다. 즉, 사고의 초점이 구현 그 자체보다 상태 설계에 있습니다.
예시 3: 애드혹형
0과 1로 이루어진 문자열을 모두 같은 숫자로 만들기 위한 최소 뒤집기 횟수를 구한다고 해보겠습니다. 이 문제를 처음 보면 실제로 뒤집는 시뮬레이션을 짜고 싶어질 수 있습니다. 하지만 정답은 문자열을 하나씩 바꾸는 과정이 아니라, 같은 숫자가 몇 개의 구간으로 나뉘는지 세는 관찰에서 나옵니다.
def min_flips(s):
zero_groups = 0
one_groups = 0
if s[0] == '0':
zero_groups += 1
else:
one_groups += 1
for i in range(1, len(s)):
if s[i] != s[i - 1]:
if s[i] == '0':
zero_groups += 1
else:
one_groups += 1
return min(zero_groups, one_groups)이 문제에서 중요한 것은 코드가 짧다는 사실이 아닙니다. 핵심은 무엇을 세면 문제가 단순해지는지 먼저 발견했다는 점입니다. 이것이 구현형이나 시뮬레이션형과 가장 크게 다른 부분입니다.
입문자가 가장 많이 헷갈리는 지점
- 코드가 길면 애드혹이라고 생각하는 경우
- 격자 문제는 전부 구현 문제라고 묶어버리는 경우
- 아이디어가 조금만 들어가도 무조건 애드혹이라고 부르는 경우
- 애드혹을 어려운 문제의 동의어처럼 이해하는 경우
하지만 실제로는 코드 길이보다 사고의 출발점이 더 중요합니다. 규칙이 이미 분명하면 구현에 가깝고, 상태 변화 순서를 설계해야 하면 시뮬레이션에 가깝고, 무엇을 관찰해야 할지부터 찾아야 하면 애드혹에 더 가깝습니다.
애드혹 문제와 구현 문제 차이를 빨리 구분하는 질문
- 규칙이 이미 자세히 주어져 있는가
- 상태를 턴 단위로 추적해야 하는가
- 무엇을 세거나 관찰해야 할지 내가 직접 찾아야 하는가
- 작은 입력을 써보면 규칙이 드러나는가
- 실수 포인트가 예외 처리인가, 아니면 관찰 자체인가
이 다섯 질문을 먼저 던지면 문제 이름에 끌려가지 않고 실제 풀이 방향을 더 빨리 정할 수 있습니다. 유형 이름보다 먼저, 지금 이 문제에서 무엇을 먼저 해야 하는지를 보는 습관이 중요합니다.
마무리
애드혹 문제와 구현 문제 차이는 ‘코드가 어렵냐 쉽냐’의 차이가 아닙니다. 구현은 규칙을 옮기는 정확성이 먼저이고, 시뮬레이션은 상태와 순서를 정리하는 설계가 먼저이며, 애드혹은 문제를 단순하게 만드는 관찰과 발상이 먼저입니다.
그래서 코딩테스트에서 막힐 때는 ‘나는 구현이 약한가?’라고만 묻기보다, 지금 막힌 지점이 정확한 옮기기인지, 상태 설계인지, 규칙 발견인지를 먼저 나눠보는 것이 훨씬 도움이 됩니다. 이 구분이 잡히면 문제를 읽는 속도도, 틀린 이유를 복기하는 힘도 함께 좋아집니다.
경쟁 프로그래밍 전반의 알고리즘 참고 자료가 더 필요하다면 CP-Algorithms 같은 정리 사이트도 함께 볼 수 있습니다. 다만 이번 글에서 다룬 구현, 시뮬레이션, 애드혹의 경계는 엄격한 학술 분류라기보다 실전 문제 풀이 감각을 돕는 구분으로 이해하는 편이 좋습니다.
