허프만 코드와 데이터 압축 컴퓨터는 문자를 그대로 이해하지 못한다. 따라서 문자를 컴퓨터가 이해할 수 있도록 숫자로 바꾸어주어야 한다. 문자를 숫자로 변환하는 것을 '인코딩' 숫자에서 다시 문자로 변환하는 것을 '디코딩' 이라고 한다. 예를 들어 아래와 같은 규칙의 코드 표가 있다면 a,b,c,d 4개 문자로 구성된 아래 문자열을 그 아래처럼 인코딩할 수 있다. 13자리 문자열이 26자리 bit 리스트로 인코딩되었다. Prefix-Free code 문자열을 인코딩할 때 사용하는 코드 표는 다른 규칙의 코드표를 사용해도 된다. 이런 코드 표를 사용하더라도 문제없이 인코딩과 디코딩이 가능하다. 이때, 각각의 bit 가 선택됨에 따라 어떤 문자를 가리키게 되는지를 이진트리로 나타낼 수 있는데 위와 같이 나타난..

동적 계획법은 어떤 값을 구할 때 반복적으로 이미 구했던 값을 사용하는 경우, 이 값을 미리 기록해두었다가 활용하는 방법의 알고리즘이다.동적 계획법은 대체로 재귀 형태의 점화식을 가지는 문제를 해결하는데 유용하게 사용할 수 있다. 이항 계수이항계수는 nCk 조합의 경우의 수를 구하는데 사용된다. 이항 계수의 값은 위와 같이 계산한다.이때 이항 계수 nCk 를 각각의 값에 따라 쭉 표를 그리듯 그리면 아래와 같이 그려진다. 이 삼각형을 가리켜 '파스칼 삼각형' 이라고 한다.파스칼의 삼각형에 따르면 이항 계수는 아래와 같은 성질을 지닌다. 이항계수의 값이 다른 이항계수의 값을 이용해 재귀적으로 표현됨을 알 수 있다.이 공식을 그대로 함수로 옮기면def binom(n,k): i..

분할 정복은 말 그대로 주어진 문제를 분할하고, 분할한 조각을 정복(해결) 하는 방식으로 해결한다. 그리고 이 과정은 재귀적으로 발생한다. 지난 글에서 정리한 피보나치 수열도 그 값을 구할 때 '재귀'를 주요 아이디어로 활용하였듯, 분할 정복도 다른 관점에서 재귀를 활용하는 알고리즘이다. 이제부터 다양한 분할 정복 알고리즘과 그들의 시간복잡도를 구해본다. 카라츠바 곱셈 계산 (Karatsuba Method) 일반적인 곱셈 계산 곱셈은 덧셈의 반복이므로, 먼저 덧셈을 하는 과정을 생각해보자. 1234와 5678을 더한다면 일반적으로 아래와 같은 과정으로 진행된다. 두 피연산자는 정렬되어있어 i번째 자릿수는 같은 열에 위치한다. 각 자리수를 더해 만약 올림(carry)이 발생한다면, 다음 자리수에 넘겨 함께..

지수 base convention 알고리즘에서 제일 중요한 지수의 base 는 '2' 이다. 따라서 앞으로 아래와 같은 컨벤션으로 로그를 작성한다. 여기에 더해 log x 는 밑이 10인 로그를 의미한다. Ceiling, Floor 만약 문맥상 반드시 정수가 와야하는데, Ceiling, Floor 기호가 빠져있다면, 어떤 나눗셈에 대해 Floor 가 적용된 것으로 본다. “For the number of inputs n, the running time T(n) = 2T(n/2) + 1.” 라는 문장의 의미는 “ · · · , T(n) = 2T(⌊n/2⌋) + 1.” 라는 의미와 같다. Notation big-O 는 g(n) 이 f(n) 보다 항상 크거나 같다. 즉, g(n)이 f(n)의 최악이다. big..

Window Programming 용어 Windows Procedure : a function that handles specific messages the parameters for the windows procedures mean specific messages when a message is created, a windows procedure corresponding to the message is called Win32 SDK : standard C library necessary to develop an application program on Windows OS MFC (Microsoft Foundation Class) : C++ class library necessary to develop ..

