확장된 유클리드 알고리즘유클리드 알고리즘에서 다루었던 베주 항등식에 의해 최대 공약수는 $gcd(a,b)=g =ax+by$ 의 선형 결합꼴로 나타난다는 것을 알고있다. 확장된 유클리드 알고리즘은 유클리드 알고리즘을 따라가면서 이 선형방정식의 해 $x,y$를 구하는 방법이다. 예시를 따라가는게 이해하기 쉽다. $gcd(56,15)$을 유클리드 알고리즘을 이용하여 구해보자. $a=56,b=15$ 유클리드 알고리즘$56= 15\cdot3+ 11$$15 = 11 \cdot 1+ 4$$11= 4\cdot2 +3$$4= 3\cdot1 +1$$3= 1\cdot 3 +0$ $gcd(56,15)= 1 =56x+15y$ 확장된 유클리드 알고리즘확장된 유클리드 알고리즘은 $gcd(a,b)=g= ax+by$를 만족하는 $x,..

합동$a,b\in\mathbb{Z}, m\in\mathbb{N}$ 에 대해서 $m|(a-b)$ 이면 $a$와 $b$는 모듈러 $m$ 에 대한 합동이라고 하고 다음과 같이 쓴다. $a\equiv b \pmod m$ 대충 $m$에 대한 두 수 $a,b$의 나머지가 같다는 말이다. 합동 모듈로 $m$의 대수적 성질합동의 정의를 이용하여 유도하고 증명할 수 있다. $a,b,c,d \in \mathbb{Z}, n\in\mathbb{n}$ 에 대하여 $a\equiv b \pmod m, c\equiv d\pmod m$이면 다음을 만족한다. 1. $(a+c)\equiv (b+d)\pmod m$양변에 같은 모듈로 $m$에 대하여 합동인 수는 더하고 빼줘도 됨. 2. $ac\equiv bd\pmod m$양변에 같은 모듈로..

산술의 기본정리 (Fundamental Theorem of Arithmetic)산술의 기본정리는 모든 물질이 원자로 구성되듯, 모든 정수가 소수로 구성되는 것을 말해준다.1보다 큰 정수는 소수의 곱으로 표현되며, 이 표현이 유일하다.$1 증명1. ‘소수의 곱으로 표현된다’는 존재성을 증명해보자. 귀류법소수의 곱으로 표현되지 않는 정수가 있다고 가정하고 그 중에 가장 작은 수를 $n$이라고 하자. (well ordering pirinciple)$n$이 소수라면 거짓이므로 증명이 끝난다.따라서 $n$은 합성수인데, 소수의 나뉨성 정리에 의해 모든 정수는 소수에 의해 나누어 떨어지므로 $n = p_1r$ 이고 $r|n$이다.$r따라서 $n=p_1r$이므로 소수들의 곱으로 표현된다. 이는 $n$의 정의에 모순된..

나머지 정리$n \in \mathbb {Z}$, $d\in \mathbb{N}$, unique $\exists q,r\in \mathbb{Z}$ s.t $n=qd+r, \quad 0\leq r정수 $n$과 자연수 $d$에 대해서 $n=qd+r$을 만족하는 유일한 정수 $q,r$이 존재한다.$q$는 몫, $r$은 나머지라고 부르는데, 다음 표기법으로 몫과 나머지를 표현한다 :$q=a \ div \ d, \ r= a\bmod d$ 유클리드 알고리즘(유클리드 호제법)일반적으로 소인수 분해를 통해서 최대 공약수 구한다. 그런데 수가 존나게 크면 소인수분해에 많은 시간이 걸리기 때문에 최대 공약수를 구하는 것이 쉽지 않다. 유클리드 알고리즘은 이를 매우 단축시킬 수 있는 방법을 제공한다.$a,b(a>b)\in \..

