'📒 CS' 카테고리의 글 목록

[Data Structure] AVL 트리

2023.08.19

AVL 트리 AVL 트리 (Adelson-Velsky and Landis tree)는 이진 탐색 트리가 데이터 삽입 순서로 인해 선형적인 형태의 트리가 되는 것을 방지하고자 스스로 균형을 잡는 이진 탐색 트리를 말한다. 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다. (균형 이진 트리의 일종) 데이터 삽입, 삭제시 균형이 항상 맞도록 트리 일부를 왼쪽 혹은 오른쪽으로 회전시킨다 (리밸런싱). 🔹가장 처음 나온 자가 균형 이진 트리 🔹red-black tree보다 균형은 훨씬 잘 잡힘 🔹red-black tree보다 삽입, 삭제가 느림 🔹서브 트리 높이 차이가 1보다 커지면 회전(리밸런싱) 통해 차이 줄임 💡탐색, 삽입, 삭제 시간 복잡도: O(logN) Balance Factor..

📒 CS/📝 Data Structure

[Data Structure] 그래프 - 인접행렬과 인접리스트

2023.08.19

그래프 (Graph) 그래프는 정점과 간선으로 이루어진 비선형 자료 구조를 말한다. 🔹정점(V) (vertex) - 그래프 내의 하나의 개별적 요소 🔹간선(E) (edge) - 정점과 정점 사이를 연결하는 선 (흐름, 관계 표현) 🔹가중치(W) (weight) - 간선과 정점 사이에 드는 비용 🔹차수 (degree) - 정 정점에 연결된 간선의 수 ◽out-degree: 다른 정점으로 나가는 간선 (수) ◽in-degree: 특정 정점으로 들어오는 간선 (수) ◽무방향 그래프에선 하나의 간선이 두 정점에 인접하므로 간선 수의 두 배 💡 비선형 자료 구조 비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다. 일반적으로 트리나 그래프를 말한다. 방향 그래프(Diredted Gr..

📒 CS/📝 DB

[DB] 논리적 조인 (Inner/Outer/Cross/Self)

2023.08.10

조인 두 개 이상의 테이블을 묶어 하나의 결과물을 만드는 것을 말한다. 비관계형 데이터베이스(MongoDB)에서도 lookup이란 쿼리로 이를 처리할 수 있는데, 관계형 데이터베이스보다 성능이 떨어지기 때문에 되도록 사용하지 않는다. 조인(논리적 조인)의 종류 논리적 조인이란 사용자가 SQL문을 이용해 원하는 데이터 결합 방식을 기술하는 것을 의미한다. Inner Join (내부 조인): 왼쪽 테이블과 오른쪽 테이블의 두 행이 모두 일치하는 행이 있는 부분만 표기 Outer Join Left Join (왼쪽 조인): 왼쪽 테이블의 모든 행이 결과 테이블에 표기 Right Join (오른쪽 조인): 오른쪽 테이블의 모든 행이 결과 테이블에 표기 Full Outer Join (전체 외부 조인): 조인 조건에..

📒 CS/📝 DB

[DB] 정규화 과정 (1NF/2NF/3NF/BCNF)

2023.08.03

함수적 종속(Functional Dependency) 관계형 데이터베이스에서의 정규화 과정을 살펴보기 전, 함수적 종속 개념에 대해 먼저 알아보자. 릴레이션 R(테이블)에서 X와 Y를 R의 속성의 부분집합이라고 할 때, X의 값 각각에 대해 Y의 값이 오직 하나로 결정 될 때 Y는 X에 종속된다고 한다. 즉, 테이블의 한 필드값 집합(X)이 다른 필드값 집합(Y)을 결정하는 관계를 말한다. 여기서 "결정한다"는 의미는 무엇일까? "알 수 있다", "영향을 미친다" 라고 받아들이면 쉽다. "X가 Y을 결정한다"라는 뜻은 X의 값을 알면 Y의 값을 알 수 있고, X와 Y는 관계가 있어 X의 값에 의해 Y의 값이 달라진다는 것을 의미한다. 이런 함수적 종속 관계를 화살표를 통해 X→Y라고 표현하고 X를 결정자..

📒 CS/📝 Network

[네트워크] HTTP (HTTP/1.X, HTTP/2, HTTP/3)

2023.07.25

HTTP HTTP(Hyper Text Transfer Protocol)는 클라이언트와 서버 간 정보를 주고받기 위한 통신 규약이다. 애플리케이션 계층에서 동작하고 웹 서비스 통신에 사용된다. HTTP/1.0부터 HTTP/3까지 발전해 왔다. 무상태성(stateless) - HTTP는 요청에 대한 상태를 가지지 않음 - 각 요청은 독립적 → 요청 간의 서로 영향 주고받지 않음 - 상태(로그인 정보 등)를 사용하기 위해선 세선이나 쿠키 사용 비연결성(Connectionless) - 요청을 주고받을 때만 연결을 유지하고 전송이 끝나면 연결 끊김 서버-클라이언트 구조 - 일반적으로 클라이언트는 웹브라우저 - 서버는 요청 대상인 서버 컴퓨터 의미 📜HTTP/1.0 한 연결당 하나의 요청을 처리한다. 서버로부터 정..

📒 CS/📝 Network

[Network] 네트워크 기기

2023.07.11

네트워크 기기 처리 범위 네트워크 기기는 네트워크 계층별로 처리 범위를 나눌 수 있다. 상위 계층 처리 기기 → 하위 계층 처리 가능 하위 계층 처리 기기 → 상위 계층 처리 불가 애플리케이션 계층 : L7로드밸런서(L7스위치) 전송 계층 : L4로드밸런서(L4스위치) 인터넷 계층: 라우터, L3스위치 데이터 링크 계층 : L2스위치, 브리지 물리 계층: NIC, AP 💡 스위치 - 여러 장비를 연결하고 데이터 통신을 중재 - 목적지가 연결된 포트로만 전기 신호보내 데이터를 전송하는 네트워크 장비 - 소규모 통신을 위한 허브보다 전송 속도 개선 애플리케이션 계층 처리 기기 L7로드밸런서(L7 스위치) 앞에 붙은 L7는 Layer7이란 뜻으로 OSI 7계층의 7번째 계층인 애플리케이션 계층에서 사용되는 기..

📒 CS/📝 Network

[Network] TCP 연결 및 연결해제 과정 (3-way handshake / 4-way handshake)

2023.07.11

TCP는 신뢰성을 확보하기 위해 송수신자 사이 연결과정과 연결 해제 과정 작업을 진행한다. + 기초 지식 제어 플래그(코드 비트) 세그먼트 헤더에 있는 영역으로 TCP 연결 회선 및 데이터를 제어하기 위한 비트이다. 6개의 종류가 있는데 TCP 연결 및 해제에선 아래 3개의 종류만 사용된다. ACK: Acknowledgement의 약자로 “응답”을 의미하는 플래그 SYN: Synchronize의 약자로 “연결 요청”을 의미하는 플래그 FIN: Finish의 약자로 “연결 해제 요청”을 의미하는 플래그 초기값: 0 / 활성 시: 1 포트 상태 정보 각 호스트의 포트 상태를 의미 CLOSED : 포트가 닫힌 상태 LISTEN : 포트가 열린 상태로 연결 요청 대기 중 SYN_SENT : SYN요청을 보내고 ..

📒 CS/📝 Network

[Network] TCP vs UDP

2023.07.10

네트워크 계층과 전송계층 네트워크 계층 중 전송 계층에 해당하는 프로토콜에는 TCP와 UDP두 종류가 있다. 이 프로토콜을 살펴보기 전에 하위 계층인 네트워크 계층에 대해 잠시 생각해 보자. OSI 7 계층에서 3 계층에 해당하는 네트워크 계층은 논리적 주소인 IP를 이용해 통신한다. IP의 역할은 장치 간의 통신(Host to Host)만을 지원한다. 따라서 같은 장치 안에서 여러 프로그램들이 통신할 경우IP만을 가지고는 통신할 수 없다. 따라서 상위 계층인 전송계층에서 포트(port) 번호를 이용하여 문제상황을 해결한다. 또한 네트워크 계층은 비연결형 프로토콜을 기반으로 동작한다. 이는 패킷이 독립적으로 처리되어 독립적인 경로로 전달된다는 의미이고 수신 확인 과정이 존재하지 않는다는 것을 의미한다. ..

📒 CS/📝 Network

[Network] 네트워크 계층 구조 (OSI 7계층, TCP/IP 4계층)

2023.07.10

인터넷 프로토콜 스위트 인터넷 프로토콜 스위트(Internet protocol suite)은 인터넷에서 정보를 주고받는 데 이용되는 통신 프로토콜의 모음이다. 이를 보통 TCP/IP 4계층 모델과 OSI 7계층 모델로 설명한다. 💡 프로토콜 (protocol) - 컴퓨터 내부 또는 컴퓨터 사이에서 데이터의 교환 방식을 정의하는 규칙 체계 - 기기 간 통신은 교환되는 데이터의 형식에 대해 상호 합의를 요구하는데, 이런 형식을 정의하는 규칙의 집합을 프로토콜이라고 한다. 네트워크 계층구조 컴퓨터 간 서로 통신하기 위해선 하나의 프로토콜로만 이루어질 수 없다. 통신 프로토콜의 집합은 프로토콜의 네트워킹 범위에 따라 추상화 계층으로 구분할 수 있으며 대표적으로 OSI 7계층과 TCP/IP 4계층 모델로 프로토콜..

📒 CS/📝 Network

[Network] 네트워크 기초 (용어, 분류, 토폴로지)

2023.07.06

네트워크 기초 용어 네트워크란? 네트워크란 컴퓨터 등의 장치들이 통신 기술을 이용하여 구축하는 연결망을 지칭하는 용어다. 네트워크는 노드(node)와 링크(link)로 구성되어 있으며, 리소스를 공유한다. "몇 개의 독립적인 장치가 적절한 영역 내에서 적당히 빠른 속도로 물리적 통신 채널을 통하여 서로가 직접 통신할 수 있도록 지원해 주는 데이터 통신 체계" _ IEEE(국제 전기 전자 공학회) 💡 노드(node) 컴퓨터, 서버, 라우터, 스위치 등의 네트워크 장치 💡링크(link) 유선 또는 무선 처리량, 트래픽, 대역폭 처리량(throughput)이란 링크 내에서 성공적으로 전달된 데이터의 양을 말한다. 단위로는 bps (bits per second)를 사용하며 초당 전송(수신)된 비트 수를 나타낸다..

티스토리툴바