타입챌린지 : 4182-Fibonacci Sequence (medium)

이 글은 제가 타입챌린지를 하면서 해석한 내용을 적는 글입니다. 틀린 내용이 있으면 댓글 달아주시면 감사하겠습니다.

 

https://github.com/type-challenges/type-challenges/blob/main/questions/04182-medium-fibonacci-sequence/README.md

 

 

타입으로 피보나치 수열을 구현하는 문제이다.

나는 MinusOne타입과 Plus타입을 이용해서 구현했지만...

depth가 너무 깊어진다고 에러가 났다...

type Push<T extends any[], U> = T extends [infer F, ...infer O] ? [F, ...O,  U] : [U];

type NumberToArray<T extends number, U extends any[] = []> = U['length'] extends T ?
  U : NumberToArray<T, Push<U, 0>>

type MinusOne<T extends number> = NumberToArray<T> extends [infer F, ...infer O] ? O['length'] : never;

type Plus<T extends number, U extends number> = [...NumberToArray<T>, ...NumberToArray<U>]['length']

type Fibonacci<T extends number> = T extends 1
  ? 1
  : T extends 2
    ? 1
    : Plus<Fibonacci<MinusOne<MinusOne<T>>>, Fibonacci<MinusOne<T>>>

 

MinusOne타입에 대해서는 다음 포스팅을 참고하자.

https://suloth.tistory.com/86

타입챌린지 : 2257-MinusOne (medium)

 

말을 하지 않아도 위의 타입에 대해서는 알거라고 생각한다.

 

그러면 이제 다른 분들의 답을 봐보자.

type Fibonacci<T, K extends any[] = [1], P extends any[] = [], C extends any[] = [1]>
  = K['length'] extends T 
      ? C['length']
      : Fibonacci<T, [...K, 1], C, [...P, ...C]>;

K는 재귀를 돌 때, 현재 재귀횟수 (반복 횟수)를 판단하기 위해 있고,

C는 재귀를 하면서 현재까지 쌓인 배열을 말한다.

P는 현재 바로 전의 배열을 가져오는 것 같다.

 

K['length'] extends T ? C['length'] : K의 길이가 T가 된다면 C의 길이를 리턴한다. 여기에서 K가 T를 위한 재귀 횟수 판단을 위한 제네릭임을 알 수 있다.

Fibonacci<T, [...K, 1], C, [...P, ...C]> : [...K, 1]로 재귀를 하면서 현재 재귀 횟수를 파악하고, C를 P자리에 대입함으로써 현재 배열을 다음 재귀로 넘겨준다. 그리고 [...P, ...C]를 넘김으로써 이때까지의 배열을 넘겨준다. 그리고 최종적으로 K의 길이와 T가 같아진다면, C의 길이가 곧 피보나치 수열의 답이 된다.

 

엄... 조금 어렵게 설명했는데 이 이상 어떻게 설명을 해야할 지 모르겠다... 그냥 간단히 말하면 C에는 항상 1이라는 원소가 담기고, 이 원소의 개수를 재귀를 탈 때마다 더해주면서 배열을 만들어간다고 보면 될 것같다.