![]()
HTTP(HyperText Transfer Protocol)HTTP는 애플리케이션 계층에서 웹 서비스 통신에 사용되는 프로토콜이다.HTTP는 HTML 문서와 같은 리소스들을 가져올 수 있도록 해주는 프로토콜로 웹에서 이루어지는 모든 데이터 교환의 기초이며 클라이언트-서버 프로토콜이기도 하다.클라이언트-서버 프로토콜이란 클라이언트 및 서버 요구 사항을 기반으로 하는 요청 및 응답 프로토콜로 서로 호환된다면 모든 유형의 콘텐츠를 교환할 수 있다. HTTP 요청HTTP 요청은 웹 브라우저와 같은 인터넷 통신 플랫폼에서 웹 사이트를 로드하는 데 필요한 정보를 요청하는 방법이다.인터넷을 통해 이루어진 각 HTTP 요청은 서로 다른 유형의 정보를 전달하는 인코딩 된 데이터를 전달하게 된다.일반적으로 아래와 같은 정..
![]()
IP(Internet Protocol) 주소 IP 주소는 인터넷 프로토콜 주소를 나타낸다. 즉, 네트워크를 통해 장치를 식별하는 고유 주소를 의미하는데 이는 인터넷이나 로컬 네트워크를 통해 전송되는 데이터의 구조를 관리하는 일련의 규칙과 거의 같다. IP주소는 인터넷이 서로 다른 라우터, 컴퓨터 및 웹사이트를 구별하는 데 도움이 되는데 이는 특정 네트워크에서 특정 기계 식별자 역할을 하며 소스와 대상 간의 시각적 통신을 개선하는 데 도움이 된다. ARP(Address Resolution Protocol) ARP는 주어진 IP 주소에 대한 MAC 주소를 검색하는 데 사용되는 프로토콜로 데이터를 목적지까지 보내기 위해서는 IP주소만 이용해서 보낼 수 없기 때문에 물리적 주소인 MAC 주소가 필요하게 된다. ..
![]()
TCP(Transmission Control Protocol) TCP는 패킷 사이의 순서를 보장하고 연결지향 프로토콜을 사용해서 연결을 진행하며 이를 바탕으로 신뢰성을 구축해서 수신 여부를 확인하는 가상회선 패킷 교환 방식을 사용한다. 장점 단점 신뢰할 수 있는 프로토콜이다. 광역 네트워크용으로 만들어졌으므로 리소스가 부족한 소규모 네트워크에서는 크기가 문제가 될 수 있다. 오류 검사 메커니즘과 복구 메커니즘을 제공한다. 여러 계층을 실행하므로 네트워크 속도를 늦출 수 있다. 흐름 제어를 제공한다. 연결을 통한 안정적인 데이터 전달을 보장함에 따른 오버헤드가 발생하여 속도가 느리다. 데이터가 전송된 정확한 순서대로 올바르게 도달했는지 확인할 수 있다. 가상회선 패킷 교환 방식 각 패킷에는 가상회선 식별자..
네트워크 기기네트워크는 여러 개의 네트워크 기기를 기반으로 구축된다.네트워크 기기는 계층별로 처리 범위를 나눌 수 있는데 상위 계층을 처리하는 기기는 하위 계층을 처리할 수 있지만 그 반대는 불가능하다. 계층별 주요 네트워크 기기애플리케이션 계층: L7 스위치인터넷 계층: 라우터, L3 스위치데이터 링크 계층: 브리지, L2 스위치물리 계층: NIC, 리피터, AP 애플리케이션 계층L7 스위치스위치는 여러 장비를 연결하고 데이터 통신을 중재하며 목적지가 연결된 포트로만 전기 신호를 보내 데이터를 전송하는 통신 네트워크 장비이다.여러 스위치 중 L7 스위치는 로드밸런서라고도 하며 서버의 부하를 분산하는 기기이다.클라이언트로부터 오는 요청들을 뒤쪽의 여러 서버로 나누는 역할을 하며 시스템이 처리할 수 있는 ..
![]()
OSI 7계층 CS 지식 중에서 네트워크 분야를 학습하면 가장 먼저 접하게 되는 지식이 바로 OSI 7계층이다.OSI 7계층은 표준 프로토콜을 사용하여 다양한 통신 시스템이 통신할 수 있도록 국제표준화 기구에서 만든 개념 모델이다. 말 그대로 컴퓨터 간 서로 통신할 수 있는 표준이라고 생각하면 될 것 같다.각 계층은 하위 계층과 상위 계층 간의 통신이 가능하여 데이터를 주고받을 수 있다.데이터는 Application Layer(응용 계층)에서 Physical Layer(물리 계층)으로 흐르게 되고 마지막 물리 계층이 데이터를 전송할 상대 PC의 물리 계층으로 전송하여 해당 PC의 물리 계층에서부터 다시 응용 계층으로 데이터가 전달된다.각 계층마다 어떤 역할을 가지고 있는지 하나씩 살펴보자. Applica..
![]()
유선 LAN 유선 LAN은 주로 이더넷으로 구축하며 전이중화 통신을 쓴다. 이더넷 이더넷은 가장 널리 사용되는 LAN 기술이며 IEEE802.3이라는 프로토콜에 따라 정의된다. 이더넷은 이해와 구현 및 유지 관리가 쉽고 저렴한 네트워크 구현이 가능하고 토폴로지 측면에서 유연성도 제공하기 때문에 폭넓게 사용되고 있다. 이더넷은 일반적으로 버스 토폴로지를 사용하고 있으며 OSI 모델에서 물리 계층과 데이터 링크 계층에서 작동한다. 주로 DLL을 다루므로 PDU는 프레임이다. 유선 네트워킹에서 이더넷을 자주 사용하는데 그 이유로 무선 네트워크보다 더 안전하고 간섭에 덜 민감하기 때문이다. 전이중화 통신 양쪽 장치가 동시에 송수신할 수 있는 방식을 말한다. 송신로와 수신로로 나눠서 데이터를 주고받으며 현대의 고..
![]()
네트워크(Network) 네트워크는 노드와 링크가 서로 연결되어 있거나 연결되어 있지 않은 집합체를 의미한다.여기서 노드는 서버, 라우터, 스위치 등 네트워크 장치를 의미하고 링크는 유선 네트워크 케이블 또는 무선 네트워크의 공간을 의미한다.컴퓨터 네트워크의 작동은 간단히 규칙이나 프로토콜로 정의될 수 있으며 이러한 규칙과 프로토콜은 링크를 통해 데이터를 송수신하고 컴퓨터 네트워크 간의 통신을 가능케 한다.좋은 네트워크를 만들기 위해서는 많은 처리량을 처리할 수 있고 지연 시간이 짧으며 장애 빈도가 적으면서 좋은 보안을 갖춰야 한다. 처리량처리량은 링크를 통해 전달되는 단위 시간당 데이터양을 말한다.단위로는 bps(bits per second)를 사용하고 초당 전송 또는 수신되는 비트 수를 의미한다.처리..
그리디(Greedy)그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.장기적인 결과보다 즉각적인 이익을 우선시하여 미래의 영향을 고려하지 않고 현재 상황을 기반으로 결정을 내린다.그리디 알고리즘을 사용하면서 조심해야 될 부분은 그리디 알고리즘은 항상 최적의 해를 보장하지 않는다는 것이다.그리디 알고리즘을 사용할 때 잘 따져보지 않으면 반례가 생길 수 있으니 조심해서 접근해야 된다.그리디 알고리즘을 적용하기 위해서는 두 가지 조건이 성립해야 한다. 1. 탐욕 선택 조건그리디 알고리즘을 적용하기 위해서는 탐욕적인 선택 즉, 선택지 중에서 최선의 선택을 했을 경우 전체 문제의 최적해를 반드시 도출할 수 있어야 한다. 2. 최적 부분 구조 조..
![]()
이진 탐색(Binary Search)이진 탐색은 정렬된 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.시간 복잡도는 O(logN)으로 빠른 시간 복잡도를 가진다.이진 탐색 알고리즘을 적용하기 위해서는 데이터가 정렬되어 있어야 하고 데이터 구조의 모든 요소에 액세스 하려면 일정한 시간이 걸리게 된다. 이진 탐색 과정(오름차순 기준)1. 현재 데이터셋의 중앙값을 선택한다. 2. 중앙값과 타깃 데이터를 비교하여 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다.현재 타깃 데이터는 50, 중앙값은 37로 서로 비교해보면 타깃 데이터가 더 크기 때문에 왼쪽 데이터셋은 선택하..
![]()
세그먼트 트리(Segment Tree)세그먼트 트리는 주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태가 바로 세그먼트 트리다.세그먼트 트리를 사용하는 이유는 구간 합을 할 때 데이터 업데이트가 느리기 때문이다.구간 합을 통해 만들어진 합 배열에서 중간에 데이터가 바뀌는 순간 기존 데이터와 바뀌는 데이터의 차이 만큼 바뀌는 데이터 뒤에 위치한 값들에게 모두 더해줘야 하는 문제가 생긴다. 이러한 업데이트 시 시간이 오래걸린다는 문제점을 세그먼트 트리로 해결할 수 있다. 세그먼트 트리 핵심 이론1. 트리 초기화 하기리프 노드의 개수가 데이터의 개수 이상이 되도록 트리 배열로 만든다.샘플 데이터로 {5, 8, 4, 3, 7, 2, 1, 6}이 주어진다면 먼저 트리의 크..
![]()
최소 공통 조상(LCA, Lowest Common Ancestor)최소 공통 조상은 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 뜻한다.일반적으로 구하는 방법과 빠르게 구하는 방법이 있다. 일반적인 최소 공통 조상 구하기먼저 일반적인 최소 공통 조상 구하기를 사용하려면 트리의 높이가 크지 않은지 판단해야 한다.최소 공통 조상은 트리의 높이가 시간 복잡도에 많은 영향을 주기 때문에 트리의 높이가 높지 않은 경우에 사용한다.예시로 4번 노드와 15번 노드의 공통 조상을 찾는다고 해보자먼저 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장해야 한다. 여기서 트리라는 특징을 잘 활용하면..
![]()
이진 트리(Binary Tree)이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 뜻한다.트리 영역에서 가장 많이 사용되는 형태로 트리를 1차원 배열로 표현해준다. 이진 트리의 종류1. 편향 이진 트리: 노드들이 한 쪽으로 편향돼 생성된 이진 트리2. 포화 이진 트리: 프리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리3. 완전 이진 트리: 마지막 레벨(차수)을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽 부터 채워진 트리※ 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비되므로 데이터를 담을 때 완전 이진 트리의 형태로 담는 것이 좋다. 이진 트리의 순차 표현가장 직관적이면서 편리한 트리 자료구조 형태는 바로 배열이다.배열의 인덱스..
![]()
트리(Tree)트리는 노드와 에지로 연결된 그래프의 특수한 형태로 비선형 계층적 자료구조이다.각 노드는 여러 노드의 주소를 저장한다. 모든 노드는 자식의 주소를 저장하고 첫 번째 노드의 주소는 루트라는 별도의 포인터에 저장된다.그래프의 특수한 형태이기 때문에 그래프의 표현으로도 트리를 표현할 수 있다. 트리의 구성 요소노드 - 데이터의 인덱스와 벨류를 표현하는 요소에지 - 노드와 노드의 연결 관계를 나타내는 선루트 노드 - 트리에서 가장 상위에 존재하는 노드부모 노드 - 두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드 - 두 노드 사이의 관계에서 하위노드에 해당하는 노드리프 노드 - 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)서브 트리 - 전체 트리에 속한 작은 트리 트리의 ..
![]()
동적 계획법(DP, Dynamic Programming)동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다. 동적 계획법의 원리와 구현 방식1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다.3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 DP 테이블을 이용한다. 이를 메모이제이션(Memoization) 기법이라고 하고, 시간 복잡도 측면에서 유리하다.4. 동적 계획법은 탑-다운 방식과, 바텀-업 방식으로 구현할 수 있다. 아래의 핵심 이론은 동적 계획법의 기초적인 예제인 피보나치 수열로 설명..
![]()
조합(Combination)조합은 코딩 테스트에 자주 출제되는 주제이며 동적 계획법(DP)을 이해하는데 기초가 되는 부분이다.조합 점화식 도출 방법에 대해 깊이 학습하면 조합은 물론 동적 계획법의 점화식 도출 부분에 많은 도움이 된다.조합과 비슷한 순열을 비교하면 조합은 순서를 고려하지 않고, 순열은 순서를 고려한다는 부분이 다르다.위 사진과 같이 순열은 순서를 고려하기 때문에 1,2,3과 3,2,1을 각각 다른 것으로 구분하지만, 조합은 순서를 고려하지 않기 때문에 두개 다 같은 것으로 생각한다.왼쪽은 순열의 수학적 공식, 오른쪽은 조합의 수학적 공식이다. 다른 점으로는 조합은 순서를 고려하지 않기 때문에 r!를 추가하여 순서가 다를 경우의 수를 제거해준다.조합의 공식을 살펴보면 n개의 숫자에서 r개를..
