The Way

정적분을 배웠으니 그 응용을 해 볼 차례이다.적분은 애초에 무언가를 쌓는다는 이미지가 강하기 때문에, 넓이나 부피를 구하기 용이하다.아래 나온 것들도 사실 구분구적법을 배운 사람이라면 따로 공부하지 않아도 구할 수 있는 정도이다. 개꿀챕터. 1. 부피 구하기원판을 합하는 식은 원체 쉬우니 넘어가자. 회전체의 경우 원판이 아닌, 두께가 없고 높이가 있는 고리 모양을 합해서 구할 수 있다. 아래 예제를 보자. 예제 1. x축과 포물선 $f(x) = 3x - x^2$으로 둘러싸인 영역을 수직선 $x=-1$로 회전시켰을 때 얻어진 입체의 부피y축 기준 원판모양으로 구하려면 상당히 어려운 문제다. 하지만 x축 기준으로 고리 모양으로 합하면 쉽다.고리의 길이는 $2\pi R$이고 높이는 $f(x)$이다. 2. 호의..

드디어 나왔다. 적분.여담이지만, '적분'이란 무엇인가?미분의 역연산? 그래프 아래의 넓이? 과연 이 물음에 정확한 답을 할 수 있는 대학생이 얼마나 될까.적분의 세계를 한 번 탐험해보자. 부정적분부정적분은 굉장히 간단하다. 책에 따르면,'함수 f의 역도함수(미분해서 f가 되는 함수) 전체의 집합'을 f의 부정적분이라고 한다.그런데 한글 위키피디아에는'어떤 함수를 도함수로 하는 모든 함수를 구하는 연산'이 부정적분이라고 한다. 음? 어떤게 맞는거지? 영문 위키피디아를 보자.'in calculus, an antiderive is a differentiable function F whose derivative is equal to the original function f.'영문 위키피디아의 정의를 따르자...

재미없는 단원이다. 하지만 중요한 내용이 많으니 버티자. ㅠㅠ 먼저 기본인 최대, 최소. 최댓값, 최솟값은 정의역의 양 끝점이나 임계점에서만 가질 수 있다.임계점은 도함수가 0이거나 정의가 되지 않는 점. 다음으로 롤의 정리, 평균값의 정리가 나온다.고교 과정에도 나오는 간단한 식이고 대부분 증명을 할 때 이용된다. 롤의 정리는 너무 쉬워서 생략. 평균값의 정리$y=f(x)$가 $[a,b]$에서 연속이고 $(a, b)$에서 미분 가능하면$\frac{f(b)-f(a)}{b-a}=f'(c)$인 $c$가 $(a, b)$에 존재 간단하게 기억하고 넘어가자. 도함수와 2계 도함수, 극값을 알면 그래프의 개형을 간단하게 그릴 수 있다.하지만 그냥 컴퓨터로 등간격으로 나누어서 그리는게 더 쉽게 먹힐 수 있다.. 다음..

미분은 정말 신이 내린 선물이다. 왜냐하면 쉽기 때문에. 적분같은 것과는 차원이 다르다.대부분 고교과정에 있는 내용이라 후딱후딱 넘어갔다. 그런데 역함수의 미분은 잘 기억이 나지 않았다.그런데 굉장히 유용하니 정리하자. 역함수의 미분아래 그림을 보면 간단하게 이해할 수 있을 것이다. 간단한 식이지만 활용이 굉장히 다양하다. 예제 1. $\frac{d}{dx} \ln{x}$ 구하기일반적인 방법. 아마 수학의 정석에 소개된 방법일 것이다.하지만 역함수의 미분법을 사용하면 두 줄이면 끝난다. 마찬가지로 삼각함수의 역함수의 미분을 구하는 데에도 유용하게 사용된다.공대생 중 아크사인의 미분을 못 구하는 사람도 많을 듯 하다. 나만 못구했었나..? 먼저 구하기 전에 삼각함수의 미분을 가볍게 정리하고 넘어가자. 위 ..

극한과 연속은 입실론-델타 논법만 알면 된다. 거의 지분 99% 정도인 듯. 입실론 델타 논법간단히 말하면 $\epsilon$을 던져주었을 때 저 식을 만족하는 $\delta$를 찾기만 하면 된다. 뭐든 상관없이. 보통 $\delta$를 찾기 위해 역추적을 해준다. 예제 1. $\lim_{x\rightarrow 1} (5x-3) = 2$를 보여라. 예제 2. $\lim_{x\rightarrow 4} \sqrt{x} = 2$를 보여라. 예제 3. $\lim_{x\rightarrow c} f(x) = L$, $\lim_{x\rightarrow c} g(x) = M$일 때$\lim_{x\rightarrow c} (f(x) + g(x)) = L + M$임을 보이기. 나머지는 다 뻔한 내용이다.우극한과 좌극한은 ..

