개발 블로그

#1.6 Chat Completed

html 로 메세지를 전송하는 버튼과, 메세지 리스트를 보여줄 수 있는 화면을 작성해보자.

line 13 ~ 16 을 추가해준다.

html에서 작성한 ul, form 을 브라우저 쪽에서 변수로 선언해주고,

from 에 대한 변수인 messageForm에 eventListener 를 add 해준다. 

즉 submit 이벤트가 발생했을 때  line 17~21 메소드를 실행한다.

* preventDefault() : submit 되었을 때 defulat 동작은 초기 화면으로 돌아오는 것인데, 해당 함수를 통해 그 default 동작을 막는다. 즉 submit 이 되어도 그 화면을 그대로 유지할 수 있도록 해준다. 

 다음 서버를 실행하고 브라우저에 hello 를 입력하면 정상 실행됨을 확인할 수 있다. 

이제 input.value를 console.log 로 출력하는 대신, socket.send 를 사용해서 

front->back 으로 입력 값을 전송해보자. 

또한 input.value 값을 초기화해줌으로써 submit 후에 입력 창에 문자가 남아있지 않도록 해준다. 

서버 재실행 후 브라우저에서 숫자를 입력해보면 backend 에서 그 값을 확인할 수 있다. 

backend 가 받은 메세지를 그대로 다시 front 로 전송해보자.

line 32를 line 33으로 수정해주면 

아래와 같이 브라우저에서 hi 라고 입력 후 send 버튼을 누르는 즉시 back->front 로 그 메세지를 다시 전송하여 콘솔 창에서 그 메세지를 확인할 수 있다. 

그러나 이 기능은 메세지를 입력한 그 브라우저와 서버 간에 통신을 하는 것이다. 즉 크롬 브라우저와 사파리 브라우저간의 통신이 되지 않느다. 이를 확인하기 위해 사파리에 동일한 주소로 접속을 한 뒤 메세지를 입력하면 이는 사파리에서만 확인 가능하지 크롬에서는 확인이 불가하다.

이제 chrome <-> server <-> safari 구조로 chrome ~ safari 사이에 통신할 수 있도록 해보자. 

현재 socket 에 누가 연결이 되었는지 모르므로 fake database를 생성해주자. 

앞으로 누군가 서버와 connection이 되면, 그 연결 정보인 socket 을 sockets 배열에 넣어줄 것이다. 

line 27, 30을 통해서 하나의 socket(브라우저)을 통해 받은 메세지를 다른 socket(브라우저들)들에 전송할 수 있다. 

현재 코드로는 자신의 브라우저에도 메세지를 보내는 방식이지만 추후 이 방식은 개선하도록 한다. 

line 38과 같이 연결된 모든 브라우저에 socket 을 통해 메세지를 보내주는 기능을 추가한 뒤 

크롬에서 메세지를 send 하면 safari 에서도 그 메세지가 출력됨을 볼 수 있다. 

반대로 safari 에서 입력해도 동일하게 chrome 에 출력된다.

#1.4 WebSockets Messages

앞서 server.js 에서 handleConnection 이라는 함수를 따로 정의했었는데,

on 함수의 두번째 인자 내에 바로 함수를 생성해보자. (line 26~28)

이 방식으로 하면 line 23~25 방식에 비해, socket이 현재 어떤 상태인지 알기 쉽다. 즉, 연결이 되면 socket이 인자에 들어온다는 것을 직관적으로 이해할 수 있다. 

이제 console.log 대신 "welcome to chat" 이라는 메세지를 보내보자. 

send 메소드는 server의 메소드가 아닌 socket 의 메소드이며, 이는 socket 과의 직접적인 연결을 제공해준다.

backend 에서 메세지를 보냈으니, 이를 Frontend에서 받아보자. 가능한 옵션은 네가지가 있고 이 중 open을 입력하자. open은 connection 이 opne 되었을 때를 의미한다.

backend 쪽도 로그를 추가해주자. 

다음으로 socket에 이벤트 두개를 추가해보자. message와 close 이벤트를 추가한 코드이다. 

message이벤트는 메세지를 받을때마다 아래 내용을 출력한다. 

서버에도 브라우저와 잘 연결되었다는 메세지가 출력된 모습이다. 

브라우저 쪽도 잘 작동한다.

