나다김강니

LCA(최소 공통 조상)트리 그래프에서 임의의 두 노드를 선택했을 때 각각 자신을 포함해 거슬러 올라가다 처음 공통으로 만나게 되는 부모 노드 💡 최소 공통 조상의 핵심 이론ⓐ 일반적인 최소 공통 조상 구하기트리의 높이가 크지 않을 때는 일반적인 방법으로 구한다. 1️⃣ 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장한다. 2️⃣ 만약, 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 depth를 맞춰준다. 3️⃣ 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다.     이때 처음 만나는 노드가 최소 공통 조상이 된다.  ⓑ 최소 공통 조상 빠르게 구하기트리의 높이가 매우 커질 경우, 시간 제약 문..

세그먼트 트리주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조이다.더 큰 범위로 '인덱스 트리'라고 불린다. 💡 세그먼트 트리의 핵심 이론세그먼트 트리의 종류는 구간 합, 최대 · 최소 구하기로 나눌 수 있다. 1. 트리 초기화하기리프 노드의 개수가 데이터의 개수(N)이상이 되도록 트리 배열을 만든다.트리 배열 크기 구하기 : 2k ≥ N을 만족하는 k의 최솟값을 구하고 2k x 2를 트리 배열의 크기로 정의한다.그리고 주어진 데이터들을 2k에 해당하는 인덱스부터 채운다. 만약, 8개의 데이터가 주어졌을 때는 {5, 8, 4, 3, 7, 2, 1, 6}2의 제곱수 중 처음으로 8보다 크거나 같아지는 제곱수를 구한다 -> k=3배열의 크기는 23 x 2 = 16배열을 채..

이진 트리이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 말한다. 💡 트리의 핵심 이론이진 트리의 종류데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비 된다.일반적으로 코테에서 데이터를 트리에 담는다고 하면 완전 이진 트리 형태를 떠올린다.  이진 트리의 순차 표현이진 트리는 아래와 같이 1차원 배열의 형태로 표현할 수 있다.자식 노드 인덱스 = 부모 노드 인덱스 x 2, 부모 노드 인덱스 x 2 + 1 구성 요소인덱스 연산제약 조건(N = 노드 개수)루트 노드index = 1 부모 노드index = 자식 노드 인덱스 / 2현재 노드가 루트 노드가 아님왼쪽 자식 노드index = 부모 노드 인덱스 x 2index * ..

트리트리는 노드와 에지로 연결된 그래프의 특수한 형태이다.순환 구조(사이클)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 가진다.트리의 부분 트리 역시 트리의 모든 특징을 따른다. 💡 트리의 핵심 이론구성 요소설명노드데이터의 index와 value를 표현하는 요소에지노드와 노드의 연결 관계를 나타내는 선루트 노드트리에서 가장 상위에 존재하는 노드부모 노드두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드두 노드 사이의 관계에서 하위 노드에 해당하는 노드리프 노드트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)서브 트리전체 트리에 속한 작은 트리  💡 코딩테스트에서 트리가 나오는 유형① 그래프로 푸는 트리(DFS, BFS)② 트..

RESTREST는 Representational State Transfer의 약자로, HTTP 통신을 활용하기 위해 고안된 아키텍처이다.Representational인터넷상의 자원을 URI로 나타낼 수 있음을 의미URI로 표현된 자우너을 HTTP메서드를 이용해 CRUD 연산을 할 수 있다.State Transfer자원의 상태를 주고받는 것, 요청받은 자원의 상태를 전달하는 것💡 REST의 6가지 특징일관된 인터페이스자원을 나타내는 URI를 HTTP 메서드로 조작하는 일관된 인터페이스를 사용한다. HTTP를 따르는 모든 플랫폼에서 REST를 사용할 수 있다.클라이언트-서버 구조클라이언트와 서버 간에 요청-응답의 독립적인 구조를 가진다.클라이언트 : 서버에 요청을 보내고 응답을 대기서버 : 자원을 가지며 ..

