jiho_bae
Go devlog
jiho_bae
전체 방문자
오늘
어제
  • 분류 전체보기 (158)
    • JavaScript (38)
      • theory (34)
      • vanilla (4)
    • HTML & CSS (2)
    • Browser (3)
    • CS (6)
      • linux (1)
      • shell (2)
      • compiler (2)
    • DS & Algorithm (87)
      • theory (5)
      • basic (7)
      • programmers (30)
      • baekjoon (45)
    • Design Pattern (2)
    • Error (4)
    • Git & Github (4)
    • Tools (1)
    • 부트캠프 (4)
    • Small Tips (2)
    • Java (3)
    • test (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 가사 검색 자바스크립트
  • 외벽 점검 javascript
  • 자바스크립트 sort는 왜 그모양일까
  • 덧칠하기 javascript
  • 카카오 코딩테스트 양궁대회 nodeJS
  • safari invalid date error
  • 계수정렬 자바스크립트
  • 자바스크립트 모듈 시스템
  • fetch 취소하기
  • 대충만든자판 javascript
  • 자바스크립트 배열의 특수함
  • 13460 javascript nodejs
  • 리코쳇 로봇 javascript
  • 25632 소수 부르기 게임
  • 프로그래머스 숫자카드나누기 javascript
  • 자바스크립트 이벤트 위임
  • 병합정렬 자바스크립트
  • safari Date format NaN
  • 리액트 프로젝트 디버깅하기
  • javascript use strict
  • 퀵정렬 자바스크립트
  • 자바스크립트 비동기 마이크로 태스크 큐와 렌더링 과정
  • 자바스크립트 커링
  • 1753 최단경로 javascript
  • JavaScript
  • 자바스크립트 채팅방 스크롤
  • 깃 이전 커밋에서 새 브랜치 만들기
  • 백준 자바스크립트 입력 템플릿
  • 억억단을 외우자 javascript
  • 백준 17406 nodeJS

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
jiho_bae

Go devlog

DS & Algorithm/programmers

[프로그래머스] 피보나치 수 - 자바스크립트

2021. 6. 19. 23:23

문제

 

코딩테스트 연습 - 피보나치 수

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) =

programmers.co.kr

 

풀이

간단한 문제지만 문제 조건을 유의해야 한다.

 

n번째 피보나치 수를 1234567으로 나눈 나머지를 구하는 문제이다.

 

주어진 수 n은 1 <= n <= 100000 의 범위를 가진다.

 

이 문제를 재귀함수로 풀려고 하면
n의 값이 100,000일 때 Maximum call stack size exceeded 에러가 발생한다.

말 그대로 너무 재귀가 많이 호출되어 콜스택의 크기를 초과했다는 것.

 

재귀가 아닌 단순 반복문으로 10만번 정도는 거뜬하다.

반복문을 사용하자.

 

K번째 피보나치 수는 1234567로 나눈 나머지 값을 저장해준다.

주어진 수 N번째 피보나치 수만 1234567로 나눈 나머지 값을 구하는 것이 아니라, 매 스텝마다 나눈 나머지를 값으로 삼아야 한다.
=> 1000번째 피보나치 수만 해도 4.346655768693743e+208으로 매우 큰 값이다.

 

이를 바탕으로 코드를 작성해보자.

 

코드

function solution(n) {
  if (n < 2) return n;
  const fibo = { 0: 0, 1: 1 };
  for (let i = 2; i <= n; i++) fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1234567;
  return fibo[n];
}

조건을 잘 이해하면 간단한 코드로 해결할 수 있다.

저작자표시 (새창열림)

'DS & Algorithm > programmers' 카테고리의 다른 글

[프로그래머스] 영어 끝말잇기 - 자바스크립트  (0) 2021.06.27
[프로그래머스] 파일명 정렬 - 자바스크립트  (0) 2021.06.24
[프로그래머스] 튜플 - 자바스크립트  (0) 2021.06.19
[프로그래머스] 오픈 채팅방 - 자바스크립트  (0) 2021.06.19
[프로그래머스] 소수 찾기 - 자바스크립트  (0) 2021.06.18
    'DS & Algorithm/programmers' 카테고리의 다른 글
    • [프로그래머스] 영어 끝말잇기 - 자바스크립트
    • [프로그래머스] 파일명 정렬 - 자바스크립트
    • [프로그래머스] 튜플 - 자바스크립트
    • [프로그래머스] 오픈 채팅방 - 자바스크립트
    jiho_bae
    jiho_bae
    하루에 한 걸음씩

    티스토리툴바