이 중에 직접 받은 data 만 받고 싶다면 위 사진의 line 8 중 message 파라미터를 message.data 로 바꿔보자. 

data 만 출력한 모습이다. 

이 상태에서 서버 터미널에 ^C를 입력하여 서버를 kill 하면, 브라우저에서는 서버 연결이 끊겼다는 메세지가 발생한다. 

동일하게 서버에서도 close event에 대한 Listener 를 등록해보자. (socket.on () )

브라우저에서 연결을 끊기 위해 크롬 창을 닫으면,  아래와 같이 터미널창에 브라우저로부터 연결이 끊겼다는 메세지가 출력된다. 

서버와 브라우저 간 양방향 통신에 대해 알아봤고,

이제 frontend -> backend 로 메세지를 보내보자. (위에서는 backend -> frontend 만 했음)

보내기 전에 10초를 기다리기 위해 timeout 을 설정하자. 

timeout을 설정함으로써 메세지를 순차적으로 보낼 수 있다. 

브라우저가 보낸 메세지를 backend 에서 받기 위해 eventListener를 작성해보자. (line 31~33)

이제 서버를 재실행하면,

1. back -> front : hello! 메세지를 보냄. ( 위 사진의 Line 34)

2. front -> back : front에서 10초 후 메세지를 보내면 backend 터미널에 hello from the server 라는 메세지 출력됨.

그러나 아래와 같은 에러가 떠서

강의 아래 있는 코멘트를 보고 수정한 뒤 재실행 하니

정상적으로 출력된것을 확인할 수 있었다.

* 메세지를 받을 때, frontend 에서는 addEventListener() 메소드로 받고, backend 에서는 socket.on() 메소드로 받는다. 

#1.3 WebSockets Events

이제 ws를 사용해서 backend 와 frontend 사이에 connection을 만들어보자. 

frontend 에서 websocket을 이용하여 backend 와 연결하는 것은 -> JS 에서 지원한다. 

websocket은 위의 버튼리스너가 동작하는 방식과 비슷하다.

즉 Event가 있고, 그 Event가 실행될 때 사용할 Function을 정하면 된다. 

(* 추가 상세 이론은 무료 vanilla JS 강의 참고) 

websocket은 listen 할 특정 event 명이 있으며, 추가적인 정보를 받기 위한 function 도 있디.

Event는 어떤 것들이 있을까?

-> click, submit, Wi-Fi on/off 등이 있다.

on() 함수의 첫번째 인자는 event, 두번째 인자는 function 이다. 이 function은 첫번째 인자인 event 가 발생할 때 호출된다. 

여기서 cb(call back)으로 socket을 받는다고 나와있다. socket은 연결된 어떤 사람을 말한다. 연결된 브라우저의와 contact line을 말하며, 이 socket 인자를 변수에 저장해놔야한다. 그래야 Function의 인자에 넣을 수 있다. 

아래는 event 들의 종류이다. connection를 입력한다. 

그 후 function을 생성한다. 이름은 handleConnection.(line 23~25)

connection 이벤트가 발생하면 handleConnection함수는 인자를 통해

backend에 연결된 사람의 정보를 socket을 통해 frontend로 받아온다. 이 방법은 vanilla JS를 사용할 때의 방법입. 

이제 frontend에서 backend와 연결하는 부분을 작성해보자.

참고 : https://developer.mozilla.org/en-US/docs/Web/API/WebSocket/WebSocket#syntax

아래와 같이 frontend 에 작성 후 

console에서 새로고침을 해보면, 아래와 같이 http 프로토콜을 사용해서 에러가 났음을 확인할 수 있다. 

http를 ws로 변경하자. 

그리고 모바일에서 사용 시 localhost:3000으로 접속할 수 없으니 이 부분도 수정을 해보자.

브라우저에서 위 정보를 스스로 가져오게 해보자. 

콘솔창에서 window.location.host 를 입력하면 'localhost:3000'과 같이 뜨는 것을 확인할 수 있다. 

frontend 코드상에서도 아래와 같이 수정한 뒤 저장하고 refresh를 해보면 

WebSocket connection to 'ws://%24%7Bwindow.location.host%7D/' failed: 

