정용이의 놀이동산

개요 URL은 인터넷의 리소스를 가리키는 표준 이름입니다. URL은 리소스가 어디에 있고, 어떻게 접근할 수 있는지 알려줍니다. URL 문법 대부분의 URL 스킴의 문법은 일반적으로 9개 부분으로 나누어져 있습니다. 스킴://사용자 이름:비밀번호@호스트:포트/경로;파라미터?질의#프래그먼트 URL의 가장 중요한 3가지 컴포넌트는 스킴, 호스트, 경로입니다. 컴포넌트 스킴 리소스 접근 시 사용할 프로토콜을 나타냄 기본값 X 사용자 이름 몇몇 스킴은 리소스 접근 시 사용자 이름을 요구함 기본값 anonymous 비밀번호 사용자 비밀번호 사용자 이름에 :을 붙여서 기술함 기본값 이메일 주소 호스트 리소스를 호스팅하는 서버의 호스트명/주소 기본값 X 포트 호스트가 열어놓은 포트번호 많은 스킴(프로토콜)이 기본 포..

개요 펜윅 트리(Fenwick Tree)라고도 한다. 누적 합 배열의 동적 자료구조이다. 이름은 트리이지만 배열로 표현한다. 모든 배열의 인덱스가 1부터 시작한다고 가정한다. 그래야 구현하기가 좀 더 쉽다. 시간복잡도가 O(log n)인 2가지 연산을 제공한다. update(int k, int diff) : 배열의 원소 갱신 sum(int k) : 1번 원소부터 k번 원소까지의 구간 합 계산 p(k) : k의 약수 중에서 가장 큰 2의 거듭제곱. p(k) = sum(k - p(k) + 1, k) 위치 k에서 끝나면서 그 길이가 p(k)인 구간의 합 BIT를 사용하면 어떤 sum(1, k)의 값도 O(log n)에 구할 수 있다. 배열의 원소를 갱신하면 BIT에서 해당 원소가 포함되어 있는 값도 갱신해야 ..

개요 집합의 묶음을 관리하는 자료구조이다. 집합은 서로소 집합(Disjoint Set)이고, 하나의 원소는 오직 하나의 집합에 속한다. 집합마다 하나의 원소가 해당 집합의 대푯값이 되고, 나머지 원소에서 대표 원소로 가는 경로가 존재한다. 유니온-파인드 자료구조는 O(Log n)의 시간복잡도를 가진 2가지 메서드를 제공한다. unite(a, b) : a와 b가 속한 각각의 집합을 하나로 합친다. find(x) : x원소가 속한 집합의 대푯값을 반환한다. 집합을 합칠 때, 원소가 더 적은 집합의 대푯값을 원소가 더 많은 집합의 대푯값으로 연결함으로써 효율적인 unite 연산을 수행할 수 있다. 구현 유니온-파인드는 배열을 사용해서 쉽게 구현할 수 있다. 배열은 각 원소에 대해서 경로상의 다음 원소를 저장하..

노드 간 경로 프로토콜 노드 : 호스트, 라우터, 스위치, WIFI AP ... 링크 : 노드 간 통신 채널 링크 계층의 서비스 프레임화 : 전송 전 데이터그램을 링크 계층 프레임으로 캡슐화함 링크 접속 : 매체 접속 제어 프로토콜로 링크 상 프레임 전송 규칙 명시 신뢰적 전달 : 링크 계층 프로토콜이 신뢰성 있는 전달을 제공할 경우 데이터그램은 링크 상에서 오류없이 전송됨 오류 검출과 오류 정정 : 전송할 필요가 없는 비트 오류가 있는 데이터그램을 검출하고 정정함 링크 계층 구현 위치 네트워크 인터페이스 카드(Network Interface Card, NIC) == 네트워크 어댑터 오류 검출, 오류 정정 비트 수준의 오류 검출과 오류 정정 제공 패리티 검사 체크섬 순환중복검사 --> 오늘날에 주로 사용..

송신 호스트 --> 수신 호스트로 패킷 전송 주요 기능 포워딩(전달) 라우터에서 적절한 출력 링크로 패킷 이동 매우 짧은 시간동안 이뤄짐 --> 하드웨어에서 실행 라우팅 패킷의 경로를 결정 경로 계산 알고리즘 --> 라우팅 알고리즘 네트워크 전반에 걸쳐서 출발지 - 목적지까지 데이터그램의 경로 결정 상대적으로 긴 시간 --> 대개 소프트웨어에서 실행 포워딩 테이블 : 라우터는 도착하는 패킷 헤더의 필드값을 조사해서 패킷을 포워딩함 네트워크 서비스 모델 호스트 간 패킷 전송 특성을 정의 보장된 전달 지연 제한시간 이내 보장된 전달 순서화 패킷 전달 최소 대역폭 보장 보안 최선형 서비스 제공 패킷 스위치 링크 계층 스위치 : 링크 계층 프레임 필드값에 근거해서 포워딩 결정 라우터 : 네트워크 계층 필드값에 ..

