Programmer's Digest

이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. binary tree에서 각 node는 두개의 children을 갖거나 혹은 leaf node이거나 둘 중 하나라고 할 때, leaf node = non-leaf node + 1 개가 된다.

어떤 정점 A에서 C로 가는 직접경로는 없고, 우회경로가 있을 때 A->C로의 간선을 연결한 그래프

Partial order relation 집합   {\displaystyle S}  위의  이항 관계   {\displaystyle {\leq }} 가 다음 조건을 만족시키면 이 이항 관계는 집합  {\displaystyle S} 에 대한  부분 순서 이다. 모든  {\displaystyle s\in S} 에 대하여,  {\displaystyle s\leq s}  ( 반사성 ) 모든  {\displaystyle s,t,u\in S} 에 대하여, 만약  {\displaystyle s\leq t} 이며  {\displaystyle t\leq u} 라면  {\displaystyle s\leq u}  ( 추이성 ) 모든  {\displaystyle s,t\in S} 에 대하여, 만약  {\displaystyle s\leq t} 이며  {\displaystyle t\leq s} 라면  {\displaystyle s=t}  ( 반대칭성 ) 집합과 그 집합에 대해 부분 순서인 이항 관계의  순서쌍   {\displaystyle (S,\leq )} 을  부분 순서 집합 이라고 한다. Total order relation Partial order realtion 조건에서 다음조건을 추가하면 된다. 모든  에 대하여,  이거나     둘중 하나이다.

집합 X 위의 equivalence는 reflexive이자 symmetric이자 transitive인 이항관계이다. 즉, 다음 조건들이 성립하여야 한다. (reflexive) 임의의  {\displaystyle x\in X} 에 대하여,  {\displaystyle x\sim x} (symmetric) 임의의  {\displaystyle x,y\in X} 에 대하여, 만약  {\displaystyle x\sim y} 라면,  {\displaystyle y\sim x} (transitive) 임의의  {\displaystyle x,y,z\in X} 에 대하여, 만약  {\displaystyle x\sim y} 이고  {\displaystyle y\sim z} 라면  {\displaystyle x\sim z}

전단사 함수(全單射函數, 영어: bijection, bijective function)는 두 집합 사이를 중복 없이 모두 일대일로 대응시키는 함수이다. 일대일 대응이라고도 한다.

set A, set B에 대해 cartesian product A * B는 다음과 같다. 대표적인 예로, 2차 유클리드 공간(평명) X*Y , (x,y)인 직교좌표계이다. relation은 Cartesian product의 subset이다. 예를들어, ∀a∈A,∀b∈B 일 때 aRb<->(a,b)∈R 의 경우 왼쪽 R은 relation을 나타내고, 오른쪽 R은 집합이다.

수학적 귀납법(數學的歸納法, 영어: mathematical induction) , 줄여서 귀납법은 어떤 성질이 모든 자연수에 대해 성립함을 증명하기 위해 사용되는 방법이다. 어떤 성질이 모든 자연수 n에 대해 성립함을 보이기 위해서는, '두 조건'을 각각 증명하는 두 과정을 거친다. 첫 자연수(0 또는 1)에 대해 성립 증명 n에 대해 성립함을 가정하고, n+1 에 대한 성립 증명