와 같은 오류가 뜨는데 이는 따옴표(')를 -> 백틱(` - 물결 아래에 있으며 한글일 때는 ₩로 타이핑되므로 영문으로 전환 후 입력하면 된다)을 쓰면 해결된다. 

여기까지 websocket을 이용해 frontend와 backend 간 connection을 만들어보았다.

이제 real-time 으로 메세지를 주고 받아보자. 

#1.0 Introduction

실시간 채팅 어플을 만들어보자.  

#1.1 HTTP vs WebSockets 

http와 websocket 은 둘 다 프로토콜이다.  

아래 코드는 http의 request, response 방식이다. 즉 ,유저가 "/"(home)으로 Get Request 를 보내면 , 

template 으로 respond 한다. 인터넷은 기본적으로 이와 같이 http 방식이다. 

그러나 http의 특징은 stateless이다. 즉, req/res 후에 backend 는 유저를 잊는다. req를 주면 그저 res를 기다릴 뿐. 

그래서 authenticate 를 하려면 서버에 cookie를 보내줘야한다. 예를 들어 프로필 페이지에 들어가려면 내가 누구인지 알려주는 cookie를 서버로 보내고, 서버는 일치하는 프로필 페이지를 respond 해준다. 

Get request, Post Request 모두 Req/Res 방식이며, 이 과정은 Real time 으로  발생하지 않는다. 

WebSocket : 실시간 채팅/notification 기능 활용 가능

Websocket은 처음에 악수를 한다. (WebSocket request-> accept) accept하면 coonection이 성립된 것이며, 연결이 되었기 때문에 서버는 유저를 기억한다. 그래서 원한다면 서버가 먼저 유저에게 메세지를 보낼 수 있으며, 둘 사이에는 양방향 통신이기 때문에 서로 언제든지 메세지를 보낼 수 있다.(ex. Wifi, 전화통화) 

이후 자바스크립트용으로 구현된 websocket과 브라우저에 내장된 websocket api를 사용할 것이다. 

websocket 은 브라우저-backend 뿐 아니라 backend-backend 간에도 동작한다. (http도 동일)

#1.2 WebSockets in NodeJS

node.js로 websocket 서버를 만들어보자. (ws라는 package 활용)

ws는 websocket 을 사용하기 위한 기본. 다양한 기능 사용을 위해서는 framework를 추가로 사용해야한다. 

https://www.npmjs.com/package/ws

먼저 npm i ws로 모듈을 설치한다. 

이제 서버를 만들 것이다. ws 서버를 새로 만드는 것이 아니라 express 서버(http) 와 합친다. 

=> http + websocket 

express 는 websocekt 을 지원하지 않기 때문에 function을 새로 추가해야 한다.

이제 http server, Websocket server 를 만들어보자. => localhost:3000은 이 두 서버를 모두 사용할 수 있다. 즉, 동일한 포트 3000번에서 http, ws request 두개를 다 처리할 수 있다. 

[http]

line 1 : http package는 모든 Node.js 에 내장되어 있으므로 line 1 과 같이 import 만 해주면 설치없이 사용할 수 있다. 

line 18 : 서버 생성한 부분이다. 

[websocket]

line2 : websocket import

line 21 : 생성한 http 서버(const server) 위에 websocket 서버를 생성하였다. 

이제 위의 line 22와 같이 만든 서버를 listen 해보면 정상적으로 실행되는 것을 볼 수 있다.

전과 차이는 없지만, 생성한 http 서버의 위에 ws 서버를 생성한 것이다. (같은 포트 3000번 공유)

출처 : https://nomadcoders.co/noom/lectures/3111

#0.1 Requirements 

[BackEnd]

• ExpressJS
• app.get()
• Pug
• (req, res) => 
• package.json
• babel
• nodemon

[FrontEnd]

• 바닐라JS (바닐라JS로 크롬 앱 만들기 참고)  
  •   document.querySelector, document.createElement, title.innerText=""
  •  js로 HTML에서 요소를 가져오거나 생성하는 방법
  • 클래스명 추가/삭제 방법 (ex  .classList.add() )

[NodeJS]

• ver 4.17.3 이상

#0.2 Server Setup

package.json 만들기

Babel, Nodemon 설정하기

npm이란?

Node.js Package Manager의 약자

노드 프로젝트를 시작할 때

$npm init

으로 시작한다. 

터미널에서 바로 vscode 실행하는 방법

vscode 에서 shift+cmd+p 누르고 code 검색 후 설치 

터미널에서 code . 명령어 실행

여기서 main, scripts 부분 삭제

상단의 Terminal 탭에서 New Terminal 클릭하여 터미널 창 신규 생성

touch README.md 명령어 실행하여 github 용 README 추가

https://server-talk.tistory.com/392

Nodemon 설치하기

npm i nodemon -D 

babel 파일 생성, nodemon.js 파일 생성, src 폴더 생성

Babel 설치

먼저 git init. 실행 후 babel 설치

git init .

npm i @babel/core @babel/cli @babel/node -D

touch .gitignore 

추가로 preset 설치

npm i @babel/preset-env -D

후 babel.config.json 파일에 아래와 같이 입력

npm i express

npm i pub

import express from "express";

localhost:3000 접속 후 확인 

#0.3 Frontend Setup

static file과 User 에게 가게 될 파일 만드는 단계

WebPack을 사용하지 않고 단순히 JavaScript를 User에게 전송할 것 

먼저 아래와 같이 public, js 폴더 생성 후 그 안에 app.js 파일을 생성한다. 

public 안에 veiws 폴더 생성 및 home.pug 파일을 생성한다.

일반적인 html 작업을 위해 html 5를 선택한다. 

 pug 페이지들을 렌더하기 위해 server.js 파일에 pug 설정을 해준다. (line 5,6)

line 6은 views 경로를 설정해준 것이다. 

이제 npm run dev 로 실행시켜 보자.

이제 Route 를 생성할 차례이다. ( 한 개만 사용함)

여기서 Express 로 하는 것은 view 를 셋팅하는 것과, render 를 하는 것이며,

나머지는 websocket 에서 실시간으로 일어난다. 

오류가 나서 views 디렉토리 경로를 line 7과 같이 수정한다. 정상동작됨을 확인하였다.

다음은 home 에 script 를 작성한다.

이 상태에서 line 10의 url로 이동하면 동작하지 않는다. url 동작을 위해서는 static 작업이 필요하다.

line 8은 static 작업을 한 내용이다. user가 public 으로 이동하면 __dirname+/public 폴더를 보여주는 것이다. 

그 후 User가 보는 FrontEnd 에 해당하는 app.js 파일에 hello; 를 입력한 뒤 서버를 재시작하면 다음과 같이 확인할 수 있다.

app.js 를 저장할 때마다 nodemon이 새로 시작된다. 이는 비효율적이므로 views 나 server 를 수정할 때만 ㅜodemon이 재시작되도록 해보자. 아래와 같이 nodemon.json 파일에서 해당 파일을 ignore 하면 된다.

* nodemon은 우리의 프로젝트에서 변경 사항이 발생하면 서버를 재시작해주는 프로그램. 

서버를 재시작하는 대신에 babel node 를 실행한다.("exec": )

Babel은 우리가 작성한 코드를 일반 NodeJS 코드로 컴파일해주는 역할이며, 그 작업을 src/server.js 에다가 해주는 것이다. 

정리하면,

Pug로 view engine을 설정하고, Express에 template이 어디있는지 설명해주고 (line 6,7)

puglic url 을 생성하여 유저에게 파일(public 폴더)을 공유해주고 (보안적인 측면에서 유저가 모든 부분을 볼 수 없도록 제한) (line 8)

home.pug를 render 해주는 route handler 를 만듦. (line 9)

이제 mvp css 를 사용해서 추가로 html tag 를 더 예쁘게 꾸며보자. 

아래의 href 링크를 복사해서 

header에 추가하자.

line 8 : 기존의 link:css 에서 href 를 위 mvp css 걸로 수정한다.

왼쪽이 mvp css 적용 전, 오른쪽이 적용 후 이다. 

마지막으로 javascript가 잘 연결됐는지 확인해보자.

위의 javascript는 제대로 frontend 로 가고 있는 것이다. 

#0.4 Recap

Line 10 과 같이 CatchAll Url 만들어보자. 유저가 아무 url 로 이동하려고 시도해도 home 디렉토리로 리다이렉트 시킨다. 

제 1장. 데이터 모델링의 이해

1번. 모델링의 특징

1) 추상화 : 현실세계를 일정한 형식에 맞춰 표현