소수와 약수현대 암호학은 정수론을 활용한다. 소수와 약수는 정수론의 논의를 시작하기 위한 첫걸음이다. 여기서는 소수와 약수에 대해서 정의하고, 결과적으로는 모든 물질을 이루는 원자와 같이 모든 정수는 소수로 이루어지는 것을 알아볼 것이다. (소인수 분해의 유일성(산술의 기본정리)). 약수(나누어 떨어짐)$n,d\in \mathbb{Z}, d\neq0 \\ d|n \Leftrightarrow \exists k \in \mathbb{Z}$ s.t. $n=dk$정수 $n,d$에 대해 $n=dk$를 만족하는 정수 $k$가 존재하면 $d$를 $n$의 약수라고 하고, 다른 말로 $n$이 $d$로 나누어 떨어진다고 한다. 나뉨성의 추이성(약수의 추이성)$a,b,c \in \mathbb{Z}, \quad a|b$ an..

임의의 프로그램이 끝나지 않고 반복할지 정지할지 완벽하게 판별할 수 있는 알고리즘은 존재할 수 없다. 또한 정수는 컴퓨터로 표현할 수 있지만 실수는 표현할 수 없다. 이렇듯 만능일 법한 컴퓨터도 근본적인 한계에 의한 해결할 수 없는 문제들을 가지고 있다. 집합의 크기(기수)서수: 순서를 나타내는 수 (ordinal number)기수: 크기를 나타내는 수(cardinal number) 유한 집합의 크기는 원소의 갯수를 통해서 정의한다. 그렇다면 자연수, 정수 집합 같은 무한 집합은 크기를 어떻게 정의할까? 놀랍게도 무한집합도 크기가 존재하며 심지어 다르기도 하다. 무한의 개념에서 크기는 모호한 표현이기 때문에 이제부터 크기 대신 기수라는 표현을 사용한다. 기수는 원소의 갯수가 아니라, 원소들의 일대일 대..

함수함수를 정의하고 증명한다. 데카르트곱(cartesian product, 곱집합)$A,B$ : sets$A\times B = \{ (a,b)| a\in A, b\in B\}$ ; A cross B 관계곱집합에서 특수한 조건을 만족하는 부분집합을 관계라고 한다.A,B ; sets, $A\times B = \{(x,y)|x\in A, y\in B\}$$xRy\Leftrightarrow (x,y) \in R \subseteq A\times B$ 함수의 정의 두 집합 $X$(정의역, domain)와 $Y$(공변역, codomain) 사이의 곱집합에서 다음 조건을 만족하는 관계를 함수$f$라고 한다.$f:X\to Y$1 .$\forall x\in X, \exists y\in Y \ s.t.\ (x,y)\in f..

기초 집합론수학은 같은 성질을 가지는 수학적 대상을 모아서 연구하는 방향으로 발전했다. 우리가 흔히 사용하고 있는 함수도 집합으로부터 시작한다. 집합의 기본 정의집합$A = \{ x\in S| P(x)\}$; $P$를 만족하는 $S$의 원소를 모은 집합 부분집합$A\subseteq B \Leftrightarrow \forall x, x\in A \to x\in B$ 진부분집합$A\subsetneq B \Leftrightarrow A\subset B$ and $\exists x \in B$ s.t. $x\notin A$ 집합의 상등$A= B \Leftrightarrow A\subseteq B$ and $B\subseteq A$ 집합의 연산$A\subseteq U$ and $B \subseteq U$$A\..

술어(명제 함수)유한 개의 변수들을 가진 문장. 특정 변수를 대입하면 명제가 된다. 술어(predicate)를 명제함수(propositinal function)라고도 한다. 술어는 함수이므로 적절한 정의역이 있다. 공역은 참/ 거짓 두 가지 값을 가진다.$P(x):D\to${true, false} 진리집합(truth set)명제 함수의 결과가 참인 원소들의 집합을 진리집합이라고 한다.$P(x) :D\to$ {true, false} ; 명제함수{$x\in D| P(x)$ is true} ; 진리집합 한정화 명제전칭 한정자(unimersal quantifier, $\forall$) : forall (모든 x에 대해서)존재 한정자(existential quantifier, $\exists$) : there e..

