본문 바로가기

Computer Science

(45)
<네트워크> 네트워크 계층(1) 1. 네트워크 계층의 역할 * 네트워크 간의 연결 구조 - 다른 네트워크에 있는 목적지로 데이터를 전달하려면 네트워크 계층의 기술이 필요하다. - 지난 장에서 다룬 데이터 링크 계층에서는 이더넷 규칙을 기반으로 데이터 전송을 담당했다. 따라서 같은 네트워크에 있는 컴퓨터로만 전송이 가능했다. - 네트워크 A~C와 같이 네트워크 간 통신을 가능하게 하는 것이 네트워크 계층의 역할이다. 이 때 라우터라는 네트워크 장비가 필요하다. - 라우터는 해당 목적지까지 어떤 경로로 가는 것이 좋을지를 알려준다. - IP 주소: 랜에서는 MAC주소만으로 목적지를 판단했으나 네트워크 간에는 네트워크를 식별할 수 있는 별도의 주소가 필요하다. - 라우팅 : 목적지 IP 주소까지 어떤 경로로 데이터를 보낼지 결정하는 것 - ..
<네트워크> 데이터 링크 계층 1. 데이터 링크 계층의 역할과 이더넷 * 이더넷 - 랜에서 데이터를 주고 받으려면 두 번째 계층인 데이터 링크 계층의 기술이 필요하다. - 데이터 링크 계층은 네트워크 장비 간에 신호를 주고 받는 규칙을 정하는데, 일반적으로 많이 사용되는 규칙이 이더넷이다. 쉽게 말해 이더넷은 네트워크를 구성하는 방식 중 하나의 방법이며, 오늘날 LAN을 대표하는 가장 대중적인 기술이다. - 앞서 봤었던 허브를 생각해보자. 데이터를 받으면 연결된 모든 컴퓨터에 보내버린다고 했었다. 이런 경우를 대비해서 규칙이 있다. 목적지 정보를 추가해서 보내는 것인데, 이렇게 하면 다른 컴퓨터는 데이터를 받더라도 무시하게 된다. - 충돌 : 컴퓨터 여러 대가 동시에 데이터를 보내면 데이터들이 서로 부딪히는 것 - 충돌을 피하기 위해..
<자료구조> 우선순위 큐 1. 우선순위 큐(Priority Queue) * 우선순위 큐 - 우선순위 큐는 큐와 달리 우선순위가 높은 것부터 Dequeue를 시키는 자료구조를 의미한다. - 이 장에서는 파이썬 모듈 heapq를 이용하여 구현해보자. * 힙(heap) - 힙은 완전이진트리(complete binary tree)를 기본으로 하는 자료구조이다. - 힙은 부모-자식 노드의 키값 대소 관계가 일정하게 유지된다. - 최대 힙 : 자식 노드의 키 값보다 부모 노드의 키 값이 항상 크다. - 최소 힙 : 자식 노드의 키 값보다 부모 노드의 키 값이 항상 작다. - 참고로 파이썬에서 heapq모듈은 최소 힙 자료구조만 제공한다. 2. 구현하기 * 생성 - 먼저 모듈을 불러와야 한다. import heapq heap = [] - 모..
<네트워크> 물리 계층 1. 물리 계층의 역할과 랜 구조 * 전기 신호 - OSI 모델의 1계층인 물리 계층은 0과 1만으로 이루어진 비트열을 전기 신호로 변환한다. - 전기 신호의 종류에는 아날로그 신호와 디지털 신호가 있다. - 아날로그 신호는 물결 모양이며, 전화회선이나 라디오 방송에 사용된다. - 디지털 신호는 막대모양이다. 비트열을 위와 같이 바꿔서 네트워크를 통해 전송하고, 수신 측 컴퓨터는 이를 다시 0과 1의 비트열 데이터로 변환한다. * 랜카드 - 컴퓨터는 네트워크를 통해 데이터를 송수신할 수 있도록 랜 카드가 메인보드에 포함되어 있는 내장형 랜 카드나 별도의 랜 카드를 가지고 있다. 2. 케이블의 종류와 구조 * 트위스트 페어 케이블 - 전송매체 : 데이터가 흐르는 물리적인 선로로 유선과 무선으로 나뉜다. -..
<네트워크> 네트워크 기본규칙 1. 네트워크의 규칙 * 프로토콜 - 프로토콜은 원래 외교상의 언어로써 국가간의 약속을 의미했다. 여러 나라와 각 나라의 언어로는 대화가 불가능한데 이럴 때 만약 영어로 하자고 규칙을 정한다면 대화가 가능해질 것이다. - CS에서 프로토콜은 시스템끼리 통신을 원활하게 하도록 해주는 절차나 규칙등을 의미한다. 간단하게 통신하기 위한 규칙이라고 보자. - 네트워크 용어에서 약자로 나오는 P는 대부분이 프로토콜이다. 2. OSI모델과 TCP/IP 모델 * OSI모델 - ISO에서 네트워크 기술의 기본이 되는 모델인 OSI모델을 표준 규격으로 제정하였다. - 통신 시 데이터는 7계층인 응용계층부터 차례대로 아래로 전달된다. - 송수신 측면에서 보면 다음과 같이 데이터를 주고 받는다. * TCP/IP 모델 - T..
<네트워크> 네트워크 구조와 LAN&WAN 1. 네트워크의 구조 * 네트워크 - CS에서 네트워크란 2대 이상의 컴퓨터가 연결되어 통신 가능한 것을 의미한다. 네트워크를 통해 컴퓨터는 데이터를 서로 주고 받는다. - 인터넷 : TCP/IP 프로토콜을 사용하는 세계 최대 규모의 컴퓨터 통신 네트워크 * 패킷 - 패킷은 네트워크를 통해 전송되는 데이터 조각을 의미한다. - 큰 데이터가 있더라도 작게 나누어 보내는게 규칙이다. 만약 큰 상태 그대로 보낸다면 네트워크의 대역폭을 많이 차지하여 다른 패킷 흐름을 방해할 수 있다. 좁은 도로에 큰 트럭들이 천천히 다니고 있다고 생각해보라. - 패킷이 도착하고 원래 데이터로 되돌리는 작업이 필요한데, 이를 위해서 패킷에 순서를 붙여서 전송한다. - 패킷은 전송한 순서대로 도착하지 않는다. 그러나 부여받는 번호..
<자료구조> 해시 테이블과 트라이 * 해시 테이블 - 연결리스트와 트리구조에서 검색시간이 O(n)과 O(log n)이 걸렸다. 그러나 컴퓨터 공학자들은 이 시간을 더 단축시켜서 O(1)에 가깝게 만들기를 원했다. - 위를 가능하게 해주는 구조 중 하나가 바로 해시 테이블이다. - 해시테이블은 연결리스트를 원소로 가지는 배열이다. - 이름표를 바구니에 담는다고 가정하자. 단순히 바구니 하나에 여러 이름표를 담으면 사람들이 찾는 데 오랜 시간이 걸릴 것이다. - 그렇다면 바구니를 여러개로 한다면 어떨까. 이 때 바구니를 무슨 기준으로 나누는 것이 좋을까. - 이 때의 기준이 해시 함수이다. 이름표이므로 해시함수를 이름의 가장 첫 글자로 시도해보자. 알파벳이라면 총 16개의 포인터들이 생기고, 그 알파벳은 각각 연결리스트를 가리키게 된다. -..
<자료구조> 트리구조 * 연결리스트의 장단점 - 연결리스트는 배열과 달리 새로운 값을 추가하면 메모리를 추가하지 않아도 되었다. - 그러나 배열과 달리 임의 접근이 불가능하다. - 위와 같은 단점은 값의 추가, 검색에서 손실을 가져온다. 추가와 검색을 위해 연결리스트의 각 node를 하나하나 이동해야하기 때문이다. - 배열의 경우에는 정렬만 되어 있다면 임의 접근이 가능하여 이진검색을 이용하면 O(log n)의 실행시간을 갖는다. 그러나 위와 같은 단점때문에 연결리스트는 O(n)이 된다. * 트리구조의 등장 - 트리는 연결리스트를 기반으로 한 새로운 데이터 구조이다. - 연결리스트에서 노드의 연결이 1차원이었다면 트리에서의 노드의 연결은 2차원이다. - 위에서 언급되었던 단점을 해결한 '이진 검색 트리' 를 살펴보자. - 가..
<자료구조> 연결리스트와 노드 * 연결리스트 소개 - 배열에선 각 인덱스 값들이 메모리 상에서 연이어 저장되어있다. 그렇다면 배열에 새로운 값을 추가하려면 어떻게 해야 할까 - 기존 배열 바로 뒤에 다른 값이 있을 수 있으므로 배열의 길이를 늘리려면 새로운 메모리를 할당해서 값을 하나하나 복사하여 옮겨야한다. - 위의 방식은 너무 번거롭다. 각 값을 메모리의 다른 곳에 저장하더라도 배열처럼 사용할 수 있다면 어떨까. 각 값에 다음 값의 메모리 주소를 기억하게 하는 것이다. 이를 연결리스트라 한다. (Linked List) - 이제 첫 값인 1은 2의 주소를 갖고, 2는 3의주소를, 3은 Null을 갖게 된다. * 노드 - 연결리스트를 C언어 코드로 구현하면 다음과 같은 구조체로 정의한다. typedef struct node { int..
<컴퓨터 구조> 메모리 교환, 스택, 힙 1. 메모리 교환 * 메모리 교환 - 변수 두 개의 값을 서로 바꾸는 함수를 만들어 보자. - 먼저 변수 두 개의 값을 바꾸려면 임시 변수(tmp)를 만들어서 넣어가며 바꿔야 한다. - 이를 구현하면 다음과 같을 것이다. #include void swap(int a, int b); int main(void) { int x = 1; int y = 2; printf("x is %i, y is %i\n", x, y); // x is 1, y is 2 swap(x, y); printf("x is %i, y is %i\n", x, y); // x is 1, y is 2 } void swap(int a, int b) { int tmp = a; a = b; b = tmp; } - 함수 내에서 값을 교환하는 것 같지만..