9._.coding

NAT, Network Address Translation은 네트워크 주소를 변환해주는 장치로 공유기, 라우터 드의 라우팅 장치를 통과하는 IP 패킷 헤더의 IP주소 정보를 변환한다. 로컬 네트워크 (서브넷)에는 하나의 외부 IP주소만 사용하며, 로컬 내부에서는 NAT이 부여한 private IP주소를 사용한다. 즉, 하나의 public IP주소를 이용해 로컬 네트워크 내부에 여러 장치들을 사용할 수 있는 것이다. (private IP주소를 사용) 1) 10.0.0.1의 주소를 가진 호스트가 128.119.40.186, 80으로 데이터그램을 보내고자 한다. 2) NAT 라우터가 데이터그램 전송 주소 10.0.0.1, 3345를 138.76.29.7, 5001로 바꾸고, NAT translation tab..

DHCP는 Dynamic Host Configuration의 약자로 컴퓨터가 네트워크에 접속하면 DHCP 서버가 자동으로 (동적으로) IP 주소를 할당해주는 역할을 한다. 사용 중인 주소를 연장하거나 연결된 상태에서 주소를 재사용 할 수 있다, 서버와 클라이언트로 나뉘어 동작하는데, 클라이언트는 접속하려는 PC와 같다고 생각하면 된다. DHCP 서버는 공식적인 IP주소를 보유하며, IP주소를 클라이언트에게 자동으로 할당해준다. DHCP 클라이언트는 DHCP 서버에게 서비스 받는 호스트로, 부팅하면 DHCP 서버에게 IP주소를 요청 받고, lease time이라고 불리는 일정 기간 동안 IP주소를 부여받고 사용한다. 호스트가 DHCP를 통해 IP 주소를 얻는 과정은 discover, offer, reque..

인터페이스란 호스트 또는 라우터와 물리적 링크 간의 연결을 의미하는 것으로, 호스트는 유선 이더넷, 무선 랜 등 일반적으로 몇 개의 인터페이스를 가지고, 라우터는 일반적으로 다중 인터페이스를 보유한다. 인터페이스는 고유 IP 주소를 가지고 있다. 우리가 흔히 사용하고 있는 32비트 IP 주소는 호스트/라우터 인터페이스의 32bit 식별자로 서브넷 ID와 호스트 ID를 포함하고 있으며, 이것이 무엇인지에 대해서는 이 게시물 아래에서 소개합니다. 이 방식을 IPv4라고 하는데, 32비트 체계이므로 약 42억 개의 IP 주소를 표현할 수 있습니다. 8비트가 4개로 점을 이용해 구분하며, 십진수 표기이기 때문에 한 자리에 올 수 있는 최대 수는 255입니다. Subnets 서브넷은 대규모 네트워크를 구성하는 개..

네트워크 계층은 통신 계층으로부터 세그먼트를 받아 데이터그램으로 처리한 후에 다시 통신 계층으로 전송해주는 계층이다. Sender, 즉 송신 측에서는 세그먼트를 데이터그램화 해주는데, 이 과정을 헤더로 감싸준다고 해서 encapsulation, 캡슐화라고 한다. 인접 라우터로 데이터그램을 전송하는데, 입력 링크에서 출력 링크로 데이터그램을 전달해준다. Receiver, 수신 측에서는 링크 계층(네트워크 계층의 하위 계층)으로부터 받은 데이터그램에서 세그먼트를 추출하여 이를 통신 계층으로 전송한다. 이 과정은 모든 호스트와 라우커에서 동작해야 한다. Routing / Forwarding 네트워크 계층에서는 라우팅과 포워딩의 두 과정이 있습니다. 라우팅은 목적지까지 최적의 경로를 찾아주는 것으로 일종의 네비..

HTTP는 응용 계층 프로토콜로 클라이언트와 서버로 나누어져 동작하는데, 클라이언트는 사용자, 웹 브라우저 쪽으로 웹에서 필요한 것들을 서버에 요청/수신/표시한다. 서버는 클라이언트의 요청에 대한 응답으로 클라이언트가 필요한 객체를 보내준다 HTTP는 안정적인 전송이 가능한 TCP를 사용하는데, 이 TCP로 클라이언트와 연결을 맺는다. 클라이언트가 80번 포트(HTTP는 80번 포트 사용)를 통한 TCP 연결을 생성하고 서버가 이 연결을 승인하면, 브라우저와 웹 서버, 즉 클라이언트와 서버가 필요한 HTTP 메시지를 교환하고, 교환이 완료되면 연결을 종료하는 과정으로 통신이 이루어진다. 이때, 서버의 부담을 줄이기 위하여, 서버는 과거에 있었던 요청에 대한 정보를 유지 및 관리하지 않고, 사용자에 대한 ..

