트리보나치 숫자 (Tribonacci Number)
Tribonacci Number : 트리보나치 숫자 피보나치 수열은 $F_n = F_{n-1} + F_{n-2}$ 와 같이 이전에 계산된 두개의 값을 이용해 새로운 값을 찾는 개념이죠. 트리보나치 수열은 피보나치 수열과 비슷한 개념으로 이전에 계산된 값이 두개가 아닌 세개의 값으로 새로운 값을 찾는 개념입니다. 쉽게 생각하면, 트리보나치는 피보나치의 세개짜리 버젼이라 생각하시면 됩니다. $$F_n = F_{n-1} + F_{n-2} + F_{n-3}, F_0 = F_1 = 0 \ and \ F_2 = 1$$ 트리보나치 숫자를 나열하면 다음과 같습니다. 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 1951..
포함 배제의 원리 (Inclusion-Exclusion)
포함 배제의 원리 포함 배제의 원리는 조합, 확률, 그리고 계산에서 유용하게 쓰이는 유명한 기술입니다. $n$ 개의 집합 $A_1, A_2, \dotsc , A_n$ 들이 주어진 전체 집합 $A$ 가 있습니다. 이제 이 집합들이 가지고 있는 합집합의 원소갯수를 $S_n$ 이라 하겠습니다. 좀더 수식으로 표현하자면, $S_n = \bigg|\bigcup_{i=1}^n A_i\bigg|$ 와 같습니다. 즉, $n$ 개의 집합 $A_1, A_2, \dotsc , A_n$ 에 주어진 모든 원소들을 합집합 하여 만든 집합을 $S$ 라 한다면 그 $S$ 집합 원소들의 총 개수인 $S_n = |S|$ 를 찾는것 입니다. (집합 $A$ 에 대한 집합의 원소개수를 영어로 cardinality (카디널리티) 라고 하고 $..