트랜스포트 계층 프로토콜은 서로 다른 호스트에서 동작하는 프로세스 간 논리적 통신 제공 네트워크 라우터 X, 종단 시스템에서 구축됨 데이터가 segment라는 트랜스포트 계층 패킷으로 캡슐화됨 UDP, TCP ... 트랜스포트 계층과 네트워크 계층 트랜스포트 계층 --> 프로세스 간 논리적 통신 제공 네트워크 계층 --> 호스트 간 논리적 통신 제공 트랜스포트 계층은 네트워크 프로토콜이 비신뢰적이어도 신뢰적인 통신 제공 + 보안 제공 네트워크 계층의 IP : 비신뢰적인 서비스 최선형 전달 서비스 제공 세그먼트의 순서 보장 X 데이터의 무결성 보장 X 트랜스포트 계층은 호스트 간 전달 --> 프로세스 간 전달로 확장하는 트랜스포트 다중화와 역다중화 제공 다중화와 역다중화 애플리케이션은 소켓을 통해서 트랜스..

네트워크 애플리케이션 종단 시스템에서 통신하는 프로그램 네트워크 애플리케이션 구조 클라이언트-서버 클라이언트 : 서버에 요청을 발신하는 호스트 서버 : 항상 켜져있음, 고정 IP, 데이터센터를 구축해서 가상 서버 생성함 P2P 서버에 거의 의존하지 않음 애플리케이션은 peer라는 연결된 호스트 쌍이 통신함 peer는 데스크톱, 랩톱 등 자가 확장성이 있음 프로세스 간 통신 운영체제 관점에서 실제로 통신하는 것은 프로그램이 아닌, 프로세스 프로세스는 메시지를 교환함으로써 종단 시스템간 통신함 클라이언트-서버 클라이언트 : 통신 세션에서 통신을 초기화하는 프로세스 서버 : 세션을 시작하기 위해 접속을 기다리는 프로세스 프로세스는 소켓을 통해 네트워크로 메시지를 송수신함 프로세스 --> 집, 소켓 --> 출입..

구성요소 호스트(종단)의 집합 호스트는 통신링크와 패킷 스위치로 연결 패킷 = 세그먼트+헤더 종단 간 송신은 패킷으로 이뤄짐 패킷 스위치 --> 라우터, 계층 스위치 종단은 ISP로 인터넷에 접속 인터넷에서 여러 프로토콜 수행. 특히 인터넷 프로토콜(TCP/IP) 서비스 분산 애플리케이션들이 수행되는 곳 애플리케이션은 소켓 인터페이스로 통신 네트워크 프로토콜 둘 이상 개체간 통신을 위한 규약 메시지 포맷, 순서, 행동 등 정의 네트워크 변두리 호스트들의 집합 호스트는 서버와 클라이언트로 구분할 수 있음 접속 네트워크 가정 DSL(Digital Subscriber Line) - 집전화(텔코) 기반 케이블 - 케이블 TV 기반 FTTH - 지역 중앙국(Central Office)에서 집까지 광섬유 경로를 제..

배열(Array) 같은 자료형의 데이터를 여러개 만들 때 사용 배열을 이용하면 연속적인 메모리 공간에 데이터들을 저장할 수 있음 각 데이터에는 인덱스를 이용하여 접근 ADT Array 객체 : 쌍의 집합 연산 : create(n) : n개의 요소를 저장할 수 있는 배열 get(A, i) : 배열 A의 i번째 요소 반환 set(A, i, v) : 배열 A의 i번째 위치에 v 저장 구조체(Structure) 배열 : 같은 타입의 데이터 모임 구조체 : 다른 타입의 데이터 묶음 struct를 이용하여 형성 예제 형식 struct 구조체이름 { int a; float b[10]; char name[20]; }; 구조체 변수 생성 struct 구조체이름 구조체변수; 구조체 타입 선언 typedef struct {..

2.1 순환 소개 순환 : 어떤 알고리즘이나 함수가 자기 자신을 호풀하여 문제를 해결하는 기법 순환 알고리즘 구조 순환을 멈추는 부분 + 순환 호출을 하는 부분 만약, 호출을 멈추는 부분이 없다면 int factorial(int n) { printf("factorial (%d)\n",n); //if(n 순환이 적절함 ex) 순환적인 문제들 보통 반복과 순환은 문제해결능력이 동등, 어떤 한 문제에 두 알고리즘을 모두 사용 가능 ex) 순환 -> 반복, 반복 -> 순환 순환은 반복에 비해 알고리즘을 명확하게 간결하게 표현 가능 순환은 매구간 함수 호출 --> 보통 반복에 비해 수행속도가 느릴 수 있음 순환 원리 순환은 분할정복(Divide & Conquer)을 구현 --> 문제의 일부분을 해결한 뒤, 문제의..