HTTPHTTP는 인터넷상에서 데이터를 전송하기 위한 프로토콜로, TCP/IP 4계층에서 응용 계층에 속한다. HTTP의 특징 1️⃣ 비연결성(connectionless)비연결성이란 클라이언트에서 요청을 보낸 후 서버로부터 응답을 받으면 연결을 끊는 것을 의미한다.불특정 다수를 대상으로 하는 서비스에 유리하다.서버에서 응답은 받고 연결을 유지하려면 자원이 필요한데 비연결성으로 자원을 아낄 수 있다.하지만 연결을 유지하지 않기 때문에 서버가 클라이언트를 기억할 수 없다.동일한 클라이언트에서 연속적으로 요청이 오면 연결, 연결 해제를 반복해 자원을 낭비하게 된다. ☝🏻 위에서 말한 단점을 보완하기 위해 HTTP Keep Alive를 사용한다.HTTP Keep AliveHTTP 연결 시 일정 시간 동안 요..

TCPTCP는 전송 계층에 해당하는 네트워크 프로토콜로, 연결형 서비스를 지원하고 데이터의 신뢰성을 보장한다.송신부와 수신부의 연결을 확인하는 연결형 서비스패킷 교환 방식 : 패킷이 전달되는 회선이 정해져 있는 가상 회선 방식패킷 전송 순서가 보장된다.패킷의 수신 여부를 확인한다.송신부와 수신부가 1 : 1 통신을 한다.데이터 손실이 없음을 보장하므로 신뢰성이 높다.느리다☝🏻 패킷 교환 방식 2가지· 가상 회선 방식데이터를 주고받기 전에 패킷을 전송할 경로인 가상 회선을 설정해서 모든 패킷을 같은 경로로 전송 · 데이터그램 방식패킷마다 최적의 경로로 전송한다. 때문에 송신부에서 보낸 패킷 순서와 수신부에서 받는 패킷의 순서가 다를 수 있다. TCP 핸드셰이킹TCP에서는 연결형 서비스를 지원하기에 송신부..

네트워크 계층네트워크에는 다양한 기기 간 통신을 위해 약속된 구조가 있다.  OSI 7계층OSI 7계층이란 국제 표준화 기구에서 네트워크 통신이 이뤄지는 과정을 7단계로 나눈 네트워크 표준 모델이다. 📤 송신부 각 계층은 독립적이며 데이터를 송신할 때 각 계층에서 필요한 정보를 추가해 데이터를 가공한다. 이때 제어 정보를 담은 헤더나 트레일러가 붙는데, 이 과정을 데이터 캡슐화라고한다.응용 계층 -> 물리 계층 📥 수신부  물리 계층부터 응용계층까지 거치며 받은 데이터에서 헤더와 트레일러를 분석해 제거하는 역캡슐화를 진행한다. 이 과정에서 각 계층은 필요한 제어 정보를 얻는다.  프로토콜  통신 규약. 즉, 데이터를 송수신하기 위해 정한 규칙을 의미한다.7계층(응용 계층)HTTP, FTP 등의 프로토..

최소 신장 트리(MST)최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리사이클이 포함되면 가중치의 합이 최소가 될 수 없다. -> 사이클을 포함하지 않는다.N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다.최소 신장 트리 대표 알고리즘 : 크루스칼, 프림 💡 최소 신장 트리의 핵심 이론1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기데이터를 노드가 아닌 에지 중심으로 저장한다. 그래서 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.유니온 파인드 리스트도 함께 초기화한다. 자신의 인덱스 값으로 초기화한다.  2. 그래프 데이터를 가중치 기준으로 정렬한다.에지 리스트에 담긴 그래프 데이터를 가중치 기준으..

플로이드-워셜그래프에서 최단 거리를 구하는 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜)모든 노드 간에 최단 경로 탐색 -> 시작 노드가 따로 정해져있지 않다.음수 가중치 에지가 있어도 수행 가능하다. 다만, 사이클이 있으면 안된다.동적 계획법의 원리를 이용해 알고리즘에 접근한다.시간 복잡도는 O(V3)   노드가 1000개이면 시간초과가 일어날 확률이 높다.💡  플로이드-워셜 핵심 이론A노드에서 B노드까지 최단 경로를 구했다고 가졍했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로 🔍 도출한 플로이드-워셜 점화식     D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 1. 리스트를 선언하고 초기화하기D[S][E]는 노드 S에서..