파도반 수열 알고리즘

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

파도반 수열(Padovan Sequence)의 정의

현재항의 값이 2, 3번째 이전의 항의 합으로 계산되는 수열.

여기서는 인덱스가 0이고 초기값인 {1, 1, 1}인 수열을 사용한다.

아래는 인덱스가 0이고 초기값이 {1, 0, 0}인 파도반 수열의 리스트이다.

{1, 1, 1} 으로 시작하는 부분부터 위 그림의 점화식을 따른다.

padovan_seq_upto200.txt

출처 : OEIS_A000931

파도반 수열 알고리즘 개요

파도반 수열과 피보나치 수열의 점화식은 매우 유사하다.

따라서 파도반 수열을 구하는 알고리즘도 피보나치와 고만고만하다.

Function Information

pado_recursion(n)	재귀를 이용하여 n번째 피보나치 수를 구한다.
pado_recursion_memoized(n)	메모이제이션이 적용된 재귀를 이용하여 n번째 피보나치 수를 구한다.
pado_iterative(n)	순회를 이용하여 n번째 피보나치 수를 구한다.
pado_iterative_queue(n)	원형 큐를 이용한 순회를 이용하여 n번째 피보나치 수를 구한다.
pado_bino(n)	빠른 곱셈 알고리즘이 적용된 행렬을 이용하여 n번째 피보나치 수를 구한다.
pado_pisano(mod)	mod로 나눴을 때의 피사노 주기를 구한다.

RunningTime Statistics (1,000,000회 평균값)

	10	30	60	90	Time	Memory
pado_recursion()	0.47 μs	235 μs	시간초과	시간초과	2^n	1
pado_recursion_memoized()	0.42 μs	1.52 μs	2.80 μs	4.20 μs	nearly n	n
pado_iterative()	0.09 μs	0.21 μs	0.27 μs	0.33 μs	n	n
pado_iterative_queue()	0.08 μs	0.20 μs	0.32 μs	0.40 μs	n	1
pado_bino()	0.21 μs	1.50 μs	4.58 μs	9.38 μs	nearly n	1

* 각 테스트케이스마다 캐싱된 값을 초기화하고 실행하였음.

1. 재귀

<핵심>

    1.  가장 직관적으로 점화식을 사용한다.

    2.  성능은 보장할 수 없다.

* 피보나치 재귀 설명으로 대체함.

각 단계의 Fib 함수가 2개씩 나눠지며 총 2^(5-1)개의 함수가 호출되었다.

같은 단계의 함수가 다시 호출했을 때, 중복된 계산이 발생하여 성능이 저하된다.

위의 트리에서 모든 Fib(2)가 매번 Fib(1), Fib(0)을 호출한것에 주목하자.

자신의 결과 값을 캐싱하고 있었다면(메모이제이션), 아랫단계의 함수를 호출할 필요가 없다.

2. 메모이제이션이 적용된 재귀

<핵심>

    1.  메모이제이션을 활용하여 중복된 계산이 발생하지 않도록 한다.

    2.  시간복잡도는 순회와 재귀 사이에 있다. (nearly n)

* 피보나치 메모이제이션 재귀 설명으로 대체함.

위는 메모이제이션이 적용되었을 때의 Fib(6)의 호출트리이다.

한번 실행되었던 단계가 다시 호출되었을 때, 단순히 캐싱값만 내어준다.

3. 순회

<핵심>

    1.  보통 순회를 이용하면, 재귀보다 직관적이지 못하다.

    2.  간단한 알고리즘에서는 재귀, 순회 둘 다 직관적이다.

    3.  왠만한 경우에서 재귀보다 훨씬 빠르게 동작한다.  (시간복잡도 n)

4. 원형큐를 이용한 순회

<핵심>

    1.  일반적인 순회는 메모리를 n 만큼 잡아먹는다, 원형큐를 사용하여 메모리 복잡도를 1로 줄이자.

    2.  원형큐의 인덱스를 계산하는데 오버헤드가 있다.

    3.  중간과정이 필요한 경우에는 적절하지 않다. (어차피 n만큼 캐싱해야 되기 때문.)

5. 이항계수

<핵심>

    1.  이항계수와의 관계를 이용한다.

    2.  이항계수 로직에서 오버플로우가 발생할 수 있다.

