구상.md

용어

• 패턴: 요소 혹은 패턴이 일정한 규칙을 가지고 반복되는 것, 트리에서의 노드에 해당

• 최소의 패턴: 더이상 패턴으로 쪼개지지 않는 요소들을 가지는 패턴, 트리에서의 말단 노드에 해당

• 파라미터: 상위 패턴 혹은 현재 패턴의 바깥의 무언가에서 현재 패턴으로 넘겨지는 값

케이스 예측

케이스 예측은 정해진 규칙에 따르는 입력 - 출력의 케이스들이 주어진 경우 새로운 입력에 대한 출력을 예측하고 규칙을 코드화하는 것이다.

순열 예측

순열 예측은 주어진 순열에 대해서 다음 수를 예측할 수 있는, 순열을 일반화하는 것이다.

Process

그룹화 -> 패턴화 -> 코드 생성

그룹화

그룹화는 전체 순열을 하나의 패턴으로 분리하는 것을 말한다. 전체 순열이 최소한의 패턴 하나로 나타나지는 경우는 그룹화가 매우 쉬울 것이다.

최소한의 패턴 하나로 나타내지는 경우 예)

1, 2, 3, 4, 5, ... -> (1, 2, 3, 4, 5, ...)
9, 16, 25, 36, ... -> (9, 16, 25, 36, ...)

패턴을 패턴으로 가지는 경우 예)

1, 1, 2, 1, 2, 3, ... -> ((1), (1, 2), (1, 2, 3), ...)
이 전체 패턴은 n에 대해서 1..n 을 가지는 패턴들이 반복되는 패턴이다. 이 때 주어지는 파라미터는 1부터 시작하는 n의 값이다.

1, 10, 2, 11, 3, 12, ... -> (1, 2, 3, ...), (10, 11, 12, ...)
이 전체 패턴은 두개의 순열이 번갈아가면서 나오는 패턴이다.

(하나의 패턴은 하나의 순열이라고 보면 더욱 이해하기 쉽다. 순열에서 반복되는 순열은 끝이 있는 또다른 순열이다.)

패턴화

패턴화는 전체 순열을 패턴의 트리로 구축하는 것을 말한다. 구축된 트리의 모습은 파스 트리와 매우 유사하다.

최소한의 패턴이 트리로 구축된 모습 예)

1, 2, 3, 4, 5, ...

(패턴 i <- [1, ...])
↓
수 i

9, 16, 25, 36, ...

(패턴 i <- [1, ...])
↓
수 (i + 2) ^ 2

최적화시:
(패턴 i <- [3, ...])
↓
수 i ^ 2

패턴을 가지는 패턴이 트리로 구축된 모습 예)

1, 1, 2, 1, 2, 3, ...

(패턴 i <- [1, ...])
↓
(패턴 j <- [1, ..., j]>)
↓
수 j

코드 생성

패턴이 구축한 트리를 이용하여 코드를 생성하고 순열의 규칙을 설명한다.

개선

순열 예측은 주어진 실마리가 없으니 바텀업으로 일일히 비교해보는거 밖에 없을 것 같다. 하지만 케이스 예측은 실마리가 주어졌으니 탑다운으로 내려가도 괜찮을 것 같다.