https://www.acmicpc.net/problem/17472구현 + MST 섬의 위치가 격자판 모양으로 주어질 때, 격자판 모양으로부터 그래프를 직접 정의하고, 그 그래프에 대해 MST를 찾으면 됩니다.이런 복잡한 문제는 어떤 것들을 구현해야 하는지 잘 나눠서 생각하면 구현하기 좋습니다.(그래도 이 문제는 구현이 엄청 복잡한 편까지는 아닙니다.) 먼저 섬부터 찾아보겠습니다.섬을 찾는다는 것은 격자판을 그대로 그래프로 보았을 때, 컴포넌트를 찾는 것과 같습니다.# 섬 찾기island_number = 2island_tiles = []for i in range(N): for j in range(M): if board[i][j] == 1: # BFS ..
ICMPInternet Control Message Protocol 의 줄임말이다.trace route를 하는 과정을 통해 ICMP 동작을 살펴본다. 원래 ICMP의 목적은 호스트나 라우터에서 error reporting 목적으로 사용되는 프로토콜이다.(호스트나 라우터에 도달할 수 없다든가, 프로토콜이 존재하지 않는다거나) 또는 ping 프로그램에서 요청/응답을 echo 하는데 사용한다. 이 프로토콜은 3계층 프로토콜이지만, 마치 TCP 처럼 IP 위에 존재하는 프로토콜이라, ICMP 메세지는 IP 데이터그램의 데이터로 들어간다. 그래서 이때는 IP 헤더에 프로토콜을 가리키는 부분에 ICMP 정보가 들어간다. ICMP 메세지는 다음과 같은 구조를 가진다. Type, Code 로 구성된다.(0, 0) 이면..
이전에 정리한 SDN은 data plane 관점에서의 SDN 이었다.이번엔 control plane 관점에서 SDN을 정리해보자.즉, 어떤 OpenFlow 기반의 라우팅 테이블이 어떻게 만들어지는지, 누가 만드는지를 살펴보자. SDN인터넷 네트워크 계층인 기본적으로 분산 라우터 기반의 control approach를 쓰고 있다.라우터끼리 라우팅 도메인(AS, 정확히는 area) 내에서 정보를 교환해서 각 라우터가 스스로 라우팅 알고리즘도 결정해서 포워딩 테이블을 만들었다. 이 방식은 최초의 라우터를 만든 CISCO 사에서 시작했다.그때는 라우터를 만들면서 당연히 장치에 필요한 소프트웨어를 다 넣어서 같이 팔았다.온전한 일체형 제품을 판 것이다. (이를 가리켜 monolithic router 라고 한다.)..
BGPBGP (Border Gateway Protocol) 는 ISP 사이의 통신 표준이다.이 프로토콜을 따르지 않으면 다른 AS하고 통신할 방법이 없기 때문에, 모든 라우터 벤더들이 이 프로토콜을 따른다.이 프로토콜은 인터넷을 연결시켜주는 접착제 역할을 한다. intra-AS routing protocol 은 심지어 프로토콜 자체를 안써도 상관없다.우리는 그냥 라우팅 프로토콜 없이 어떤 목적지로 갈 때는 static 하게 무조건 이 길로 간다라고 해도 상관이 없다.하지만 그런 AS도 다른 AS와 연결되고 싶다면 이 프로토콜을 써야 한다. 가령 위 그림과 같이 네트워크가 구성되어 있다고 해보자.AS X 에 속한 A 컴퓨터에서 트래픽을 발생시켰는데, 목적지를 가는 길에 AS Y 를 거쳐야 한다고 하면, ..
지금까지는 일반적인 라우팅 알고리즘들을 정리하였다.이제 실제 인터넷에서 사용되고 있는 구체적인 라우팅 프로토콜에 대해 정리한다. 대표적으로 자주 사용되는 프로토콜이 intra-ISP 라우팅 프로토콜인 OSPF와 inter-ISP, 즉, ISP끼리의 라우팅 프로토콜 표준인 BGP가 있다. 만약 내가 어떤 특정한 라우팅 도메인을 관리하고 있는 네트워크 관리자라면 intra ISP 라우팅 프로토콜은 임의로 선택하면 된다. (OSPF도 좋고, 직접 만들어서 써도 된다.) 이 방식이 기존의 전통적인 라우팅에 기반한 방식이고, 비교적 최근 등장한 SDN에 기반한 방식을 사용할 수도 있다.분산된 라우팅 알고리즘을 각각 라우터들끼리 나눠서 정보를 주고받으면서 나온 결과로 라우팅하는 것이 SDN 기반이다.이 방식을 사용..
어떤 요소를 추상화하는 기본적인 개념이 2가지가 있다. 1. Process abstraction함수와 같이 어떤 기능(절차)의 추상화를 말한다. 2. Data abstraction객체지향 프로그래밍의 클래스같이 데이터를 하나로 추상화하는 것을 말한다. 이번 글에서는 process abstraction에 대해서 더 깊게 파보자. Subprogram서브프로그램은 말 그대로 프로그램을 구성하는 하위 프로그램이다.서브 프로그램은 반드시 맨 처음부터 시작한다. (중간부터 시작x)즉, 진입점이 하나밖에 없는 single entry point 를 가진다. 프로그램을 호출하는 프로그램을 caller, 호출당하는 프로그램을 callee 라고 한다.callee가 실행되는 동안에는 caller가 멈춰있고, callee가 실..
Expression모든 프로그래밍 언어는 수식을 갖고 있을 수 밖에 없다. (프롤로그조차도 포함했으니)수식을 통해 계산한 결과 값을 assignment statement를 통해 변수에 저장한다. Arithmetic Expression수식 중에 제일 간단한 것은 산술 수식이다.산수식은 operator, operand, 괄호, 함수 호출로 구성된다. 대부분의 언어에서 이항연산자는 infix 지만, 일부 언어에서는 prefix 를 사용하기도 한다. (LISP)당연히 postfix를 사용하는 언어도 있다.. 연산자는 크게 단항(unary), 이항(binary), 삼항(ternary) 연산자로 구분된다.피연산자 개수가 12개가 될 수도 있고, 행렬이 될 수도 있고.. 언어마다 다양하다. Arithmetic Exp..
Logic Programming Language기호 논리(symbolic logic) 에 기반을 두고 있는 프로그래밍 언어다.논리적으로 맞는 답을 도출하는 것이 목표이다.논리를 선언하는 것에 신경을 쓰고 (Declarative) 그 도출과정은 신경쓰지 않는다. (procedural)(답이 뭐가 나와야 한다고만 할 뿐, 어떻게 내는지는 신경쓰지 않는다.) 논리형 프로그래밍 언어는 다음과 같은 것들로 구성된다. Proposition (명제)logical statement 로, 참 / 거짓으로 분류가 된다.오브젝트와 오브젝트 간 관계로 구성되어 있다. 오브젝트는 상수, 변수로 구성된다.상수는 오브젝트 자체를 나타내는 기호이다.변수는 명령형 언어의 변수보다, 함수형 언어의 변수에 가깝다. 다른 시점에 다른 오브..
명령형 언어는 변수가 중요하다.이때 변수는 6가지 속성을 가질 수 있었다.address, name, value, type, scope, lifetime 이다.이번 글에서는 이 중 type 에 대해 자세히 정리하려고 한다. Data Type데이터 오브젝트와, 그 오브젝트들에 대해 미리 정의된 연산들을 모은 collection을 정의한 것을 말한다.descriptor는 변수의 attributes 의 collection을 말한다.하나의 오브젝트는 사용자 정의 타입의 인스턴스를 나타낸다. 모든 데이터 타입에 대한 설계시 문제는 어떤 연산들을 정의해야 하는지, 그리고 이들의 동작을 어떻게 명시할 것인지가 중요하다.과연 이것이 필요한 데이터 타입인가, 어떤 오퍼레이션이 필요한가, 어떻게 이들을 정확하게 표시할 것인..
함수형 언어함수형 언어에서 말하는 '함수'는 수학에서 말하는 '함수'를 가지고 프로그램을 만들어보자는 아이디이에서 시작되었다. 우리가 흔히 사용하는 C, C++ 과 같은 언어들은 모두 명령형 언어(imperative languages) 이다.명령형 언어들은 모두 폰 노이만 아키텍쳐에 직접적인 기반을 두고 있다.즉, 폰 노이만 구조를 어떻게 쉽게 사용할 지가 목표인 언어였다.쉽게 사용한다는 말은 효율성이 높다는 의미이다.효율성이 우선 고려사항이었기 때문에, 소프트웨어 개발에 대한 언어의 적합성을 고려하지 않았다. 함수형 언어(functional languages) 는 수학적 함수에 기반을 둔 언어로서, 프로그램이 실행되는 아키텍쳐가 아니라 사용자에게 더 친숙한 이론적 기반을 사용하는 것에 중점을 둔 언어이..
