기록하는 습관 "기습"

주소 변환 논리는 주소는 호스트나 라우터가 사용하는 32비트 길이의 전세계적으로 유일한 주소다. 물리주소는 로컬 네트워크에서 만 유효한 주소이다. 하드웨어로 구현된다. 패킷을 호스트나 라우터로 전달하기 위해 논리 및 물리 주소가 필요하며, 논리 주소를 물리 주소로 변환하거나 그 반대의 행위가 필요하다. 정적 변환 : 논리와 물리 주소 연관 테이블을 생성하여 필요 시 테이블에서 검색해 찾아내는 것. 동적 변환 : 논리나 물리 주소 중 하나만 알면 프로토콜을 이용해 다른 하나를 알아내는 것이다. ARP는 논리에서 물리 주소로 변환하는 것이고 RARP는 그 반대이나 현재는 사용하지 않는다. ARP는 논리주소를 물리주소로 변환시킨다고 하였다. 이는 네트워크층에 ICMP와 함께 자리해 있다. ARP 요청은 브로드..

근거리 통신망 LAN 지역적으로 제한된 지역에서 독립적인 장치들이 서로 통신할 수 있는 데이터 통신 시스템을 일컫는다. 오늘날 LAN들은 대부분 WAN(광역 통신망)이나 인터넷에 연결한다. IEEE 표준 이더넷 무선 통신을 전제로 해서 단일 주파수 통신을 하는 무전기처럼 타인에게 이야기하는 동안은 그 상대방은 수신만 가능하다. CSMA/CD(충돌검출)방식을 사용한다. 논리 링크 제어 LLC : 흐름제어, 오류제어, 프레임 생성 일부분의 역할을 처리하는 부계층이다. 서로 다른 LAN 사이에 연결성을 제공하기도 한다. 매체 접근 제어 MAC : 프레임을 만드는 기능의 일부나 토큰에 대한 방식을 정의하는 기능을 담당한다. 이더넷 II 프레임 형식 프레임은 다음과 같은 6개 필드로 구성된다. 프리엠블 목적지 주..

NP 완비 NP-complete 요약하자면, 현실적인 시간 내에 답을 얻을 수 있는 해법이 존재하는 것을 말한다. 여기서 이제까지 다룬 모든 알고리즘은 다항식 시간, 즉 입력 크기가 n일 때 최악의 경우에도 수행시간이 O(n^k)의 시간이 걸리는 알고리즘들이었다. 하지만 모든 문제를 컴퓨터로 다항식 시간에 풀 수 있지 않다. 정확히는 풀 수 있으나 현실적인 시간 내에 풀 수 없는 문제가 있고, 아무리 시간이 주어져도 풀 수 없는 문제가 존재한다. 간혹 들어보는 표현 중에 "슈퍼 컴퓨터로 몇 십년 이상 걸리는 문제"가 그것이다. P 는 polynomial이란 의미로, 문제가 주어졌을 때, 대답을 다항식 시간에 할 수 있는 문제이다. NP는 yes라는 근거만 주어지면 다항식 시간에 풀 수 있는 문제이다. N..

연결형 서비스 패킷을 보내기 전, 발신지의 네트워크층 프로토콜은 목적지의 프로토콜과 연결을 설정한다. (네트워크층의 경로설정) 연결 설정 이후, 패킷들을 순서대로 하나씩 전송한다. 모든 패킷을 전송하고 나면 연결이 해제된다. 비연결형 서비스 각 패킷이 독립적으로 처리되며 패킷 사이에 아무런 연관이 없다. 물론 목적지가 같더라도 다른 경로도 전달될 수도 있다. 패킷 포워딩 패킷 포워딩이란 패킷을 전달하는 방법을 의미한다. 포워딩 자체는 뒤에서 살펴보도록 하자. 네트워크층은 패킷이 목적지까지 갈 수 있도록 경로를 지정하여 관리한다. IP패킷을 목적지까지 보내기 위해 경로를 지정하는 방법이 필요한데, 다음 두 종류가 있다. 직접 전달 : 목적지가 전달자와 같은 네트워크에 위치한 호스트에게 전달하는 것을 의미한..

원시적인 naive 매칭 문자열 하나하나에 패턴문자열을 대조해보는 방법으로, O(mn)의 수행시간을 갖는다. 다만 이전에 비교했던 불일치 건에 대한 사실을 전혀 활용하지 못하기에 비효율적이다. Rabin-Karp 알고리즘 문자열 패턴을 수치화하여 문자열 비교를 수치비교로 대신한다. 수치화 방법은 다음과 같다. 가능한 문자 집합의 크기에 따라 진수가 결정된다. 만약 A = {a,b,c,d,e}이면, |A| = 5이다. 여기서 문자열 ad를 수치화한다고 했을 때 수치는 다음과 같다. 0*5^1 + 3*5^0 = 4 (4가 문자열 ad의 수치화, 맨앞의 숫자는 알파벳의 순서) 문자열 수치화로 문자열 매칭을 수행하려면 다음과 같은 문제점을 해결해야 한다. 수치화 작업의 부담 보통 하나의 문자열들을 일일이 계산하..