Knapsack Problem(배낭 문제)란, 도둑이 배낭에 담을 수 있는 물건의 무게에 한계가 있는 상황에서 각 물건의 가치가 다를 때, 물건의 가치를 최대로 만드는 문제로, Fractional과 0-1의 두 가지 방식이 있다. Fractional Knapsack Problem은 같은 상황에 대해 물건을 일정 비율만큼 훔칠 수 있는 경우로, 물건을 분할해서 가져갈 수 있는 문제이고, 0-1 Knapsack Problem은 하나의 물건에 대해 나눌 수 없고, 훔치거나 훔치지 않는 선택만을 할 수 있는 경우의 문제이다. Fractional Knapsack Problem은 각 물건을 원하는대로 가져갈 수 있기 때문에 단위 무게당 가치(가치/무게)를 구해서 그 값이 높은 순서대로 배낭을 채운다. 그래서 물건을..

활동 선택 문제는 시작 시간과 종료 시간이 주어진 다양한 활동 중에서 가장 많은 활동을 할 수 있는 활동의 집합을 고르는 문제이다. 활동의 정보를 보고 활동 간의 관계를 계산하여 가장 긴 활동들의 sequence를 구한다. 이 문제는 순간의 최적을 전체의 최적이라고 판단하는 그리디 알고리즘으로 구할 수 있는데, 가장 빨리 끝나는 (=종료 시간이 가장 빠른) 활동을 선택하여, 남는 시간이 가장 크도록 하는 활동들을 최적이라고 판단하여 선택한다. 그리디 알고리즘의 개념은 아래 게시물에 잘 설명되어 있다. 가장 짧은 활동, 가장 덜 겹치는 활동, 일찍 시작하는 활동을 선택할 경우 반례가 존재해 문제 전체로 봤을 때 최적의 해를 구할 수 없게 되기 때문이다. 수열 S = {1, 2, … , n}을 종료 시간 순..

그리디 알고리즘은 현재 가장 좋아보이는 선택을 하는 알고리즘이다. 다시 말해, 순간마다 최적의 선택을 진행하여 적합한 해를 도출하며, 그것이 전체의 최적이 될 것이라고 생각한다. 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성되며, 이를 최적 부분 구조라고 한다. 이러한 특성으로 인해, 그리디 알고리즘은 장점과 단점이 뚜렷한 알고리즘이다. 장점은 각 부분에서 최적의 선택을 진행하기 때문에 계산 속도가 빠르다. 단점은 부분에서만 최적을 계산하기 때문에 전체적으로 봤을 떄 최적이 아닐 가능성이 있어 도출된 해가 최적임을 보장하지 않는다. 그리디 알고리즘은 Greedy-Choice Property(탐욕적 선택 속성)과 Optimal Substructure(최적 부분 구조)를 만족하는 문제를..

Problem A number of students are members of a club that travels annually to exotic locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven. The group agrees in advance to share expenses equally, but it is not practical to have them share every expense as it occurs. So individu..

연쇄행렬곱셈 문제는 행렬곱의 횟수를 최소로 할 때의 최적 답안과 그 횟수를 구하는 문제이다. 행렬을 곱할 때에는 한 번에 두 행렬끼리만 곱할 수 있는데, 여러 행렬을 곱해 답을 구하는 과정에서, 어떠한 행렬쌍을 먼저 곱하는지에 따라 연산의 횟수가 달라지게 된다. 예를 들어 A는 2x3 행렬, B는 3x5 행렬, C는 5x2 행렬이라고 가정했을 때, ((A B) C)는 50회, (A (B C))는 42회가 나오는 것처럼 괄호의 위치에 따라 연산 횟수가 다르게 나온다. 따라서, 가장 적은 횟수로 최종 행렬곱을 구하는 방법을 구하는 것이 연쇄 행렬 곱셈이다. 이 계산을 하기 위해 일일이 하나하나 곱해가면서 값을 비교해 최솟값을 구한다면, 위에 보이는 식과 같이 기하급수적으로 값이 (시간복잡도가) 커지게 된다...