2) 사전 작업 : 시스템 구현, 업무분석, 업무 형상화를 목적으로 하는 사전 단계의 작업

3) 단순화 : 복잡한 현실을 제한된 언어나 표기법을 통해 이해 쉽게

4) 정확화 : 누구나 이해 가능하게 정확히 현상 기술

2번. 데이터 모델링 필요 이유

- 데이터 모델링 : 업무 정보를 구성하는 기초 정보들을 일정한 표기법에 의해 표현

- 필요 이유 1 : 분석된 모델로 디비 생성해서 개발 or 데이터 관리에 사용하기 위함

- 필요 이유 2 : 데이터 모델링을 통해 그 자체로서 업무의 흐름을 설명/분석하는데에 도움

3번/4번. 데이터 모델링 중 유의 사항

- 중복 : 여러 디비에 같은 정보 저장하지 않도록 해야함

- 비유연성 : 데이터 정의와 사용 프로세스를 분리해야함 --> 작은 변화가 애플리케이션 or 디비에 큰 영향 줄 수 없도록

- 비일관성 : 서로 연관된 데이터 중 하나만 업데이트 할 때 발생 --> 데이터 간의 연관 관계에 대해 명확한 정의 필요

5번. 데이터 모델링 종류

- 개념적 모델링 : 전사적 데이터 모델링 수행 시 많이 함. 추상화 수준 높음. 업무 중심적. 포괄적 수준의 모델링

