함수 복원

• 미지의 함수에 대해서 주어진 인풋과 아웃풋의 쌍들로부터, 함수를 복원하는 문제.
• 만들기도 쉽고, 푸는 사람 입장에서도 별도의 배경지식이 필요하지 않아서, 아이큐 테스트, 미궁, 방탈출 등등 여기저기에서 흔히 쓰인다.
• 그러나 그러다 보니 퀄리티가 떨어지는 문제도 많다.

위에서 예시로 든 두 문제는 이러한 문제의 전형적인 형태이다. 이러한 문제에서 대부분의 경우 연산자는 원래 의미대로 쓰이지 않으니 무시하고 보면

왼쪽 문제는

f(1,4)=5
f(2,5)=12
f(3,6)=21
f(8,11)=??

오른쪽 문제는

f(3,4,2)=5
f(6,4,2)=8
f(5,1,3)=3
f(7,3,9)=??

와 같이, 결국 같은 형태이다.

사실 이 문제의 가장 큰 단점은, 가능한 f가 무수히 많다는 점에 있다. f의 형태에 제약이 존재하지 않는 한, 저 식을 성립시키는 f는 무수히 많아진다. 간단하게 생각해서 f(ai)=bi (i=1..n) 의 형태로 문제가 주어진다면, 식을 성립시키는 n차 다항식형태의 f를 쉽게 찾아낼 수 있다.

따라서 f의 형태에는 암묵적인 제한이 있다고 가정해야 한다. (만약 제한된 함수의 집합안에서, 식을 성립시키는 것이 아니라 오차를 최소화 시키는 함수를 찾는 것을 목적으로 한다면, 이것은 흔히 공부하는 회귀분석 문제가 된다.)

• 함수 안에 임의의 상수값은 포함되지 않는다.
  • 1,2,10 과 같은 자명한 값은 허용해 준다.
• 연산은 사칙연산, 지수연산, 나머지연산 정도만 사용 가능하다.
• 연산 횟수가 너무 길어지면 안된다. (너무라는 표현은 모호한데, 이것이 길어질수록 못 만든 문제라는 욕을 먹게 된다)

또한 제대로 된 문제는, 이러한 제한 안에서 찾아지는 f가 유일하게 나오도록 해야 한다.

Number Tree by Nob