[CodingTest] 피보나치 수열

문제 : 피보나치 수열

제 1항부터 입력한 자연수(N)까지의 피보나치 수열 항들의 합을 구하여라.

F₀ = 0
F₁ = 1z
F_n+2 = F_n+1 + F_n

N	Fibonacci(N)	Answer
0	0	0
1	1	1
2	1	2
3	2	4
4	3	7
5	5	12
6	8	20
7	13	33
8	21	54
9	34	88
10	55	143

내 답안 : 메모제이션 적용

// Run by Node.js
​
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
​
​
rl.on("line", function(line) {
  if(line==1) return console.log(1)
  let memo = {0:0, 1:1, 2:1}
  
  function fibonacci(n) {
    if(n==0) return 0
    if(!memo[n]) memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]
  }
​
  function sum(obj) {
    return Object.keys(obj).reduce((sum,key)=>sum+obj[key]||0,0);
  }
  fibonacci(line)
  console.log(sum(memo))
  rl.close();
}).on("close", function() {
  process.exit();
});

더 좋은 방법

변수에 기억해두어서 공간 복잡도를 더 낮추는 방법.
피보나치 수열을 재귀법으로 작성하면 많은 노드들이 중복되어 호출된다.
예를 들어 Fibonacci(5)를 구한다고 했을 때, Fibonacci(3)은 두 번, Fibonacci(2)는 세 번이 호출된다.
이들이 호출될 때마다 다시 계산할 필요는 없다.
따라서 Fibonacci(N)를 캐시에 저장하고, 나중에 저장된 값을 사용하는 방식이 메모이제이션 방식이다.

// Run by Node.js
​
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
​
​
rl.on("line", function(line) {
  if(line==0) return console.log(0)
  if(line==1) return console.log(1)
  if(line==2) return console.log(2)
  let memo = {0:0, 1:1, 2:1}, before, after, answer=0
  for(let i=3;i<=line;i++){
    after += before
    before = after
    answer += after
  }
​
  rl.close();
}).on("close", function() {
  process.exit();
});

2023 1
2022 2
2019 45
2018 1

2023

Flutter 맛보기 1

3 분 소요

직방 기술지원팀 기술공유 세미나 중 플러터를 소개한 내용입니다

2022

D3.js 차트 개발 Hands on lab

5 분 소요

직방 기술지원팀 기술공유 세미나 중 D3.js를 소개한 내용입니다

직방이 사용자 행동 로그를 관리하는 방법. ZAMS

최대 1 분 소요

직방에서 작성했던 블로그 글을 공유합니다.

2019

[Tutorial] Storybook과 Bit을 활용한 UI 컴포넌트 관리(Workflow)

1 분 소요

회사에서 프론트엔드 개발원칙을 SFC(Single File Component)에서 UI 컴포넌트를 기준으로 CDD(Component Driven Development)를 진행하려고 한다. 그래서 체계적으로 관리하기위해 Storybook과 Bit을 도입해보고자 한다. 각각의 역할은 ...

[Scaffold] Scaffold Module 개발

최대 1 분 소요

도입 이유

[Workflow] 프론트엔드 개발조직을 위한 워크플로 설계

2 분 소요

작성 배경 회사의 작업구조를 페이지 중심 개발에서 UI 컴포넌트 중심 개발로 변경하면서 Workflow를 개선할만한 환경을 구성해야했다. 폐쇄망 기반에서 개발자간 UI 명세서 역할을 할 수 있는 Storybook과 그것을 공유할 Verdaccio라는 구축형 NPM Pri...

[Git] Git Command 정리

3 분 소요

Git 시스템 이해하기

[Design Pattern] Monorepo 공부

2 분 소요

결론

[Methodology] CDD(Component Driven Development) - 테스트(2/2)

1 분 소요

Intro

[Methodology] CDD(Component Driven Development) - 계획(1/2)

1 분 소요

CDD(Component Driven Development)란?

GraphQL, Prisma, Apollo 공부

2 분 소요

GraphQL? RESTful?

[CodingTest] Combination(조합) 문제풀이 2

최대 1 분 소요

문제

[CodingTest] Combination(조합) 문제풀이 1

최대 1 분 소요

문제

[ESlint & Prettier] 개발 관습 설정 in Visual Studio

1 분 소요

회사 프로젝트를 작업하기 전 프론트엔드 개발자들 간의 코드 규칙을 Eslint와 Prettier 설정을 맞춰 관리해가는 방향을 정했다. 아직 협업을 할 경우는 없지만 미래에 인수인계 받거나 협업을 진행할 경우 코드관습이 달라 고생할 경우를 대비하기로 했다. 설정은 작업을 진행하며 ...