- 물리적 모델링 : 실제로 디비에 이식 할 수 있도록 성능/저장 등의 물리적 성격을 고려한 모델링

6번. 데이터 베이스  스키마 구조 3단계

- 외부 스키마 : 실세계의 데이터를 어떤 구조로 사용자에게 보여줄 것인지 논리적 구조를 정의.

- 개념 스키마 : 모든 사용자 통합 관점의 스키마. 모든 응용시스템이나 사용자들이 필요로하는 데이터 통합.

- 내부 스키마 : 물리적인 저장장치 중심으로, 어떻게 디비를 저장할건지 물리적 저장 구조를 정의.

7번.

8번. ERD

- 1976년 피터첸이 Entity Relationship Model 개발

- 작성 방법 : 엔티티 도출(그리기) -> 엔티티 배치 -> 관계 설정 -> 관계명 기술 -> 관계 참여도 기술 -> 관계 필수여부 기술

- 관계 명칭은 관계 표현에 있어서 매우 중요

9번. 

10번/11번. 엔티티 특징

- 유일한 식별자에 의해 식별 가능해야함

- 두 개 이상(영속적으로 존재)의 인스턴스 집합  

- 업무 프로세스에 의해 이용되어야 함 ( 데이터가 있지만 업무에서 필요하지 않으면 해당 업무의 엔티티 성립 X)

- 반드시 속성이 있어야 함

- 다른 엔티티와 최소 한 개 이상의 관계 있어야 함 (통계성, 코드성 엔티티는 관계 생략 가능)

12번. 엔터티 분류

[유무형에 따른 분류] 

- 유형 : 물리적 형태 (사원, 물품, 강사)

- 개념 ; 개념적 정보 (조직, 보험 상품)

- 사건 : 업무 수행시 발생 (주문, 청구, 미납)

[발생 시점에 따른 분류]

- 기본(키) 엔터티 : 원래 존재하는 정보. 다른 엔터티와의 관계에 이해 생성되지 않고 독립적으로 생성 가능. 자신은 타 엔터티의 부모 역할함. 다른 엔터티로부터 주식별자를 상속받지 않고 고유한 주식별자 가짐. (사원,부서,고객,상품)

- 중심 : 기본 엔터티로부터 발생. 다른 엔터티와의 관계로 많은 행위 엔터티 생성 (계약, 사고, 주문)

- 행위 : 2개 이상의 부모 엔터티로부터 발생. 자주 바뀌거나 양이 증가함 (주문 목록, 사원 변경 이력)

13번. 엔터티 명명 기준

- 현업에서 사용하는 용어

- 가능하면 약어 사용 X

- 단수명사 사용

- 모든 엔터티 중 유일한 이름으로 

- 엔터티 생성 의미대로 이름 부여

14번. 속성이란

속성이란 : 업무에서 필요로 하는 인스턴스에서, 관리하고자 하는, 의미상 더 이상 분리되지 않는 최소의 데이터 단위

15번. 속성에 대한 설명