논리와 증명수학이든 프로그래밍이든 올바른 논증을 해야 오류에 빠지지 않고 신뢰할 수 있는 올바른 결론에 도달할 수 있다. 주어진 명제들이 믿을 수 있는 진실인지, 주어진 논증이 과연 정당한지 파악할 수 있는 방법에 대하여 알아보자. 논리적 동치(logical equivalence)논리적 동치를 잘 알고 있다면 같은 말도 더 간단하게 할 수 있다. 예를 들면 복잡하게 얽혀있는 조건문을 더 간단하고 알아보기 쉽게 쓸 수 있다. 명제 변수 $p,q,r$, 항진명제 $t$, 모순명제 $c$ 라고 하자. 다음은 논리적으로 동치이다.1. 교환법칙 $p\land q \equiv q\land p, \quad p\lor q \equiv p\lor q$2. 결합법칙 ..

스마트 포인터 cpp에서 가장 조심해야 하는 것 중에 하나가 메모리 누수이다. 동적 할당 받은 메모리는 사용 후에 반드시 해제해야 한다. 포인터의 수명이 끝날 때 지시하는 메모리도 자동으로 해제되면 좋겠지만, 이러한 기능은 소멸자 메커니즘을 통해서 클래스에 대해서만 제공된다. '그럼 포인터 역할을 하는 클래스를 만들어서 자동으로 메모리가 해제되도록 하면 되겠네?' 그것이 스마트 포인터(smart pointer)이다. 스마트 포인터는 포인터처럼 동작하는 클래스 객체로 수명이 다하면 자동으로 지시하는 메모리를 해제한다. 따라서 메모리 누수로부터 안전성을 보장받는다. 다양한 스마트 포인터다수의 스마트 포인터가 같은 주소를 가르키고 있다고 하자. 그렇다면 스마트 포인터가 소멸할 때마다 이미 해제된 메모리를 계속..

템플릿(Template)템플릿(template)은 일반화 프로그래밍으로, 함수와 클래스의 일반화 서술이다. 데이터를 중시하는 객체 지향 프로그래밍과는 다르게 일반화 프로그래밍은 프로그램의 알고리즘에 중점을 둔다. 일반화 프로그래밍 중 하나인 템플릿은 구체적인 데이터 타입마다 별도의 함수나 클래스를 정의하는 것이 아닌, 이들을 포괄하는 일반화된 데이터 타입으로 함수와 클래스를 정의하여 하나의 함수 또는 클래스가 다양한 데이터 타입에서 동작할 수 있도록 한다. std의 자료구조들이 이에 해당한다. 템플릿을 통해 정의한 코드는 실제로 생성되지 않는다. 템플릿은 함수 또는 클래스를 정의하는 것이 아니라 정의하는 방법을 컴파일러에게 알려주는 것이다. 정확한 데이터형으로 템플릿을 사용하면 컴파일러는 그 데이터형과 ..

클래스 상속 (Class inheritance)기존에 작성한 클래스의 확장된 클래스를 만드려고 할 때, 새로 클래스를 정의하는 것보다 기존 클래스를 이용하는 것이 훨씬 효율적이다. 클래스 상속(class inheritance)을 통해 기존 클래스의 멤버 변수와 멤버 함수를 물려받아, 확장된 새로운 클래스를 만들 수 있다.class Parent //기초 클래스{private: int m_var1;public: Parent(int data) : m_var1(data) {} ~Parent(){};};class Child : public Parent //파생 클래스 {private: float m_var2;public: Child(int data1) : Parent(data1), m_var2(3.5) {}..

