CS

이진탐색 - Lower bound, Upper bound

Target으로 찾는 값이 한 배열 안에 여러 개 존재할 때, target 값 이상의 값이 최초로 나오는 위치를 Lower Bound라고 한다. Target을 초과하는 값 중, 가장 인접한 위치를 Upper Bound라고 한다. Target보다 같거나 작은 숫자들 중, target 값이 마지막으로 나오는 위치를 Custom Bound라고 한다. Lower Bound public static int lowerBound(int[] arr, int target) { int left = 0; int right = arr.length - 1; int minIdx = arr.length; while (left = target) { right = mid - 1; minIdx = Math.min(mid, minIdx)..

이진탐색

이진탐색 찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소 관계에 따라 특정 구간으로 이동하는 것을 반복. 전제 숫자들이 좌에서 우측으로 커진다는 전제에서 가능하므로, 숫자들은 항상 정렬되어있어야 한다. 가운데의 숫자를 선택하고 해당 숫자보다 크다면 우측(최소 값 위치를 타겟 숫자 + 1로 변경, 최대 값 위치 유지) 작다면 좌측 범위를 선택하게 되는 것(최소 값 위치 유지, 최대 값 위치를 타겟 숫자 -1로 변경) 시간복잡도는 구간의 길이가 1이 될때까지 계속해서 반으로 감소하는 것을 반복하기 때문에, 루프는 약 log2​N 번 돌게 된다. 루프 내부 연산의 시간 복잡도는 O(1)이기 때문에, 자연스럽게 시간복잡도는 O(1∗logN)=O(logN) 이진 탐색을 사용 하는 이유는 ..

[DP] 한 칸씩 이동하여 최대 합 구하기.

조건 각 칸에 숫자가 적혀있는 판이 존재한다. 이동은 (i+1, j), (i+1, j+1)만 가능하다. 풀이 마지막 방문 위치가 dp[i][j]일 때, 해당 위치에 도달할 수 있는 경우는 바로 위에서 내려온 경우, 왼쪽 대각선 위에서 내려오는 경우 두가지 경로가 존재한다. 이전 위치와 현재 위치의 값을 합한 후, 최대값을 dp[i][j]에 저장한다. 점화식 dp[i][j] = max(dp[i-1][j] + a[i][j], dp[i-1][j-1] + a[i][j])

[HTTP] HTTP 메세지

HTTP 메시지 구조 empty line 공백 라인(CRLF)는 무조건 들어가야 한다. HTTP 요청 메시지 GET /search?q=hello&hl=ko HTTP/1.1 Host: www.google.com HTTP 응답 메시지 HTTP/1.1 200 OK Content-Type: text/html;charset=UTF-8 Content-Length: 3423 ... 시작 라인 - 요청 메시지 start-line = request-line / status-line request-line = method SP(공백) request-target SP HTTP-version CRLF(엔터) HTTP 메서드(GET: 조회) 요청 대상(/search?q=hello&hl) HTTP Version 요청 메시지 - ..

[HTTP] 비 연결성(Connectionless)

연결을 유지하는 모델 클라이언트 2와, 3이 놀고 있어도 계속 연결한 서버가 유지를 해야 한다는 단점이 있음. 연결을 유지하지 않는 모델 최소한의 자원으로 서버를 유지할 수 있음. 비 연결성 HTTP는 기본이 연결을 유지하지 않는 모델이다. 일반적으로 초 단위 이하의 빠른 속도로 응답 1시간 동안 수천명이 서비스를 사용해도 실제 서버에서 동시에 처리하는 요청은 수십 개 이하로 매우 작다. 예) 웹 브라우저에서 계속 연속해서 검색 버튼을 누르지 않는다. 서버 자원을 매우 효율적으로 사용할 수 있다. 한계와 극복 TCP/IP 연결을 새로 맺어야 한다. - 3 way handshake 시간이 추가된다. 웹 브라우저로 사이트를 요청하면 HTML 뿐만 아니라 자바스크립트, css, 추가 이미지 등등 수많은 자원이..

[HTTP] Stateful, Stateless

무상태 프로토콜 무상태(Stateless) 서버가 클라이언트의 상태를 보존하지 않는다. 장점: 서버 확장성(스케일 아웃)이 높다. 단점: 클라이언트가 추가 데이터를 전송해야 한다. Stateful, Stateless 차이 상태 유지(Stateful) 중간에 다른 서버로 바뀌면 안 된다. 서버가 바뀔 시 상태 정보를 다른 서버에게 미리 알려줘야 한다. 무상태(Stateless) 중간에 다른 서버로 바뀌어도 괜찮다. 클라이언트 요청이 증가해도 서버를 대거 투입할 수 있다. 무상태는 응답 서버를 쉽게 바꿀 수 있다 -> 무한한 서버 증설이 가능하다. 무상태(Stateless)의 한계 무상태 - 데이터를 너무 많이 보낸다. 로그인이 필요 없는 단순한 서비스 소개 화면 상태 유지 로그인 로그인한 사용자의 경우 로..

[HTTP] 클라이언트 서버 구조

클라이언트 서버 구조 Request Response 구조 클라이언트는 서버에 요청을 보내고, 응답을 대기 서버가 요청에 대한 결과를 만들어서 응답 클라이언트와 서버를 분리하는 것이 중요하다. 비즈니스 로직과 데이터를 서버에 넣고 클라이언트는 UI와 사용성에 집중한다. 클라이언트와 서버가 각각 독립적으로 진화 가능하다. 참조 모든 개발자를 위한 HTTP 웹 기본 지식 - 인프런 | 강의 실무에 꼭 필요한 HTTP 핵심 기능과 올바른 HTTP API 설계 방법을 학습합니다., - 강의 소개 | 인프런... www.inflearn.com

[HTTP] HTTP

HTTP HyperText Transfer Protocol HTTP 프로토콜에 모든 형태의 데이터를 전송 가능. HTML, TEXT IMAGE, 음성, 영상, 파일 JSON, XML (API) 거의 모든 형태의 데이터 전송 가능 서버간에 데이터를 주고 받을 때도 대부분 HTTP 사용 실무에서 일해보면 서버간 통신할 때 TCP 프로토콜 직접 이용해서 데이터를 전송하는 경우가 거의 없다. HTTP 프로토콜로 연결하고, 물론 TCP 프로토콜 위에 HTTP 프로토콜이 있긴 함. TCP 직접 연결해서 하는 경우는 게임 서버 또는 특수한 경우. 모바일 게임의 경우 HTTP열어서 통신하는 구조로 개발을 많이 한다. 시간이 흐르면서 문서 뿐 아니라 모든 것을 전송할 수 있게 발전하였음 HTTP 역사 HTTP/0.9 1..