231. Ad-Hoc

여섯 번째로 애드 혹(Ad-Hoc)에 대해서 다룬다. 애드 혹은 굉장히 정의하기 어려운 용어인데, 이름이 '애드 혹'인 어떤 알고리즘이 존재하는 게 아니라 그 문제를 풀기 위해 필요한 일반적인 자료 구조나 알고리즘 지식이 존재하지 않고 그 문제만을 풀기 위한 방법을 필요로 할 경우 그런 문제를 애드 혹 성격의 문제라고 한다. 따라서 사람마다 체감 난이도가 매우 큰 차이를 보일 가능성이 다른 유형의 문제들에 비해 높고, 어떤 문제들은 애드 혹에 속하는지를 두고도 의견이 갈리기 쉽다. 그밖에 '풀이가 간단하다'와 '문제가 쉽다'의 차이를 잘 느낄 수 있는 유형이기도 하다.

 

 이런 문제들은 관찰이나 증명이 문제 풀이의 대부분일 가능성이 높다. 증명을 하지 않고 찍어 맞추기(Proof By AC, PBA)를 시도하기도 쉬운 문제들이 많지만 어떤 문제들에 나오는 증명은 나중에 다른 문제들을 풀 때도 도움이 되는 것들이므로 이해하고 넘어가도록 하자. 연습문제로도 관찰과 증명이 도움이 되는 것들을 넣었다. 설명을 일부러 덜 구체적으로 적었기 때문에, 왜 그런 풀이가 가능하고 이떤 문제에서 어떤 발상을 하는지 충분히 고민해 보는 것을 추천한다.

 

[연습문제]

 

BOJ 25629. 홀짝 수열 (Bronze III)

홀수의 개수가 짝수의 개수보다 하나 많거나 개수가 같으면 $1$, 그렇지 않으면 $0$이 답이 된다.

 

BOJ 13322. 접두사 배열 (Bronze I)

왜 접미사 배열은 쓰지만 접두사 배열은 안 쓰는지 알아보자.

 

BOJ 28292. 개미 수열 (Silver V)

자릿수가 $3$보다 커질 수 없는 이유를 생각해 보자.

 

BOJ 33931. 체크박스 누르기 (Silver I)

각 체크박스를 클릭하는 횟수의 차이가 $1$을 넘을 수 없다.

 

BOJ 27738. 연산자 파티 (Gold V)

Bitwise Right Shift 연산을 수행할 때 $i$가 크다면 결과가 항상 $0$이 된다는 점을 이용해서 시뮬레이션을 최적화한다.

 

BOJ 28128. 현대모비스 특별상의 주인공은? (Gold II)

$1 \times 2$ 격자판과 $1 \times 3$ 격자판만 확인해도 되는 이유가 무엇일까?

 

BOJ 1307. 마방진 (Platinum V)

마방진을 만드는 방법을 인터넷에서 찾아보자.

 

BOJ 22904. 오렌지 수 (Platinum III)

제곱수의 자릿수의 합에 어떤 특징이 있는지 살펴보자. 규칙을 알아냈다면, 노가다를 통해 반복되는 패턴을 찾으면 된다.

 

BOJ 21216. Emails (Platinum II)

트리의 지름을 구하는 방법 중 아무 정점에서 가장 먼 정점으로 이동하는 과정을 두 번 반복하는 방법이 있었다. 이 방법을 그래프에 응용하면 어떻게 될지 생각해 보자.

 

CF 1270C. Make Good (1400)

$n$개의 값을 모두 XOR한 결과를 $x$라고 하자. 수열에 $x$를 추가하면 $n + 1$개의 값을 모두 XOR한 결과는 $0$이다.

 

CF 1119C. Ramesses and Corner Inversion (1500)

두 행렬을 XOR했을 때 각 행과 열이 짝수 개의 $1$을 포함해야 한다. BOJ 25201번과 거의 똑같은 문제인데 백준 문제는 코포 문제에 비해 굉장히 높은 티어가 달려 있다.

 

CF 1189D1. Add on a Tree (1600)

리프가 $2$개이면 NO, 그렇지 않으면 항상 YES가 답이 된다. 왜 그런지 생각해 보자.

 

CF 1566E. Buds Re-hanging (2000)

Bud들을 전부 루트에 붙였다가 다시 분배해주면 된다.

 

CF 1621D. The Winter Hike (2100)

왼쪽 위 사분면과 오른쪽 아래 사분면 사이를 이동하려면 사분면의 귀퉁이 양 옆의 $8$칸 중 하나를 반드시 지나야 한다.

 

CF 1485D. Multiples and Power Differences (2200)

체스보드처럼 그리드를 분할해서 한쪽에는 전부 $1$부터 $16$까지의 최소공배수를 넣고 다른 쪽에는 ${a_{i, j}}^4$를 넣어 준다.

 

CF 1470D. Strange Housing (2200)

아무 정점에서 시작해서 그 정점과 연결된 정점을 모두 제거하고, 제거한 정점들 중 하나 이상과 인접한 정점들을 다시 확인하는 과정을 반복한다.

 

CF 1495C. Garden of the Sun (2300)

$3$줄마다 전부 빈 줄로 만들고 나머지 줄은 적당히 이어 주면 된다.

 

CF 1392F. Omkar and Landslide (2400)

인접한 원소의 대소 관계가 바뀔 수 없고, 마지막 상태에서 인접한 원소의 차이가 $2$ 이상이 될 수 없다.

 

→ solved.ac tag: ad_hoc