메르센 소수의 소수 판별 알고리즘은 일반적인 PS에서 출제되는 알고리즘은 아니지만.. 상당히 흥미로운 알고리즘이다.엄청나게 큰 메르센 소수의 소수 판별을 빠르게 할 수 있고, 그래서 알려진 큰 소수 중 상위권은 항상 메르센 소수가 먹는다.https://en.wikipedia.org/wiki/Largest_known_prime_number(작성일 기준 1~7등이 모두 메르센 소수이다) 1. Trial Factoring먼저 두 가지 정리를 미리 알아두고 가자.정리 1. $2^p - 1$이 소수이면, p도 소수이다.정리 2. $2^p - 1$의 인수는 모두 $2kp + 1$의 형태이며, 8로 나누었을 때 나머지가 1 또는 7이다. 정리 1과 2를 통해 $2^p - 1$의 인수가 될 만한 수의 후보를 추려낸 후..

windows로 c++ 코딩을 할 때, 디버깅을 할 때 vector, string, map 등의 stl이 예쁘게 출력되지 않는 경우가 있다. Visual Studio로 할 경우에는 대체로 문제가 없는 편인데, Dev c++이나 Visual Studio Code, Code::Blocks 등을 사용할때는 (적어도 나는) 항상 이런 문제가 발생했다. arr는 vector인데, 안의 원소가 안보이고 메모리 주소만 잔뜩 보인다. PS를 하면서 STL은 필수적인데, 디버깅 할때 안의 원소를 보지 못한다는 것은 가히 치명적이라고 할 수 있다.그냥 Visual Studio를 쓰면 안되냐고 물을 수 있는데,Visual Studio은 너무 무겁기도 하고, 오픈 소스도 아니고,g++이 아니라 #include 을 못 쓴다거나..

우선순위 큐를 이용한 다익스트라 알고리즘의 구현. 출처는 책 알고리즘 트레이닝. 특이한 점으로는 pq에 동일한 원소들이 추가되도록 방치한다는 것이다. 어차피 나중에 continue가 포함된 if문에서 다 걸러지게 된다. 느긋한 삭제라고 부른다. 코드는 다음과 같다. #include using namespace std; typedef pair ii; // index는 0 ~ v - 1 // v은 vertex 갯수, s는 시작점 // edge에 (번호, 거리)로 저장 int v, s; vector edge(v); vector dist(v, INF); dist[s] = 0; priority_queue pq; pq.push(ii(0, s)); while (!pq.empty()) { ii now = pq.top(..

초보자들에게 이항 계수는 보통 DP를 이용하여 계산하는 것이 정석이라 여겨진다. 하지만 어느 정도 문제를 풀다보면 DP의 메모리 범위 이상의 숫자들을 더 빠르게 계산해야 한다. 이번 AtCoder Grand Contest 025 B번 문제에서도 이를 이용하는 문제가 있었는데, 버벅이다가 결국 못풀었다. 따라서 이항계수를 구하는 방법들을 간단하게 공부해보았다. 이 분야의 한줄기 빛과도 같은 구사과님의 블로그를 참고하였다. 1. DP 생략. 시간, 공간 복잡도가 $O(n^2)$이라 쓸모가 없다. 대신 여기서 사용하는 점화식 $_n C_k = _{n-1}C_{k-1} + _{n-1}C_k$은 많은 아이디어의 기반이 되니 기억하자. * 아래 2~4번의 방법은 MOD가 N보다 크다고 가정하자. 예기치 못한 오류가..

algorithm에 포함되어 있는 lower_bound와 upper_bound 덕분에 앞으로 코딩이 조금 편해질 것 같은데,이름 때문인지 약간 헷갈려서 정리하고 가는 것이 좋을 것 같다. 기본적인 사용법 int arr[size] = {...}; int* ptr = lower_bound(arr, arr + size, n); 여기서 n은 찾고자 하는 수이다 반환되는 값은 다음과 같다. * lower_bound: n 이상의 수 중 가장 작은 것* upper_bound: n 초과의 수 중 가장 작은 것 (정확히는 pointer나 iterator가 반환된다)이렇게만 알아놓으면 헷갈릴 일은 없을 것 같다. int arr[2] = {3, 5};일 때 i = 0 ~ 7에 대해 각각 함수가 반환하는 포인터가 가리키는 값..