생성자(Constructor)생성자(Constructor)는 객체를 생성할 때 자동으로 호출되어 초기화를 수행하는 클래스의 특별한 멤버 함수이다. 디폴트 생성자 (Default Constructor)사용자가 생성자를 따로 정의하지 않았다면 컴파일러가 자동으로 기본 생성자를 제공하는데, 이 생성자는 멤버들을 default 값으로 초기화하는 디폴트 생성자(default constructor)이다. 사용자가 생성자를 하나라도 정의했을 경우 디폴트 생성자는 제공되지 않는데, 이는 클래스 설계자가 디폴트 생성자의 사용(초기값 없이 객체를 생성하는 것)을 원하지 않을 수도 있기 때문이다. 따라서 생성자를 따로 정의했을 때, 디폴트 생성자를 원한다면 디폴트 생성자를 따로 선언해주어야 한다.class String{pr..

배열과 포인터의 관계배열에서 원소가 아닌, 배열 그 자체는 메모리 주소를 저장하고 있다.int arr1[10] = { 1,2,3,4,5,6,7,8,9,10 };cout 이는 배열이 내부적으로 포인터로 구현되어 있기 때문이다. arr1[5] == *(arr1 + 5);&arr1[5] == arr1 + 5; 특징배열은 첫번째 원소의 주소(할당된 메모리의 맨 앞)를 저장하고 있다. 이는 저장된 주소 값을 변경할 수 없는 상수 (read only)이다.cout read only이기 때문에 배열에 포인터(다른 주소)를 대입하는 것은 안되겠지만, 반대로 포인터에 배열을 대입하는 것은 가능하고, 표기나 연산도 공유할 수 있다. //arr1은 배열, arr2는 포인터int arr1[10] = { 1,2,3,4,5,6,..

Blinn-Phong reflection modelBlinn-Phong reflection model 은 컴퓨터 과학자 James F. Blinn 이 Phong reflection model을 개량, 확장한 모델입니다. Blinn-Phong reflectionBlinn Phong reflection은 Phong reflection에서 반사벡터와 view 벡터를, 광원벡터와 view 벡터사이의 중간벡터와 normal 벡터로 대체합니다. 중간벡터가 노말벡터와 가까워지면, 반사벡터와 view 벡터 또한 가까워지는 특성을 이용한 것입니다. 중간벡터가 노말벡터와 일치하는 구간에서 제일 강한 specular 값을 얻을 수 있습니다.  아래는 specular를 각각 phong, blinn-phong으로 구현한 모습입..

Phong reflection model'phong reflection model 또는 phong lighting model'은 베트남 컴퓨터 그래픽스 연구자 Bui Tuong Phong이 1973년에 발표한 모델입니다. 퍼포먼스에 비해 저렴하다는 장점때문에, 하드웨어의 한계가 많았던 과거에 렌더링 분야에서 꽤 오랫동안 사용되었습니다. 그럴듯해 보이지만 현실의 물리법칙을 많이 무시하기 때문에, 하드웨어가 발전한 현대에서는 잘 사용하지 않습니다. 하지만 현대에서 사용하는 반사모델도 phong model의 구조에서 확장하는 방식이 많기 때문에 알아두는 것이 좋습니다. 마치 shader 계의 hello world... Phong reflection model 의 구조phong model은 lambertian ..

Lambertian reflectance (램버시안 반사율)컴퓨터 그래픽스에서는 일반적인 표면의 난반사(diffuse)에 대한 근사치로 램버시안 반사율(Lambertian reflectance)을 많이 사용한다. lambertian은 이상적인 난반사 표면이 관찰자가 보는 각도와 관계없이 같은 겉보기 밝기를 가진다고 설명한다. 이는 물리적으로 정확하지 않기 때문에 모든 물체의 표면을 표현할 수는 없지만, 일반적인 표면의 난반사를 표현할 때 근사치가 될 수 있기에 물체 표면의 색을 나타낼 때 많이 사용된다. 예를 들어 종이나 원목재질 또는 페인트칠을 한 표면과 같이 보는 각도에 따라 밝기가 다르지 않은 이상적인 난반사면은 램버시안 표면에 가깝다고 할 수 있다.램버트 코사인 법칙 (Lambert's Cosi..