피보나치 수열 (Fibonacci Sequence)
피보나치 수열이란?
피보나치 수열 \((F_n)_{n \geq 0}\)은 다음과 같은 점화식으로 정의될 수 있다.
\[F_0=0, \space F_1=1, \quad F_n=F_{n-1}+F_{n-2} \space \space \forall n \geq 2\]
즉, 첫 두 항을 0과 1로 시작하고, 이후 각 항은 바로 이전 두 항의
페르마의 마지막 정리와 수학적 도구들
서론 : 수학 역사상 가장 유명한 미해결 문제
나는 정말로 놀라운 증명을 발견했지만, 이 여백은 그것을 적기에는 너무 작다. - 피에르 드 페르마
1637년, 페르마는 디오판토스의 '산술' 여백에 이 문장을 남겼다. 이 짧은 메모는 수학 역사상 가장 오래된 난제 중 하나가 되어 하나의 출발점이 되었다. 이후 350년간 수많은 수학자들이
빠른 곱셈 알고리즘 - 1. 카라추바 알고리즘
알고리즘 문제 해결 분야(PS, Problem Solving)에서는 주어진 문제를 정해진 시간/공간 제약 안에 풀기 위한 여러 알고리즘이 사용된다. 특히 가장 초점을 두는 부분은 주어진 문제를 빠른 시간 안에 해결하기 위한 개선된 알고리즘을 찾는 것이며, 보통은 시간복잡도를 기준으로 알고리즘의 성능을 평가한다. 본 포스트의 1편에서는 가장 기본적인 연산인 곱셈을 빠르게
Gamma Function
Introduction
이 글에서는 감마 함수에 대해서 다루기는 하지만, 나중에 쓸 글에 선행되어야 할 지식만 언급을 할 것이기 때문에, 감마 함수의 성질이나 파생된 정리에 대해서는 일절 다루지 않는다. 필자는 감마 함수의 정의만 소개할 것이다. 감마 함수는 나중에 n 차원 구의 표면적을 구할 때 유용하게 사용되기 때문에 잘 알아두도록 하자.
Definition
감마
뭔가 매우 신기한 급수, Taylor's Series
드디어 때가 왔다. 오늘은 \( y=e^x\)와 같은 초월함수를 근사하는 방법에 대하여 알아보자. 이를 위해서는 테일러 급수라는 매우 신기한 급수를 알아야 하는데, 오늘은 이것에 대해 알아보고, 증명하며, 활용해본다.
시작하자.
I. 초월함수란 무엇인가?
초월함수란 이름에서 알 수 있듯이 다항함수로 나타내지 못하는 함수들을 뜻한다. 대표적인 예시로는 아래의 것들이 있다.
\[ y=sin(
Proof of The Runge-Kutta Method - Part 1
The R-K method, more well known as the Runge-Kutta method, is a powerful way to interpret Ordinary Differential Equations, or ODEs for short.
밀러-라빈 소수 판별법
소수 판별법
정보 문제에서 심심치 않게 등장하는 것이 바로 소수 판별법이다. 또, 소수 판벌법은 그 자체로도 중요하지만, 다른 정수론 문제에서 기본이 되는 만큼 그 효율이 중요하다.
흔히 생각할 수 있는 방법은 2에서 n-1까지의 수로 n을 나누어 보는 것이다. 이 경우 n이 커지면 시간이 너무 많이 걸린다. 조금 더 효율적으로는 2에서