알고리즘 문제 풀기

피보나치 수

문제 설명

피보나치 수는 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) = 2 + 3 = 5
와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

n은 2 이상 100,000 이하인 자연수입니다.

풀이 코드

function solution(n) {
    var answer = 0;
    var f0 = 0;
    var f1 = 1;

    for( i = 2; i <= n; i++){
        answer = (f0 + f1) % 1234567
        f0 = f1;
        f1 = answer;
    }
    return answer;
}

풀이 과정

피보나치 수 answer를 구하기 위해 f0,f1을 더한 것을 1234567로 나누어 준다.
즉, 따라서 n번 피보나치 수는 해당 피보나치 수를 1234567로 나눈 나머지를 가지게 되며, 다음 피보나치 수를 구하기 위해 f0에는 f1을, f1에는 answer를 넣어준다. n번 반복한 뒤 answer를 반환한다.

게임서버개발 주특기 플러스

바이트 배열

8비트 단위의 데이터 배열
각 요소는 0부터 255 사이의 정수 값을 가짐.(1바이트)

• 바이트 배열이 16진수로 이루어진 이유? : 컴퓨터의 바이너리 데이터들은 보통 다 16진수로 저장됨.

용도

이진데이터, 예를 들어 이미지 ,동영상, 네트워크 패킷 등 표현에 사용.
효율적인 메모리 사용과 빠른 데이터 전송이 가능.

Buffer 객체

Node.js에서 이진 데이터를 다루기 위한 특별한 객체
JavaScript의 문자열은 UTF-16 형식으로 인코딩되어 있어 이진 데이터를 효율적으로 처리하는데 어려움이 있는데 Buffer객체는 원시적인 이진 데이터를 저장하고 조작하는데 최적화 되어있음.
※ UTF-16 : 유니코드 문자를 16비트(2바이트)단위로 인코딩하는 방식.

• JS 문자열이 이진 데이터 처리에 어려움을 겪는 이유? : 바이트 배열로 네트워크 패킷 교환을 함. -> 바이트 배열은 1바이트가 기준이 되고, JS의 문자열은 2바이트 단위로 저장되어있어서 다르기 때문에 처리하기가 어려움.

==> JavaScript안에서는 Buffer 객체가 바이트 배열이라고 생각하면 되고 바이트 배열이 Buffer 객체라고 생각하면 됨.
차이점 : Buffer 객체는 바이트 배열을 다루기 위한 특별한 객체이기 때문에 지원해주는 메서드들이 조금 있음.

• 장점 : 고정 길이 : 1바이트로 고정이 되어있다., 빠른 접근 : 바이트 배열에 빠르게 접근이 가능하다.

패킷 구조

기존 웹소켓 프로젝트 패킷 구조

필드 명	타입	설명
handlerID	int	요청을 처리할 서버 핸들러의 ID
userId	int	요청을 보내는 유저의 ID
clientVersion	string	현재 클라이언트 버전 (”1.0.0”) (고정)
payload	JSON	요청 내용

TCP Echo 서버의 패킷 구조

필드 명	타입	설명	크기
totalLength	int	메세지의 전체 길이	4 Byte
handlerId	int	요청을 처리할 서버 핸들러의 ID	2 Byte
message	string	메세지	가변

• 웹소켓 패킷 구조에서 크기가 추가됨.

<Buffer 00 00 00 11 00 0a 48 65 6c 6c 6f 2c 20 54 43 50 21>

버퍼 값이 위의 값이라면 패킷 구조에 따르면 00 00 00 11 까지가 totalLength, 00 0a 까지가 handlerId, 뒤의 나머지 부분이 message가 된다.

• 여기서 헤더의 길이는 총 6바이트 이며, 실제 사용되는 패킷은 바이트 배열의 7번째 ~ 끝까지 이다.