Computer-Sience38 [Algorithm] 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘 다익스트라 알고리즘은 1959년 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라가 개발한 최단 경로 탐색 알고리즘이다. 이 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 데 사용되며, 실 생활에 사용되는 예시로는 최단 거리 알고리즘답게 내비게이션 시스템, 네트워크 라우팅 등과 같은 곳에 사용된다. 위 예제는 1번 노드(a)에서 5번 노드(b)로 가는 최단 거리를 구하는 과정을 나타낸 것이다. 기준이 되는 노드에서 방문하지 않은 각 노드 간의 거리를 계산하고, 이를 통하여 가장 낮은 거리로 계산되는 각 노도의 경로를 모두 계산하게 되는 것이다. 예제 아래는 heapq를 활용하여, 위의 예제를 다익스트라 알고리즘을 코드로 구현한 것이다. import hea.. 2024. 11. 27. [CS] NTP(Network Time Protocol) NTP 시간은 현대 컴퓨팅 시스템에서 가장 중요한 요소 중 하나이며 분산 시스템, 로그 분석 등 많은 영역에서 정확한 시간 동기화가 필수적으로 요구된다. 분산된 환경에서의 시간 동기화를 가능하게 하는 것이 바로 NTP(Network Time Protocol)이다. NTP는 컴퓨터 시스템 간의 시간 동기화를 위하여 개발이 된 네트워킹 프로토콜이다.. 데이비드 밀스(David L. Mills)가 1985년에 개발한 이후, 현재는 널리 사용되는 인터넷 프로토콜 중 하나이다. 주로 UDP 포트 123을 사용하며, Miliseconds 단위의 정확도로 시간을 동기화할 수 있다. 동작 원리 NTP는 클라이언트와 동기화 서버 간의 패킷을 교환하여 시간을 동기화한다. 아래의 4 단계를 거쳐서 동기화가 이루어진다... 2024. 11. 19. [Network] ICMP / IGMP ICMP (Internet Control Message Protocol) ICMP는 IP 네트워크의 진단과 제어를 담당하는 프로토콜이다. OSI 모델의 네트워크 계층(Layer 3)에서 작동하며, IP 패킷의 전송 과정에서 아래와 같은 역할을 수행한다. 오류 메시지 전달: IP 패킷 전송 중 발생하는 다양한 오류 상황을 보고네트워크 상태 진단: 호스트 간의 연결성과 라우팅 경로 확인네트워크 디버깅: 네트워크 문제 해결을 위한 진단 정보 제공라우팅 최적화: 더 효율적인 경로 정보를 호스트에게 제공 특징오류 보고: 패킷 전송 실패, 경로 문제 등을 알림네트워크 진단: ping, traceroute 등의 도구를 통한 연결성 테스트흐름 제어: 패킷의 속도 조절 및 혼잡 제어에 관여 IGMP (Interne.. 2024. 11. 13. [Network] MTU(Maximum Transmission Unit) MTU MTU는 어떤 데이터링크에서 하나의 프레임 또는 패킷에 담아 운반 가능한 최대 크기를 의미한다. 해당 예시로 지하도로나 터널의 높이 제한처럼 생각할 수 있으며, 높이 제한보다 높은 차량은 못지나가는 것처럼 네트워크의 MTU보다 큰 패킷은 일반적으로 해당 네트워크를 통과하지 못한다. 하지만 MTU보다 큰 데이터 패킷은 작은 조각으로 잘라 MTU에 맞출 수 있고, 이 과정을 분할(Segmentation)이라고 칭한다. 그리고 분할된 패킷은 목적지에서 조립된다. MTU의 단위는 Byte이며, 보통 MTU 사이즈는 매체마다 차이가 존재하며 Ethernet 구간의 경우, 최대 MTU 크기는 1,500bytes이다. 여기서 IP header로 20bytes, TCP header로 20bytes를 사.. 2024. 11. 12. [Data-Structure] Hash Table(해시 테이블) 1. Hash Table(해시 테이블) 해시 테이블은 (Key, Value) 쌍으로 데이터를 저장하는 자료구조이며, 일반적으로 O(1)의 시간복잡도로 빠른 속도로 데이터를 저장하고 조회할 수 있다. - 기본 구조해시 테이블의 기본 구조는 아래와 같이 이루어져 있다. Key가 되는 데이터를 해시 함수에 입력하면 인덱스가 생성이 되고, 해당 인덱스가 가리키는 버킷에 데이터를 저장하는 것이다. 인덱스 사용하기 때문에, 평균적으로 O(1)의 시간을 가지게 된다는 특징이 있다. 버킷(Bucket): 실제 데이터가 저장되는 공간해시 함수(Hash Function): Key를 고정된 길이의 해시값으로 변환하는 함수인덱스(Index): 해시값을 기반으로 계산된 버킷의 주소 2. 해시 함수(Hash Func.. 2024. 11. 11. [Network] AS(Autonomous System) AS(autonomous system) / 자율 시스템 : 단일 관리 엔티티(네트워크 관리자)에 의해 독립적으로 운영되는 라우터의 집단을 의미한다.예시로 SKT나 KT와 같은 ISP에서 제공하는 네트워크나, 기업 내부에서 구축하여 사용하는 내부 네트워크를 들 수 있다. AS의 특징 :AS는 중복되지 않는 고유한 번호(ASN)를 가진다.각 AS는 자체 라우팅 규칙이 존재하며, 이를 기반으로 네트워크를 관리한다. AS는 내부와 외부를 구분하여, AS 내부 라우팅 정보 전달을 위해 사용하는 프로토콜을 IRP(Interior Router Protocol), AS의 외부의 다른 AS와 라우팅 정보 전달을 위해 사용하는 프로토콜을 ERP(Exterior Router Protocol)라고 한다. AS의.. 2024. 7. 31. 이전 1 2 3 4 ··· 7 다음