그리디 알고리즘 눈앞의 이익만 우선 추구하는 알고리즘을 총칭한다. 최적해를 찾을 수 있으면 찾지만, 없다면 그런대로 괜찮은 해를 찾아내는 것이 목표다. 이 때문에 대부분 최적해를 보장하지 못하지만 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘으로 최적해가 보장되는 않는 예는 다음과 같다. 이진트리 최적합 경로 찾기 동전 바꾸기 배낭 문제 최적해가 보장되는 예는 다음과 같다. 최소 신장 트리 : prim, kruskal 최단 경로 : 다익스트라 회의실 배정 문제 여기서 몇가지를 뽑아서 설명하겠다. 동전 바꾸기 동전을 모아서 특정 액수를 만들되 동전의 개수를 최소로 하는 문제다. 다만 이 문제는 모든 동전의 액면이 일반적인 화폐의 유통과 같았을 때, 즉 500원, 100원, 50원, 10원일 때 그..

그래프는 정점 vertex와 간선 edge로 사물과 현상을 표현한 것이다. 이전에 다뤘기에 세세한 것은 넘어가겠다. 그래프의 표현 그래프를 표현하는 방법 중에는 인접 행렬, 인접 리스트, 인접 배열, 인접 해시테이블이 있다. 인접행렬은 간선 수 이상의 공간을 차지하고, 인접리스트는 특정 간선 존재 여부를 검사하는 데에 오래 걸린다. 이 두 단점을 커버할 수 있는 표현은 인접 배열이다. 인접배열은 정점 N개일 때 N개의 인접배열로 표현하는 것이다. 즉, 인접한 정점의 갯수만큼 배열을 또 생성한다. 인접리스트를 배열로 표현한다면 이해가 쉬울 것이다. 이때 간선 존재 여부의 수행시간은 O(log k)이다. 인접 해시테이블은 각 정점마다 인접배열을 두는 대신 하나의 해시 테이블을 사용하는 것이다. 인접한 정점이..

동적 프로그래밍 큰 문제에는 닮은 꼴의 작은 문제가 깃들기도 한다. 이를 해결한 것이 재귀적 알고리즘인데, 이 알고리즘은 잘 쓰면 효율적인 보약이지만 잘못 쓰면 치명적인 맹독이다. 재귀적 알고리즘 자체가 심한 중복 호출을 불러올 수 있기 때문이다. 이를 해결하기 위한 방법이 동적 프로그래밍이다. 심한 중복 호출이 일어나는 경우는 피보나치 수열과 행렬곱셈 최적순서 구하기가 있다. 이에 대해 알아보자. 피보나치 수 구하기 피보나치 수열의 정의는 다음과 같다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 이를 프로그램으로 구현하면 fib(n) { if (n = 1 or n = 2) then return 1; else return (fib(n-1) +fib(n-2)); } 여기서 수가 ..

집합의 처리 여기서 다루는 집합은 상호배타적 집합 disjoint set뿐이므로 교집합 연산은 다루지 않는다. 상호배타적 집합을 다루기 위해 필요한 연산은 다음과 같다. makeSet(x) : 원소 x로만 이뤄진 집합을 생성한다. findSet(x) : 원소 x가 속한 집합을 알아낸다. union(x, y) : x와 y가 속한 집합의 합집합을 구한다. 집합의 연산은 위와 같다. 다음은 위 집합의 처리를 할 때 가장 근본적으로 고려해야 할 집합의 구현방법이다. 연결리스트로 구현 : makeSet, findSet은 O(1), union은 O(log n)이 소요된다. tree로 구현 : makeSet, findSet, union에서 O(m)의 시간이 소요된다. 가장 효율적이다. 연결리스트로 집합 처리 각 원소..

인공신경망 인공신경망은 인간의 두뇌와 신경 시스템을 닮은 정보처리소자이다. 연결주의 기법으로써 뉴런들을 연결하여 문제해결 모델을 만든다. 인공 뉴런의 구조는 위와 같다. 위의 변형함수는 여러 가지가 있는데 하드리미터, 임계값, 시그모이드가 그것이다. 임계값은 어느 값을 기준으로 0과 1을 나누고, 시그모이드는 0과 1의 사이값을 취한다고 보면 된다. 하드리미터는 특정값보다 크면 1, 작으면 -1로 한다. 인공 신경망에서의 학습과정은 다음과 같다. 입력 값을 이용하여 인공 뉴런의 출력 값을 계산 인공 뉴런이 계산한 출력 값과 사용자가 기대하는 출력 값을 비교 기대하는 출력 값을 생성할 수 있도록 가중치 조절 이러한 인공신경망을 보여주는 대표적인 예가 단층인공뉴론 퍼셉트론이다. 퍼셉트론의 학습과정은 다음과 ..