rdt 개념TCP는 신뢰성을 보장하는 프로토콜이다.TCP에 대해 정리하기 전에 사전 개념으로서 rdt에 대해 정리한다. rdt는 reliable data transfer 의 줄임말이다.즉, 신뢰성있는 데이터 전송을 어떻게 할 수 있는지에 대한 개념이다.  이 그림을 보자.어플리케이션에서 데이터를 만들어 transport 계층으로 보낸다.그러면 transport 계층에 있는 프로토콜을 거쳐 네트워크 계층을 통해 데이터가 전송된 후 receiver 가 transport 계층을 거쳐 데이터를 받는다. 그런데 네트워크 계층을 포함한 그 밑의 데이터 전송 과정은 unreliable 하다.unreliable 하다는 말은 보내는 중간에 데이터가 사라지거나(loss), 훼손되거나(corrupt..

이번 글에서는 시점 변환에 대해 정리하려고 한다. 시점 변환은 주어진 그림에서 카메라의 위치를 이리저리 옮기는 것을 말한다. 카메라의 위치 정보를 설정하는 좌표계는 View Coordinate System (VCS, 시점좌표계) 이다. 따라서 시점을 옮기는 행위는 VCS이 변환되는 것을 의미한다. 이를 위해 사용하는 행렬이 뷰 행렬이다. (그런데 GL에서는 Model 행렬과 View 행렬을 합해서 하나의 행렬로 취급한다고 한다.) 그렇다면 뷰 행렬은 어떻게 구할까? 위 이미지에서 보는 것이 뷰 행렬을 구하는 것과 관련되어 있다. 결국 우리가 원하는 것은 VCS를 구하는 것이다. 즉, VCS의 x, y, z 축을 결정하고, 이 축을 기준으로 기존 정점을 새롭게 표현하는 것이다. 이는 아래와 같은 방식으로 ..

앞에서 Fetch - Decode - Execute 순으로 회로를 점차 개선하는 과정을 보였었다.이번에는 이를 한번에 정리해서 명령어별로 어떤 데이터 패스를 통해 실행되는지 정리하려고 한다.그리고 ALU 가 연산자별로 연산을 택하는 그 구체적인 과정도 함께 정리한다. lw 명령어 실행하기fetchlw 명령어를 실행하는 과정을 하나씩 그려보자.먼저 명령어를 가져올 메모리와, PC 레지스터가 필요하다. 다음과 같이 그렸다.이제 메모리에서 읽어온 명령어를 decode 해야한다. decode 읽어온 명령어의 31:26 비트를 보고 opcode를 파악해서 lw 명령어임을 파악한다.25:21 비트를 reg file 의 ra에 전달해서 base address 주소를 가져온다. 다음으로는 15:0 비트를 상수필드로 보..

투상 (Projection) 3D 물체를 2D 평면에 사상하는 것을 말한다. 지난 글까지 각종 행렬 변환을 통해 ' Model 좌표계 → World 좌표계 → View 좌표계 ' 까지 변환했다면 이렇게 변환된 좌표계 위에 놓인 3D 물체를 2차원 화면에 사상하는 과정이다. 먼저 용어부터 정리하자. 1. 투상면, View Plane = Projection Plane 화면에 그리기 전 최종 변환된 좌표계 위 3D 물체를 투상하는 2D 화면을 의미한다. 물체 영상이 이 곳에 맺힌다. 2. 관찰자 위치, View Point, Eye Position, Camera Position 투상의 기준은 관찰자의 위치로부터 결정된다. 이 위치를 '시점 좌표' 라고 한다. 3. 투상 중심 (COP = Center Of Pro..

UDP user datagram protocol RFC 768 에 정의된 매우 오래된 프로토콜이다. 트랜스포트 계층이지만, 네트워크 계층에서 포트만 더해주기 때문에, 데이터그램이라는 네트워크 계층 전송단위를 그대로 사용하기도 한다. 네트워크 계층과 동일한 서비스 모델을 제공한다. 따라서 UDP 세그먼트는 중간에 유실되더라도 복구하거나 재전송하는 서비스는 없다. send 순서와 receive 순서가 동일하다는 보장도 하지 않는다. UDP 장점 1. connectionless 미리 연결을 설정할 필요가 없어서 오버헤드 시간이 절약된다 연결 설정이 없다는 말은, 같은 목적지로 보내는 같은 내용의 세그먼트도 모두 독립적으로 여긴다는 특징이 있다. TCP와 달리 RTT 딜레이가 없다. 2. stateless se..