- 엔터티에 대한 자세한 정보임

- 하나의 엔터티는 두 개 이상의 속성 가짐

- 하나의 인스턴스에서 각 속성은 한개의 속성값을 가짐

- 한개의 엔터티는 두 개 이상의 인스턴스의 집합이어야 함

16번/17번. 속성 분류

- 기본 : 업무로부터 추출한 모든 일반적인 속성

- 설계 : 업무를 규칙화하기 위해 새로 만들거나 변형한 속성 (일련 번호)

- 파생 : 다른 속성의 영향을 받아 발생하는 속성. 빠른 성능 낼 수 있게 원래 속성 값을 계산, 적을 수록 좋음 (합, 이자)

18번. 도메인

도메인이란? : 속성에 대한 데이터 타입, 크기, 제약사항 지정 --> 각 테이블 속성에 어떤 유형의 값이 들어가는지 정의하는 개념

19번. 속성 명칭 부여 주의 사항

- 해당 업무에서 사용하는 이름 부여

- 서술식 속성명 X

- 약어 사용 지양

- 유일성 확보

20번. 데이터 모델링 관계에 대한 설명

- ERD에서 : 존재적 관계와 행위에 의한 관계 구분 표기법 없음 (단일화된 표기)

- 클래스다이어그램에서 : UML에서는 이것을 연관관계와 의존관계로 표현하며. 다르게 표기됨 (연관은 실선, 의존은 점선)

21번/22번. 관계에 대한 설명

- 구분 : 존재적 관계, 행위에 의한 관계

- 관계 표기법 : 관계명, 관계차수(1:M), 관계선택성(필수or선택)

- 소속 관계 : 존재적 관계 (부서 - 사원)

23번/24번. 엔터티 사이의 관계 체크 사항

- 두 개의 엔터티 사이에 관심 있는 연관 규칙 존재?

- 두 개의 엔터티 사이에 정보의 조합 발생?

- 업무기술서, 장표에 관계 열결을 가능케 하는 '동사' 존재?

- 업무기술서, 장표에 대한 규칙 서술됨?

25번. 주식별자 지정 시 고려할 사항

- 주식별자에 의해 엔터티 내의 모든 인스턴스들이 유일하게 구분되어야 함

- 주식별자를 구성하는 속성의 수는 유일성을 만족하는 최소의 수가 되어야 함

- 지정된 주식별자의 값은 자주 변하지 않는 것이어야 함

- 주식별자가 지정되면 반드시 값이 들어와야 함

26번. 식별자의 종류 (구분)

- 엔터티 내에서 대표성을 가지는가? --> 주식별자 / 보조 식별자

- 엔터티 내에서 스스로 생성되었는가?   --> 내부 식별자 / 외부 식별자

- 단일 속성으로 식별 되는가? --> 단일 식별자 / 복합 식별자

- 업무적으로 의미를 가지는가? --> 본질 식별자(ex. 사원)/ 인조 식별자(ex. 일련번호 - 시스템적으로 부여된 것)

28번. 주식별자 도출 기준

- 해당 업무에서 자주 이용되는 속성을 주식별자로 지정

- 명칭, 내역 등과 같이 이름으로 기술되는 것들은 가능하면 주식별자로 지정 X

- 복합적으로 주식별자 구성 시 너무 많은 속성이 포함되지 않도록 함

* 주식별자 특징 : 유일성 / 최소성 / 불변성 / 존재성(Not NULL)

29번/30번. 비식별자 관계

- 비식별자 관계란? : 부모엔터티로부터 속성을 받았지만 자식엔터티의 주식별자로 사용하지 않고 일반적인 속성으로만 사용하는 경우

- 비식별자관계의 연결 고려사항

   1) 약한 종속 관계

   2) 자식 주식별자를 독립적으로 구성

   3) 자식 주식별자 구성에 부모 주식별자 부분 필요

   4) 상속받은 주식별자 속성을 타 엔터티에 차단 필요

   5) 부모쪽의 관계 참여가 선택 관계

   6) 여러 개의 엔터티를 하나로 통합하면서 각각의 엔터티가 갖고 있던 여러 개의 개별 관계가 통합되는 경우

문제 링크 : https://www.acmicpc.net/problem/2042

문제

어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고 a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력하면 된다.

입력으로 주어지는 모든 수는 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.

