애드 혹 (Ad Hoc)

정의

애드 혹 (Ad Hoc) 은 범용 알고리즘이 아닌, 그 문제만의 관찰·트릭·창의적 사고로 푸는 문제 유형. 라틴어로 “이 목적을 위한” 이라는 뜻.

정형화된 자료구조나 DP 점화식 없이, 문제를 꼼꼼히 읽고 패턴·대칭·패리티 같은 수학적 성질을 발견하는 것이 핵심.

문제 상황과 동기

알려진 알고리즘 (BFS, DP, 세그트리 등) 이 명확히 적용되지 않는다.

• naive: 단순 시뮬레이션, 브루트포스, O(2^N) 또는 O(N^3) 이상.
• ad hoc: 문제 안의 숨은 성질 (패리티, 주기, 대칭, 경우 분류) 을 찾아 O(1) ~ O(N) 으로 해결.

핵심 통찰: 문제 자체가 힌트. 제약, 입력 범위, 샘플 입출력에서 규칙성을 귀납.

자주 등장하는 PS 위치:

• Codeforces Div2 A~C (관찰 위주)
• IOI, ICPC 의 창의적 문제
• 프로토타이핑, 해커톤 (시간 제약 아래 빠른 아이디어 검증)

시각화

핵심 아이디어

invariant: 문제 조건 자체가 해법의 힌트.

대표 관찰 기법:

1. 패리티 (parity): 홀짝 구분. 체스판 색칠, 불변량.
2. 대칭 (symmetry): 좌우/상하 대칭, 순환 대칭.
3. 극값 (extremal): 최댓값/최솟값이 정답인 경우.
4. 경우 분류 (case work): if-else 로 모든 경우를 나눔 (→ 케이스 워크 참고).
5. 주기 (periodicity): 반복 패턴 (예: 1,2,3,1,2,3,…).
6. 그리디 (greedy): 증명 없이도 직관적으로 최적.

알고리즘

1. 문제 읽기 (2~3회 정독, 제약·샘플 주목)
2. 샘플 입출력 손으로 시뮬레이션
3. 패턴 / 불변량 찾기 (패리티, 대칭, 극값, ...)
4. 가설 세우기 → 반례 찾기
5. 반례 없으면 증명 (또는 "AC 받으면 증명" → submit)
6. 구현 (보통 짧고 단순)

구현

예제: 체스판 색칠 (패리티 관찰)

8×8 체스판에서 (r1, c1) 에서 (r2, c2) 로 나이트(Knight) 이동. 흑백 칸이 번갈아 나오는가?

관찰: 나이트 이동은 항상 다른 색으로 이동. (r + c) % 2 가 플립.

// 체스판 색칠: (r+c) % 2
#include <bits/stdc++.h>
using namespace std;
int main() {
  int r1, c1, r2, c2;
  cin >> r1 >> c1 >> r2 >> c2;
  // 나이트 한 번에 다른 색으로
  if ((r1 + c1) % 2 == (r2 + c2) % 2) {
      cout << "same color, need even steps\n";
  } else {
      cout << "different color, need odd steps\n";
  }
}

# 패리티 관찰, O(1)
r1, c1, r2, c2 = map(int, input().split())
if (r1 + c1) % 2 == (r2 + c2) % 2:
  print("same color, need even steps")
else:
  print("different color, need odd steps")

1 1 2 3

same color, need even steps

1 1 2 2

different color, need odd steps

예제: 구슬 뒤집기 (대칭 관찰)

N개 구슬이 일렬. 좌우 대칭이면 “YES”, 아니면 “NO”.

관찰: a[i] == a[N-1-i] for all i.

// 좌우 대칭 체크, O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
  bool ok = true;
  for (int i = 0; i < n / 2; i++) {
      if (a[i] != a[n - 1 - i]) ok = false;
  }
  cout << (ok ? "YES" : "NO") << "\n";
}

# 리스트 reverse 비교, O(N)
n = int(input())
a = list(map(int, input().split()))
print("YES" if a == a[::-1] else "NO")

5
1 2 3 2 1

YES

4
1 2 3 4

NO

예제: 수열 주기 찾기 (periodicity)

수열 1, 2, 3, 1, 2, 3, ... 에서 k번째 수는?

관찰: 주기 3. ans = ((k - 1) % 3) + 1.

// 주기 3, O(1)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int k; cin >> k;
  cout << ((k - 1) % 3) + 1 << "\n";
}

# 나머지 연산, O(1)
k = int(input())
print(((k - 1) % 3) + 1)

// Java mod, O(1)
import java.util.*;
public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int k = sc.nextInt();
      System.out.println(((k - 1) % 3) + 1);
  }
}

7

1

10

1

복잡도

변형

함정

1. 반례 간과

관찰이 틀렸는데도 샘플만 맞아서 AC 로 착각. 엣지 케이스 (N=1, 음수, 0, 최댓값) 수동 검증 필수.

2. 과도한 일반화

“N≤10 인데 DP?” → 오버엔지니어링. ad hoc 은 단순한 if-else 로 충분한 경우가 많다.

3. 증명 없이 제출

관찰이 맞는지 손으로 반례 3~5개 찾아보고 제출. Codeforces 는 강한 프리테스트 덕분에 괜찮지만, 대회에선 WA 패널티.

4. 문제 잘못 읽기

제약 오해 (1-indexed vs 0-indexed, inclusive vs exclusive) 가 ad hoc 에서 치명적. 2~3회 정독.

BOJ 연습 문제

참고

• 해 구성하기 (증명보다 명시적 구성)
• 케이스 워크 (경우 분류 체계화)
• 그리디 (직관적 최적화)