본문 바로가기

J 바로가기

📌CS49

레드-블랙 트리 개념 각 노드에 한 비트의 color 필드가 추가로 있으며 아래 레드-블랙 특성을 모두 만족하는 이진 탐색 트리를 말한다. 레드-블랙 특성 각 노드 color는 '레드'이거나 '블랙'이다. 루트와 외부 노드(NIL)의 color는 블랙이다. 레드 노드의 부모 노드는 반드시 블랙이다. 임의의 노드 x에서 후손 리프까지 가는 경로에 있는 블랙 노드의 개수는 같다. 이것을 black-height(x)라고 한다. 트리의 높이 O(log n) n개의 키를 가진 레드-블랙 트리 T의 높이를 h라고 하면 h ≤ 2log(n+1) 이다. 높이차는 최대 2배 이상 커지지 않는다. 연산 O(log n) 탐색 최소값 찾기 최대값 찾기 선행자 후행자 삽입, 삭제 연산 알고리즘에서 수행하는 rotation은 최대 2회이다. 참.. 2021. 4. 11.

[DB] N + 1 문제 개념 ORM에서 성능 이슈가 발생하면 가장 흔한 원인으로 N+1 Problem이 언급된다. N+1 Problem은 쿼리 1번으로 N건의 데이터를 가져왔는데 원하는 데이터를 얻기 위해 이 N건의 데이터를 데이터 수 만큼 반복해서 2차적으로 쿼리를 수행하는 문제입니다. ORM : (Object Relational Mapping) 객체-관계 매핑 객체와 관계형 데이터베이스의 데이터를 자동으로 매핑(연결)해주는 것을 말한다. 객체 지향 프로그래밍은 클래스를 사용하고, 관계형 데이터베이스는 테이블을 사용한다. 객체 모델과 관계형 모델 간에 불일치가 존재한다. ORM을 통해 객체 간의 관계를 바탕으로 SQL을 자동으로 생성하여 불일치를 해결한다. Persistence API라고도 할 수 있다. JPA : (Java.. 2021. 4. 11.

문자 인코딩 | ASCII, Unicode, UTF-8 인코딩 사용자가 입력한 문자나 기호를 컴퓨터가 이용할 수 있는 신호로 만드는 것을 말한다. 문자 → 숫자 : 인코딩 숫자 → 문자 : 디코딩 예를 들어, 메모장에 A라고 친 다음 저장하면 실제로 하드디스크에 기록되는 정보는 65라는 숫자값. A -> 65라고 저장하도록 만들어놨기 때문에 아스키코드 가장 처음 만들어진 인코딩이 ASCII코드. 숫자와 문자를 매칭시키는 국제적 규칙. 패리티 비트를 제외하고, 128개의 문자조합을 제공하는 7비트 부호 (패리티 비트는 데이터의 에러를 탐지하기 위해 사용한다. 일곱자리의 이진수에서 '1'이 홀수개라면 끝에 1을, '1'이 짝수개라면 끝에 0을 덧붙인다. 아주 정밀하진 않지만 패리티 비트를 이용해 어느 정도의 에러를 탐지할 수 있다.) 문제점 아스키코드만으로는 영.. 2021. 4. 10.

[Web] HTTP, HTTPS, HTTP 버전 HTTP Hyper Text Transfer Protocol의 약어로 WWW(World Wide Web)에 내재된 프로토콜이다. 인터넷에서 자원(파일, 이미지, 비디오)을 교환하는 프로토콜(약속, 규칙) ∴ HTTP는 인터넷에서 클라이언트와 웹 서버간 통신(데이터를 주고 받음)을 위한 프로토콜 중 하나 기본 포트 80 하이퍼텍스트 문서를 표현하기 위한 텍스트 형식의 마크업 언어가 HTML(하이퍼 텍스트 마크업 언어) 문서 같은 것을 교환하기 위한 간단한 프로토콜이 HTTP(하이퍼텍스트 전송 프로토콜) 문서를 디스플레이하기 위한 클라이언트가 WWW(첫번째 브라우저) CORS(Corss-Origin Resource Sharing) 보안상의 이유로 브라우저들이 다른 도메인에게 XHR 요청 보내는 것을 제한할 .. 2021. 4. 8.

[OS] 스레드 이 글은 '그림으로 배우는 구조와 원리 운영체제' 개정3판을 참고하여 작성하였습니다. 첨부된 이미지는 책을 기반으로 직접 제작했습니다. 목차 1. 스레드의 개념과 상태 변화 개념 스레드의 주소 공간 단일 스레드와 다중 스레드 스레드의 상태 변화 스레드의 제어 블록 2. 스레드의 구현 사용자 수준 스레드 커널 수준 스레드 혼합형 스레드 1. 스레드의 개념과 상태 변화 개념 지금까지 살펴본 프로세스는 두 가지 특성인 자원과 제어로 구분할 수 있다. 이 중 제어만 분리한 실행 단위를 스레드(thread)라고 하는데, 프로세스 하나는 스레드 한 개 이상으로 나눌 수 있다. 스레드들은 프로세스의 직접 실행 정보를 제외한 나머지 프로세스 관리 정보를 공유한다. 프로그램 카운터(PC)와 스택 포인터(SP)등을 비롯한.. 2021. 4. 4.

[DB] Index 인덱스란? 인덱스 == 목차, RDBMS에서 검색 속도를 높이기 위한 기술 인덱스는 결국 지정한 컬럼들을 기준으로 메모리 영역에 일종의 목차를 생성하는 것이다. 인덱스가 필요한 이유 컴퓨터는 자주 사용되는 데이터(테이블 등)를 메모리에 올리는데, 사용자가 데이터를 찾을 때 메모리에 데이터가 없다면 디스크에서 테이블 전체를 훑으면서 찾아야 하고 이를 Full Table Scan이라고 한다. 대용량 데이터에서는 굉장히 비효율적이다. 그래서 Full Table Scan을 방지하기 위해서 목차와 같은 인덱스를 만들어서 데이터를 관리한다. 특징 인덱스는 메모리에 저장된다. B-Tree 형태로 저장됨 자식 노드가 2개 이상 디스크에 데이터를 저장하는 Page(Block)을 가장 기본단위 로 삼는다. 디스크 읽기 쓰.. 2021. 4. 4.

[Web] 쿠키와 세션 HTTP 프로토콜 특징 비연결 지향(Connectionless) 클라이언트에서 서버에 요청을 보내면 서버는 클라이언트에 응답을 하고 접속을 끊는 특성이 있다.(HTTP1.1에서 Connection헤더에 keep-alive설정하면 커넥션을 유지할 수 있다.) 상태정보 유지 안 함(Stateless) HTTP 통신은 요청을 응답하고 접속을 끊기 때문에 클라이언트 상태 정보를 알 수 없다. 쿠키와 세션의 필요성 쿠키와 세션의 탄생 → HTTP 프로토콜에서 상태를 유지하기 위함 위와 같은 HTTP 프로토콜의 특징으로 모든 요청간의 의존관계가 없기 때문에 사용자를 인증할 수 없다. 이전 요청과 현재 요청이 같은 사용자의 요청인지 알기 위해서는 상태를 유지해야 한다. HTTP 프로토콜에서 상태를 유지하기 위한 기술.. 2021. 4. 4.

[Web] REST & RESTful REST & RESTful REST는 HTTP, 프로토콜이 아니다! REST는 일종의 가이드라인이다. REST API 는 REST 기반으로 서비스 API를 구현한 것 REST 원리를 따라르는 시스템(서비스)를 RESTful 이라고 한다. = REST API 를 제공하는 웹 서비스를 RESTful 하다고 할 수 있다. REST REST는 Representational State Transfer의 약자로 분산 하이퍼 미디어 시스템을 위한 소프트웨어 아키텍처의 한 형식이다. 웹에 존재하는 모든 자원(이미지, 동영상, DB자원)에 고유한 URL을 부여해 활용하는 것으로 자원을 정의하고 자원에 대한 주소를 지정하는 방법론을 의미한다. → URL에 자원을 표현하는 것 HTTP URI 를 통해 자원을 명시하고 HTT.. 2021. 4. 3.

[OS] 프로세스 이 글은 '그림으로 배우는 구조와 원리 운영체제' 개정3판을 참고하여 작성하였습니다. 첨부된 이미지는 직접 제작했습니다. 목차 1. 프로세스 개념과 상태 변화 개념 필요자원 프로그램과 프로세스 차이 관점에 따른 프로세스 프로세스 종류 프로세스 상태 변화와 상태 정보 프로세스 제어 블록 프로세스의 문맥 교환 2. 프로세스의 관리 프로세스의 구조 프로세스의 생성 프로세스의 종료 프로세스의 제거 프로세스의 중단과 재시작 프로세스의 우선순위 변경 프로세스의 문맥 교환 1. 프로세스 개념과 상태 변화 개념 일반적인 프로세스 정의는 '실행 중인 프로그램'이다. 실행 중이라는 의미는 디스크에 있던 프로그램을 메모리에 적재하여 운영체제의 제어를 받는 상태가 되었다는 것이다. 이는 자신만의 메모리 영역(주소 공간)이 있.. 2021. 4. 2.

이전 1 2 3 4 5 6 다음

티스토리툴바