파이썬과 익숙해질 겸, 비지니스 로직 속에 빠져있는 나에게 기본을 잊지말자란 채찍질을 할 겸 뭔가를 시작해보았다

보통 피보나치는 재귀로 구현하는데, n 이 조금만 커져도 시간이 어마어마하게 증가한다 f(n-2) + f(n-1)의 반복이니 기존 값을 저장해뒀다가 쓰면 되어 배열로 처리한다는 걸 생각해 볼 수 있을 것이다

먼저 코드를 보자

해답

배열​

def fibonacci(num):
    fibos = [0, 1]

    # 2 <= i < num + 1 까지 돌린다
    for i in range(2, num + 1):
        fibos.append(fibos[i-2] + fibos[i-1])

    # 마지막 데이터가 구하려는 데이터가 된다
    return fibos[num]

테스트해보면 재귀보다 엄청나게 빨라진 속도를 피부로 느낄 수 있다 뭐 여기까진 다들 생각해봤고 구현할 수 있을 것 같다

배열에 append하는 것 보다 미리 크기가 num만큼 정의된 배열에 i로 접근해 넣으면 더 빠른 속도가 날 것 같았다

하지만... python 엔 배열을 정해진 크기만큼 초기화할 방법이 없더라 [0] * num이라는 방법 뿐

배열을 안 쓰는 방법이 있을까? 한참을 고민하다가 다른 솔루션을 찾아봤다

재할당​

멋진 방법이 있었다

def fibonacci(num):
    a = 0
    b = 1

    # 0 <= i < num
    for i in range(num):
        temp = a
        a = b
        b += temp
    return a

a 엔 b 값을 주고, b 에는 기존의 a 값을 계속 더해준다 이 짓을 num - 1만큼 반복한다

배열을 안 쓰니 절반정도의 시간이 더 줄어들었다

공식​

이마저도 조금 아쉬움이 있었다, 피보나치는 수열이고 수열은 공식이 있기 마련이다 위키피디아엔 이미 그 공식이 있었다 수학의 힘을 빌려보자

from decimal import Decimal
# fibonacci의 85번 째부터 Double 값을 넘어가기에 Decimal 기능을 써야한다
sqrt5 = Decimal(5).sqrt()

def fibonacci(n):
    return ((1 + sqrt5) ** n - (1 - sqrt5) ** n) / (2 ** n * sqrt5)

20 만번 째도 0.2 초만에 구해진다

여담

• 피보나치의 데이터를 도식화하면 힙 모양이 되는데 아주 큰 값을 구하는 거라면 피보 힙이 제일 빠르지 않을까?
• 수학의 정석 심화편이 생각나는 건 왜일까?

연번 체크 알고리즘이라고도 하는 것 같다. 통계 또는 비밀번호의 연속성을 체크하기 위해 필요할 때가 있다. 비밀번호 연속성 체크에는 target[j]의 데이터를 charCodeAt 을 붙여 처리하면 된다.

소스

function checkSequenceNumbers(target, counterLength = 6) {
  // under es6
  // let sequentialCounter = Array.apply(null, Array(counterLength)).map(Number.prototype.valueOf,0);
  let sequentialCounter = new Array(counterLength).fill(0);
  let count = 0;

  for (let i = 0, len = target.length; i < len; i++) {
    let subCount = 0;

    for (let j = 1; j < len; j++) {
      if (target[j] === target[i] + 1) {
        subCount = subCount + 1;
      } else {
        continue;
      }
    }

    count = count + subCount;
    if (subCount === 0) {
      sequentialCounter[count] = sequentialCounter[count] + 1;
      count = 0;
    }
  }

  return sequentialCounter;
}

let target = [1, 2, 3, 5, 6, 7, 8, 10, 11, 13, 16, 17];
console.log(checkSequnceNumbers(target));
// => [1, 2, 1, 1, 0, 0]

설명

n 과 n+1... n+n-1 을 비교해서 카운트한다. 결과는 sequentialCounter 배열에 각 포지션에 들어간다.

2 연속 숫자 1 개가 있다면 sequentialCounter[2] = 1;

여담

왜 이런걸 공유를 안할까?