레프네 약방

레프네 약방

  • 분류 전체보기 (147)
    • 알고리즘 문풀 (62)
      • AtCoder 연습 (6)
      • BOJ 연습 (27)
      • Codeforces Problemset 연습 (4)
      • Others (25)
    • 수학 이론 (39)
      • 정수론 (10)
      • 미적분학 (3)
      • 추상대수학 (11)
      • 선형대수학 (2)
      • 이산수학 (10)
      • 경시 테크닉 (3)
    • 수학 문풀 (20)
      • 경시 (내 풀이) (5)
      • 경시 (남의 풀이) (2)
      • 대입 스타일 (4)
      • 기타 (9)
    • CS 이론 (14)
      • 자료구조 (3)
      • 알고리즘 (11)
    • 통계학 (1)
      • 2019-1 일반통계학 (1)
    • 물리학 이론 (3)
      • 전자기학 (1)
      • 양자역학 (2)
    • 화학 이론 (3)
      • 물리화학 (3)
      • 계산화학 (0)
    • Misc. (0)
      • Computational Number Theory (0)
  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록
RSS 피드
로그인
로그아웃 글쓰기 관리

레프네 약방

컨텐츠 검색

태그

Codeforces 물리 더블카운팅 Russian Code Cup 함수방정식 computer_algebra approx 물리화학 그래프이론 computer-algebra 정수론 수학문풀 approximation ps-hell 조합론 경시수학 AOPS 수학 열역학 화학

최근글

댓글

공지사항

아카이브

분류 전체보기(147)

  • 키타마사법 (Kitamasa method)

    2017.11.05
  • Metric TSP와 Christofides' algorithm

    2017.11.05
  • 170128 함수방정식

    2017.10.28
  • Pépin's test

    2017.10.14
  • 게러슨 부등식 (Gerretsen's inequality)

    2017.10.13
  • 고정점으로 함방 풀기 - 예시

    2017.10.10
키타마사법 (Kitamasa method)

참고 : http://cubelover.tistory.com/21 Kitamasa법은 다음과 같이 계수가 결정된 선형 점화식을 갖는 수열의 \(n\)번째 항을 빠르게 결정할 수 있는 방법이다. $$ a_n = c_1 \cdot a_{n-1} + c_2 \cdot a_{n-2} + \cdots c_m \cdot a_{n-m} = \sum_{i=1}^{m}c_{i}a_{n-i} $$ Naive로 풀면 \(O(nm)\) 정도의 시간이 걸리고, $$ \color{red}{\begin{pmatrix} a_{n} \\ a_{n-1} \\ \vdots \\ a_{n-m+1} \end{pmatrix}} = \color{blue}{\begin{pmatrix} c_1 & c_2 & \cdots & c_{m} \\ & & ..

2017. 11. 5. 15:53
Metric TSP와 Christofides' algorithm

0. Introduction TSP는 가장 잘 알려진 NP - complete 문제 중 하나고, 문제 형태가 간단하기 때문에 다양한 variation이 존재한다. 오늘 다룰 것은 거리 공간(Metric) 위에서의 TSP인데, Metric TSP란 정점들을 어떤 거리 공간 \(X\) 위의 점으로 생각할 수 있고, 간선의 weight가 다음의 조건을 만족하는 거리 함수의 형태로 주어지는 TSP를 말한다. - \(d : X^2 \to \mathbb{R}\)- \(d(x,x) = 0 \)- \(d(x,y) = d(y,x) \)- \(\color{blue}{d(x,y)+d(y,z) \ge d(x,z)}\) (삼각부등식) 논의가 어렵게 느껴진다면, 그냥 2차원 평면 위에서 TSP 문제를 푼다고 생각해도 좋다. 안타..

2017. 11. 5. 08:46
170128 함수방정식

미국 가는 비행기에서 친구와 푼 문제이다. 각자 발견한 아이디어를 합쳐보니 꽤 재밌는 풀이가 나와 포스팅해본다. $$ \text{ Find all function } f : \mathbb{N} \to \mathbb{N} \text{ s.t. } \\ \forall a,b\in \mathbb{N} (f(a)+b)\cdot f(a+f(b)) = (a+f(b))^2 $$ (step 1) \(P(a,a) : f( \ a \ + f(a) \ ) = a+f(a) \)즉, \( x + f(x) \)꼴로 나타내어 지는 수들은 모두 부동점이다.\(f\)의 부동점들의 집합을 \(A\)라고 하자. 그렇다면 \(x,y\in A\)에 대해 \(x+y \in A\)임을 쉽게 보일 수 있다. \(\cdots (*)\) (step ..

2017. 10. 28. 16:22
Pépin's test

페르마 수의 primality test에 Miller - Rabin을 쓰면 어떨까? 라는 생각에서 기존 이론을 search하다가 찾아낸 이론인데, 생각해보니 옛날에 배웠던 거다... 그럼 그렇지. $$ F_n = 2^{2^n} + 1 \text{ is prime} \\ \Leftrightarrow 3^{\frac{F_n-1}{2}} \equiv -1 (\text{mod} \ F_n) (n>0)$$ pf)\( \Rightarrow) \)\( \text{by Euler's Criterion,} \) \( 3^{{F_n-1}/2} \equiv \left(\frac{3}{F_n}\right) \)이 때 \(F_n \equiv 2 (mod 3)\)이므로 \(F_n\)은 법 3에 대한 이차잉여가 아니다. \(\le..

2017. 10. 14. 08:46
게러슨 부등식 (Gerretsen's inequality)

게레첸 부등식, 게러첸 부등식이라고 더 많이 알려져 있는 것 같은(...) 이 부등식은 삼각형의 둘레의 절반 \(s = \frac{a+b+c}{2}\), 내접원의 반지름 \(r\), 외접원의 반지름 \(R\)에 관련된 가장 tight한 부등식 중 하나이다. 아마 경시 수준에서 쓰이는 기하부등식 중에선 가장 강한 것 같다. 소개할 증명에서도 상당히 강력한 부등식인 Schur 부등식이 사용된다. $$ 16Rr - 5r^2 \le s^2 \le 4R^2 + 4Rr + 3r^2 $$ (1) Lower bound 클래식한 방법은 부담이 너무 심해서 Lemma를 하나 도입해보았다. \( x := s-a, y := s-b, z := s-c\) \(\text{Lemma : } xy+yz+zx = 4Rr+r^2\) \(..

2017. 10. 13. 03:21
고정점으로 함방 풀기 - 예시

$$ \text{Find all continuous function } f \ : \ \mathbb{R} \to \mathbb{R} \text{ s.t. } \\ \forall x \in \mathbb{R} \ \ f(f(x)) = cos x $$ 페이스북에서 본 흥미로운 문제인데, 굉장히 기교를 많이 필요로 할 것 같지만 의외로 풀이가 원론적이었다. 당연히 내가 풀진 못했고... 조건을 만족하는 \(f\)가 존재한다고 가정하면,우변인 \(\text{cos}x\) 는 단 하나의 고정점(fixed point)을 갖기 때문에, (\(\text{cos} t = t\)를 만족하는 점, \(t \approx 0.7391 \) )이는 \(f\)의 유일한 고정점이어야 한다. 간단히 설명하자면 \(t\) 이외의 고정점..

2017. 10. 10. 00:01
1 ··· 18 19 20 21 22 23 24 25
Tistory Blog (here) Naver Blog
© 2018 T-Story. All right reserved.