복잡한 문제를 마주했을 때 정해진 알고리즘 없이 상황에 맞게 직접 로직을 구현해 문제를 해결하는 방식이 바로 애드혹(Ad-hoc) 알고리즘이다. 일반적인 정렬, 이분 탐색, DP, 그래프 탐색 등과는 다르게 애드혹은 특정 문제에 특화된 방식으로 맞춤형 해결법을 구현하는 접근이다. 말 그대로 “임기응변적인 해결 전략”이라고 볼 수 있다.
Ad-hoc은 라틴어로 “그것을 위하여(for this)”라는 의미이며 특정 목적을 달성하기 위해 설계된 임시 방안을 말한다. 프로그래밍에서도 마찬가지로 문제 상황에 맞는 로직을 직접 구현하는 것이 핵심이다.
언제 사용하는가?
- 문제 조건이 정해진 알고리즘으로는 해결하기 애매할 때
- 조건 분기와 구현 능력이 중요한 문제
- 문제의 제약이 작고 구현 위주로 구성된 문제
- 패턴이 눈에 보이지 않고 브루트포스도 가능해 보일 때
즉, 문제의 본질이 명확한 알고리즘 풀이보다 “문제 해석력”과 “구현력”이 더 중요한 경우가 많다. 그래서 코딩 테스트 실전 감각이나 문제 직관을 키우는 데에 매우 중요한 유형이다.
특징
| 항목 | 설명 |
|---|---|
| 정형화 여부 | 기존 알고리즘 없이 자유롭게 구현 |
| 중요 요소 | 구현력, 조건 처리, 시뮬레이션, 직관 |
| 시간 복잡도 | 문제에 따라 유동적 (브루트포스 기반도 많음) |
| 자주 등장하는 예시 | 문자열 파싱, 단순 수학 계산, 게임판 시뮬레이션, 조건 분기 문제 등 |
장점
- 문제 상황을 그대로 코드로 옮기기만 하면 되는 경우가 많아 진입 장벽이 낮음
- 다양한 문제 풀이 경험을 쌓는 데 효과적
- 사고의 유연성을 기를 수 있음
단점
- 정형화된 전략이 없어서 연습이 부족하면 막막하게 느껴질 수 있음
- 문제 해석을 잘못하면 엉뚱한 구현으로 이어지기 쉬움
- 시간 복잡도를 고려하지 않으면 TLE(Time Limit Exceeded) 발생 가능
대표 예제
예제 1: 백준 1436 - 영화감독 숌
문제 설명
숫자에 연속된 666이 포함된 숫자들 중에서 N번째 수를 구하라.
예: 666, 1666, 2666, ..., N번째로 작은 수
접근 방식
1. 숫자 666부터 하나씩 증가하며 666이 포함된 수를 찾는다.
2. count가 N이 되면 해당 숫자를 출력한다.
3. String.valueOf(i).contains("666") 활용
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int num = 666;
int count = 0;
while (true) {
if (String.valueOf(num).contains("666")) {
count++;
if (count == N) {
System.out.println(num);
break;
}
}
num++;
}
}
}예제 2: 백준 14891 - 톱니바퀴 (골드 3)
문제 설명
4개의 톱니바퀴가 있고 각 톱니바퀴는 8개의 톱니(0 또는 1)를 가진다. 톱니바퀴는 한 칸씩 시계 또는 반시계 방향으로 회전할 수 있으며 회전 시 인접한 톱니가 서로 다르면 옆 톱니바퀴도 반대 방향으로 회전한다.
N개의 회전 명령이 주어졌을 때, 최종적으로 톱니바퀴의 상태에 따라 점수를 계산하라.
- 톱니의 12시 방향(0번 인덱스)의 값이 1이면
2^i점 (i는 톱니바퀴 번호 0~3)
접근 방식
- 톱니바퀴를 Deque 또는 배열 회전으로 표현
- 회전 명령을 받을 때마다 인접한 톱니 상태를 비교
- 전파 여부를 BFS처럼 처리하거나 회전 여부를 배열에 저장 후 한 번에 회전
- 마지막에 각 톱니바퀴의 0번 인덱스만 보고 점수 계산
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
static int[][] gears = new int[4][8]; // 톱니바퀴 4개
static int[] dir; // 회전 방향 저장
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 톱니바퀴 상태 입력
for (int i = 0; i < 4; i++) {
String line = br.readLine();
for (int j = 0; j < 8; j++) {
gears[i][j] = line.charAt(j) - '0';
}
}
int K = Integer.parseInt(br.readLine());
while (K-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int gearIdx = Integer.parseInt(st.nextToken()) - 1;
int rotateDir = Integer.parseInt(st.nextToken());
dir = new int[4];
dir[gearIdx] = rotateDir;
// 왼쪽 확인
for (int i = gearIdx - 1; i >= 0; i--) {
if (gears[i][2] != gears[i + 1][6]) {
dir[i] = -dir[i + 1];
} else break;
}
// 오른쪽 확인
for (int i = gearIdx + 1; i < 4; i++) {
if (gears[i - 1][2] != gears[i][6]) {
dir[i] = -dir[i - 1];
} else break;
}
// 회전 실행
for (int i = 0; i < 4; i++) {
if (dir[i] != 0) rotate(i, dir[i]);
}
}
// 점수 계산
int score = 0;
for (int i = 0; i < 4; i++) {
if (gears[i][0] == 1) score += (1 << i);
}
System.out.println(score);
}
private static void rotate(int idx, int d) {
if (d == 1) { // 시계 방향
int temp = gears[idx][7];
for (int i = 7; i > 0; i--) {
gears[idx][i] = gears[idx][i - 1];
}
gears[idx][0] = temp;
} else { // 반시계 방향
int temp = gears[idx][0];
for (int i = 0; i < 7; i++) {
gears[idx][i] = gears[idx][i + 1];
}
gears[idx][7] = temp;
}
}
}📝 느낀점
Ad-hoc 알고리즘 문제들은 정해진 공식을 외워서 적용하는 것이 아니라 문제를 얼마나 정확히 이해하고 시뮬레이션을 정교하게 구현하느냐가 핵심임을 다시 한 번 느꼈다. 특히 톱니바퀴 문제처럼 회전 조건이 연쇄적으로 전파되는 시뮬레이션 문제에서는 조건 분기를 명확히 파악하고 중간 상태를 저장하며 순차적으로 처리하는 로직 설계 능력이 중요했다. 단순히 코드만 짜는 것이 아니라 문제의 흐름을 직접 손으로 써보거나 그림을 그려보며 상황을 파악하는 습관이 도움이 되었다.
또한 문자열 탐색 문제처럼 간단해 보이는 문제도 브루트포스 접근 외에 최적화가 가능한 지점을 찾아보는 연습이 필요하다고 느꼈다. Ad-hoc 문제는 구현 중심이라고 해서 단순하다고 오해하기 쉽지만 오히려 테스트 케이스를 놓치거나 조건을 잘못 이해하면 디버깅이 더 어렵고 복잡한 버그로 이어질 수 있다는 점에서 집중력과 꼼꼼함이 동시에 요구된다. 앞으로도 다양한 유형의 Ad-hoc 문제를 풀어보며 실전 감각과 구현력을 꾸준히 키워야겠다고 다짐했다.