요점만 말하면 F(k)는 2n + r = k+2 를 만족하는 non-zero 이항계수(n, r)의 합이다.

피사노 주기

<핵심>

    1.  파도반 수열은 피보나치 수열의 한 종류이다. (제네릭하게 k-보나치 수열이라고 한다.)

    2.  k-보나치 수열을 mod n 했을 때, 반복되는 구간이 형성된다.

    3.  파도반에서 매 반복되는 구간의 첫 부분은 항상 {1, 1, 1} 이다.

    4.  주기가 찾아질 때 까지 메모리를 끝없이 잡아먹으므로, 원형큐 파도반을 이용한다.

* 피보나치 피사노 주기 설명으로 대체함.

파도반 린덴마이어 시스템 (Lindenmayer-System, L-System)

다음 규칙을 따르는 린덴마이어 시스템을 정의하자.

variables : A B C

constants : none

start : A

rules : (A → B), (B → C), (C → AB)

위의 L-시스템을 따르는 시퀀스는 아래와 같고,

n = 0 : A

n = 1 : B

n = 2 : C

n = 3 : AB

n = 4 : BC

n = 5 : CAB

n = 6 : ABBC

n = 7 : BCCAB

n = 8 : CABABBC

각 시퀀스의 문자열의 길이는 파도반 수열을 따른다.

    1 1 1 2 2 3 4 5 ...

조합 관점에서의 해석

파도반 수열은 조합의 관점에서 해석될 수 있다.

알고리즘 문제에서 많이 나오는 파트만 해석했다. (순서쌍 조합, 회문)

• P(n) 은 2, 3으로 n+2를 만들 수 있는 경우의 수이다.

P(6) = 4,  4가지 방법으로 8을 만들 수 있다.

2 + 2 + 2 + 2 ; 

2 + 3 + 3 ; 

3 + 2 + 3 ; 

3 + 3 + 2 ;

• P(n) 은 n을 만들 수 있는 회문 수열의 개수 이다.

P(6) = 4,  4가지 회문 수열로 6을 만들 수 있다.

6 ; 

3 + 3 ; 

1 + 4 + 1 ; 

1 + 1 + 1 + 1 + 1 + 1 ;

원문

• P(n) is the number of ways of writing n + 2 as an ordered sum in which each term is either 2 or 3 (i.e. the number of compositions of n + 2 in which each term is either 2 or 3). For example, P(6) = 4, and there are 4 ways to write 8 as an ordered sum of 2s and 3s:

• The number of ways of writing n as an ordered sum in which no term is 2 is P(2n − 2). For example, P(6) = 4, and there are 4 ways to write 4 as an ordered sum in which no term is 2:

4 ; 1 + 3 ; 3 + 1 ; 1 + 1 + 1 + 1

• The number of ways of writing n as a palindromic ordered sum in which no term is 2 is P(n). For example, P(6) = 4, and there are 4 ways to write 6 as a palindromic ordered sum in which no term is 2:

6 ; 3 + 3 ; 1 + 4 + 1 ; 1 + 1 + 1 + 1 + 1 + 1

• The number of ways of writing n as an ordered sum in which each term is odd and greater than 1 is equal to P(n − 5). For example, P(6) = 4, and there are 4 ways to write 11 as an ordered sum in which each term is odd and greater than 1:

11 ; 5 + 3 + 3 ; 3 + 5 + 3 ; 3 + 3 + 5

• The number of ways of writing n as an ordered sum in which each term is congruent to 2 mod 3 is equal to P(n − 4). For example, P(6) = 4, and there are 4 ways to write 10 as an ordered sum in which each term is congruent to 2 mod 3:

8 + 2 ; 2 + 8 ; 5 + 5 ; 2 + 2 + 2 + 2 + 2

출처 : 위키피디아

기하에서의 파도반

아래와 비슷한 기하의 규칙은 파도반 수열과 관련이 있다.

알고리즘 문제에서 숨어있는 규칙으로 많이 나온다.

<파도반 삼각형>

<파도반 나선>

<파도반 + 파스칼 삼각형>

파스칼 삼각형으로 표현할 수 있다면, 이항계수로도 표현될 수 있다.

파도반 수열과 이항계수의 관계는 이미 위의 파트에서 설명한 바 있다.