ad hoc

애드혹(ad hoc)은 라틴어로 "이것을 위하여(for this)"라는 뜻이다. 일반적이지 않은 좁은 맥락에서의 문제만 해결할 수 있는 풀이나, 틀리지 않기 위해서 본 주장에 덧대는 부수적인 주장 따위를 가리킬 때 사용하는 단어다.

 

예를 들어 지구가 천체의 중심이라고 주장한 천동설에서는 기존 이론의 한계 바깥에 있는 천체의 움직임을 설명하기 위해 주전원(周轉圓, epicycle)이라는 개념을 도입했다. 그러나 우리는 천동설이 틀렸음을 안다. 태양계의 천체들은 태양을 중심으로 하는 타원 궤도 위를 공전한다. 물론 여러 개의 주전원을 통해 (마치 푸리에 급수의 합처럼) 근사적으로 올바른 궤도를 표현할 수는 있겠으나, 근본적인 해답은 되지 못한다. 이 또한 ad hoc이다.

 

하지만 자원이 한정되어 있거나, 우리가 알고 있는 방법론이 모자란 상황에서 정확한 풀이를 찾기란 요원한 일이다. 정확함을 요하는 논의에서는 지양해야겠지만, 당장 풀이가 필요하다면 일단 해결을 해볼 수도 있다.

 

알고리즘 문제 해결 대회(competitive programming)에서 말하는 'ad hoc' 카테고리의 문제는 잘 알려진 알고리즘 카테고리에 속하지 않는 풀이를 요하는 문제군을 가리킨다고 한다. solved.ac(BOJ)에서 해당 카테고리를 보고 그런 분류가 있다는 것을 처음 알았다. 한 문제 풀어보기로 했다.

 

https://www.acmicpc.net/problem/10158

10158번: 개미

 

이하는 내 사고 과정이다. 다른 사람의 영향을 받지 않고 해당 문제를 풀고 싶으신 분들은 일단 포스팅 읽기를 멈추길 권한다.

 

 

 

 

 

가장 처음 떠오른 것은 '거울 대칭된 지형을 이어붙여서 푸는 문제인가?'라는 아이디어였다. 비유적으로 말하자면, 현실 세계에서 반사되어 나오는 것은 거울 세계 너머로 직진하는 것과 거의 동등하므로. 즉 기울기가 1인 직선의 길이가 주어졌을 때, 이어진 거울 세계에서의 종착점을 구하는 문제라고 판단한 것이다.

 

그렇게 가로로 몇 번 반사하는지, 세로로 몇 번 반사하는지 구해야겠다고 생각했는데, 마음 한구석에 걸리는 부분이 있었다. 지금 접근은 조금 지저분하고 더 나은 풀이가 있다는 느낌이었다.

(이러한 직관을 보다 명시적으로 끌어내고 훈련하는 방법도 굉장히 중요하다고 보는데, 아직 잘 모르겠다. 나중에 포스팅할 기회가 있을 것 같다.)

 

한참을 들여다보고 나서야 하나를 깨달았다. 'x좌표의 움직임과 y좌표의 움직임은 독립적이지, 참.' 그러니까 이 문제는 결국 2개의 서브-문제로 쪼갤 수 있었다. t초 후의 x좌표를 구하시오, 그리고 t초 후의 y좌표를 구하시오.

 

책정된 등급이 실버3인 이유가 있었다. 여기까지 쪼개고 나면 정말 별 거 아닌 문제가 되어버리기 때문이다. 하지만 거기까지 도달하는 과정이 (적어도 내겐) 쉽지 않았다.

 

다른 ad hoc 카테고리의 문제를 보았는데, 이렇게 서브-문제를 예쁘게 정의하는 부류의 문제들이 있는 듯했다. 거기까지 도달하고 나서야 우리가 잘 아는 구현이나 브루트포스 등의 알고리즘 문제로 환원된달까.

 

생각해보면 결은 다르지만 비슷한 경험이 두어 달 전에도 있었다.

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV139KOaABgCFAYh&

SW Expert Academy

 

위 문제는 SWEA의 'Flatten'이라는 문제다. 내용을 확인하려면 회원가입이 필요하니 문제의 설명을 잠깐 하자면:

 

 

임의의 높이로 적층된 상자들이 일렬로 늘어서 있다.

가장 많이 적층된 곳의 상자를 가장 적게 적층된 곳으로 옮겨서 평탄화하려고 한다.

주어진 횟수만큼 행위를 반복했을 때 최고점과 최저점의 차이를 반환하시오.

 

 

나는 해당 문제의 요구를 그대로 이행했다. 높이를 저장한 1차원 배열에서 최고값과 최저값을 찾아서 각각의 값을 1씩 빼고 더하고. 이를 주어진 횟수만큼 반복했다.

 

그리고 다른 사람들은 어떻게 풀었나 보는데 재밌는 접근이 있었다. 정렬 내장함수를 이용하여 오름차순으로 정렬한 뒤, 첫 번째 인덱스의 값을 1 올리고 마지막 인덱스의 값을 1 내렸다. 그리고 다시 정렬. 이를 주어진 횟수만큼 반복했다.

 

재밌었던 점은 그 풀이가 내 풀이보다 더 빨랐다는 것이다. 물론 시행에 편차가 있겠지만, 그래도 시간이 얼마 차이나지 않는다는 건 흥미로웠다. 내 추측은 이랬다. '연산 이후에도 거의 정렬된 배열이므로 재정렬에 시간이 얼마 걸리지 않는 모양이다.'

 

ad hoc 문제도 그렇고 그 경험도 그렇고, 결국 문제를 우리가 아는 문제로 환원시키는 것이 정말로 중요한 능력 같다. 언제나 문제에 다가서는 것보다 우리 쪽으로 끌어오는 것이 더 쉬우므로.

 

우리는 우리의 영역을 넓혀야 하고, 끌어오기 위한 방법을 축적해야만 한다.