출력

첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력한다. 단, 정답은 -263보다 크거나 같고, 263-1보다 작거나 같은 정수이다.

접근 방법

데이터가 최근에 추가된 것 같은데, 문제에 주어진 조건이 명확하지 않아서 정답까지 오래 걸린 문제였다. N의 최대 값은 int 형인데 b,c모두 N을 넘지 않으므로 int형으로 선언했는데 계속 틀렸습니다가 출력됐다. 

100%에서 틀리는 경우에는 a,b,c모두 long long 으로 선언해서 다시 시도해보도록 하자! (c만 long long 으로 선언해줘도 되는데 문제에서 입력값 모두 long long형이라고 했으므로, 입력 값은 맘 편하게 모두 long long으로 선언하도록 하자.)

참고 : https://www.acmicpc.net/board/view/62196

#define MAX 1000001
#include <iostream>
using namespace std;

int N, M, K;
long long arr[MAX];

long long segTree[4000004];

long long init(int start, int end, int nodeNum)
{ //start : 시작 인덱스, end : 끝 인덱스,
    if (start == end)
        return segTree[nodeNum] = arr[start]; //리프 노드

    int mid = (start + end) / 2;
    return segTree[nodeNum] = init(start, mid, nodeNum * 2) + init(mid + 1, end, nodeNum * 2 + 1);
}

//start, end : 해당 노드의 시작, 끝 인덱스
//left, right : 구간 합 구하고자 하는 범위
long long subSum(int start, int end, int nodeNum, int left, int right)
{
    if (left > end || right < start)
        return 0;

    if (left <= start && end <= right)
        return segTree[nodeNum]; //완전히 포함 (6~11 구하고 싶은데 해당 노드가 6~8일 때)
    int mid = (start + end) / 2;
    return subSum(start, mid, nodeNum * 2, left, right) + subSum(mid + 1, end, nodeNum * 2 + 1, left, right);
}

void update(int start, int end, int nodeNum, int targetIdx, long long val)
{
    if (targetIdx < start || end < targetIdx)
        return;

    segTree[nodeNum] += val;
    if (start == end)
        return;
    int mid = (start + end) / 2;
    update(start, mid, nodeNum * 2, targetIdx, val);
    update(mid + 1, end, nodeNum * 2 + 1, targetIdx, val);
}

int main()
{

    cin >> N >> M >> K;

    int num;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    //1. 세그먼트트리 만들기 (트리 인덱스는 1부터 ~ )
    init(0, N - 1, 1);

    long long a, b, c;
    for (int i = 0; i < M + K; i++)
    {
        cin >> a >> b >> c;
        if (a == 1)
        { //b번째 인덱스를 c로 바꾸기. 바뀐 차이 만큼 트리 각 노드에 더해줘야함.
            long long tmp = c - arr[b - 1];	//arr 값 바꾸기 전에 값 저장해놓아야 파라미터로 넘길 수 있음
            arr[b - 1] = c;
            update(0, N - 1, 1, b - 1, tmp);
        }
        else
        { //b~c 합(b=3, c = 7이면 arr[2]~arr[6] 구해야 함)
            cout << subSum(0, N - 1, 1, b - 1, c - 1) << "\n";
        }
    }

    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/2748

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

접근 방법

처음에는 재귀 함수로 풀었는데 시간 초과가 났다.

그래서 DP로 풀었는데 dp[]의 자료형을 int 형으로 지정해서 오답으로 처리됐다. F(90) = 2,880,067,194,370,816,120 이므로 dp[]는  long long 형으로 선언해줘야한다. 

F(45) = 1836311903
F(46) = 2971215073
이므로 n = 46부터 int형 범위를 넘어간다. 

* long long(8byte) : –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 
* long (4byte) : –2,147,483,648 ~ 2,147,483,647

의문) long형으로 선언해도 백준은 정답으로 처리돼서 테스트케이스에 n=90이 없나 싶었는데,

         VsCode에서도 F(90)이 정상적으로 출력된다. 이론상으로는 long long 이 맞는데 정답 처리 되는 이유를 잘 모르겠다.

#include <iostream>
using namespace std;

long long dp[91]={0,};

int main()
{
    int n; cin >> n;
    
    dp[0] = 0; dp[1] = 1;
    for(int i = 2; i<=n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n];
    return 0;
}