이번 포스트에서는 이진트리의 순회에 대해 다루도록 하겠습니다. 이진 트리 순회란? : 트리에 있는 모든 노드를 한 번씩만 방문하는 것입니다. 또한 한 노드가 방문될 때 어떤 연산이 그 노드에 대해 수행됩니다. 만일 L, V, R이 한 노드에서 각각 왼쪽으로 이동, 노드 방문, 오른쪽으로 이동하는 것을 나타낸다면 LVR, LRV, VLR, VRL, RVL, RLV 등 6개의 순회 방법이 있을 수가 있습니다. 이진 트리 순회의 종류 : (1) Inorder (중위 순회, LVR) : 더 이상 진행할 수 없을 때까지 왼쪽 방향으로 이동하여 내려간 다음, 그 노드를 방문하고 오른쪽 자식 노드로 이동한 뒤 계속합니다. 이때 오른쪽으로 이동할 수 없을 때에는 한 노드 뒤로 되돌아갑니다. 소스 코드 : void in..
이번 포스트에서는 이진 트리에 대해 다루도록 하겠습니다. 트리란? : 트리는 1개 이상의 노드로 이루어진 유한 집합으로서 큐나 스택과 같은 선형 구조가 아닌 비선현 자료구조입니다. 트리의 특징 : 하나의 루트 노드를 가진다. 모든 노드는 0개 이상의 자식 노드를 가진다. 노드의 서로간을 연결하는 간선(Edge)이 존재한다. 트리에 관한 용어 정리 : 노드의 차수(degree) : 자식 노드의 개수 (A : 3) 트리의 차수(degree of tree) : 트리의 최대 차수, 즉 제일 많은 가짓수 (3) 단말 노드(leaf of terminal node) : 자식이 없는 노드 (K, L, F, G, M, I, J) Parent : 부모 노드 (E : B, B : A) Children : 자식 노드 (B :..
이번 포스트에서는 Window-To-Viewport의 변환에 대해 다루도록 하겠습니다. Window-To-Viewport 란? : 2D world coordinates를 device coordinates로 변환하는 프로세스입니다. 각 용어에 대한 정의는 다음과 같습니다. world coordinates (사용자 좌표) : 그래픽 개체들이 정의된 작업 영역을 통칭하는 좌표 device coordinates (장치 좌표) : 실제 장치에 표시된 영역을 통칭하는 좌표 window : 표시를 위해 선택된 사용자 좌표 영역 (즉, 화면에 표시될 것을 정한다.) viewport : 디스플레이 장치에서 window가 매핑되는 영역 (즉, 화면 어디에 표시되는 지를 정한다.) Window-To-Viewport 동작 과..
이번 포스트에서는 동차 좌표에 대해 다루도록 하겠습니다. 동차 좌표란? : 임의 0이 아닌 상수 h에 대하여 (x, y)를 (xh, yh, h)로 표현하는 것입니다. 동차 좌표의 특징 : 일반적인 동차 좌표는 (h*x, h*y, h)로 표현할 수 있다. 2D 기하하적 변환에 있어서 h는 0이 아닌 모든 값이 될 수 있다. 간편하게 h를 1로 설정할 수 있다. (x, y, 1) 동차 좌표에 있어 Translation, Scaling, Rotation의 관계식은 다음 표와 같습니다. Method Matrix Representation Composite (step = 2) Translation P' = T(dx, dy) * P P'' = T(dx1 + dx2, dy1 + dy2) * P Scaling P' =..
이번 포스트에서는 기하적 변환에 대해 다루도록 하겠습니다. Geometrical Transformation의 종류 : Rigid body(강체 변환) : 거리와 각도가 보존된 변환 (이동, 회전) Conformal(등각 변환) : 각도가 보존된 변환 (이동, 회전, 확대 또는 축소) Affine(아핀 변환) : 평행성이 보존된 변환 (이동, 회전, 확대 또는 축소, 비틀림, 반사) 이어서 Geometrial Transformation 방식에 대해 다루겠습니다. Translation (이동) : 가장 조건이 느슨한 변환 위치를 제외한 기하적 속성은 그대로 유지 관계식 : x' = x + dx, y' = y + dy Scaling (확대 또는 축소) : x 방향으로 스케일링한 비율과 y 방향으로 스케일링한..
이번 포스트에서는 라우팅 알고리즘 중의 "Link-State Algorithm"에 대해 다루도록 하겠습니다. Link-State Algorithm 이란? : 링크 상태 데이터베이스를 사용하여 목적지까지의 여러 가능한 경로들 중에서 각 링크 비용 합에 기반하여 최소의 경로 비용을 계산하는 라우팅 알고리즘입니다. 즉 쉽게 말해 모든 라우터가 주기적으로 브로드캐스트를 통해 전체 라우터의 토폴로지(topology)를 알아내어 최적의 경로를 계산하는 알고리즘입니다. Link-State 알고리즘 동작 과정 : Initialization: N' = {u} for all nodes v if v adjacent to u then D(v) = Cu,v else D(v) = ∞ Loop find w not in N' suc..
이번 포스트에서는 ICMP에 대해 다루도록 하겠습니다. ICMP 란? : ICMP는 Internet Control Message Protocol의 줄임말로 네트워크 제어 메시지를 전달하기 위해 사용된 프로토콜입니다. ICMP의 특성을 활용하여 만들어진 유틸리티로는 traceroute가 있습니다. ICMP 기능 : Error reporting Echo request/reply Traceroute : 패킷이 목적지까지 도달하는 동안 거치는 라우터의 IP주소를 확인할 수 있는 툴이다. UDP와 ICMP, IP의 TTL(Time To Live)값을 활용한다. Traceroute 동작 과정 : TTL 값을 1로 설정하고 33434번 포트로 UDP 패킷(probes)을 한 번에 세 개씩(안정 보장을 위해) 보낸다...
이번 포스트에서는 DHCP에 대해 다루도록 하겠습니다. DHCP 란? : Dynamic Host Configuration Protocol의 약자이며 호스트의 IP주소와 각종 TCP/IP 프로토콜의 기본 설정을 클라이언트에게 자동적으로 제공해주는 Application Layer의 프로토콜입니다. 즉, 쉽게 말해 우리가 사용하는 IP주소를 자동으로 할당해주는 프로토콜입니다. DHCP의 특징 : 자동 갱신(renew) 주소의 재활용 가능(reuse) 모바일 유저도 사용 가능 IP 충돌 방어 라우터에 구현됨 UDP 사용 DHCP 동작 과정 : 호스트가 브로드캐스팅을 통해 DHCP discover 메시지 전송 DHCP 서버가 듣고 DHCP offer 메시지(IP주소 오퍼)로 회신 호스트가 해당 IP주소를 가지겠다..
이번 포스트에서는 NAT에 대해 다루도록 하겠습니다. NAT 란? : NAT는 사설 IP를 공인 IP로 변경거나 공인IP를 사설IP로 변경하기 위해 필요한 주소 변환 서비스입니다. IPv4주소 체계는 대략 총 40몇 억개의 IP주소를 표현할 수 있습니다. 보기에 많지만 실제로는 턱없이 부족하기 때문에 이와 같은 IP주소 고갈문제를 해결하기 위해 나타난 것이 바로 NAT라고 할 수도 있습니다. NAT 예시 및 동작 과정 : Sour addr이 10.0.0.1이라는 사설 IP를 가진 노드 A가 Dest addr 128.119.40.186과 통신하고자 한다. 라우터에서는 Sour addr을 자신의 IP 주소인 138.76.29.7로 바꾼 다음에 통신을 요청한다. NAT translation 테이블을 채운다. ..
이번 포스트에서는 IP 주소(IPv4)에 대해 다루도록 하겠습니다. IPv4의 특징 : 독특한 32비트로 이루어진 숫자 네트워크 인터페이스를 정의 계층적 구조의 주소(네트워크 부분과 호스트 부분) IP Classful Addressing (클래스풀 주소체계 A~C) : A : 1.0.0.0 ~ 127.255.255.255 B : 128.0.0.0 ~ 191.255.255.255 C : 192.0.0.0 ~ 223.255.255.255 IP 주소를 클래스풀의 문제점 : IP주소 부족 계층화와 분할을 위해 낭비되는 IP주소가 많다 CIDR(Classless Inter-Domain Routing) : 클래스를 특별히 나누지 않고 유연하게 나눠서 쓰는 개념 표현법 : 예) 200.23.16.0/23(서브넷 마스..