레프네 약방

레프네 약방

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

레프네 약방

컨텐츠 검색

태그

조합론 수학 경시수학 물리화학 현대대수학 그래프이론 Problem Solving 화학 대수학 Codeforces ps-hell IMO AOPS 수학문풀 Russian Code Cup 열역학 정수론 함수방정식 더블카운팅 물리

최근글

  • 2021 Jan-Feb Problem Solving
  • ACM-ICPC 2020 Seoul Regiona⋯
  • Constructing Chain Cover of⋯
  • UCPC 2020 본선 후기

댓글

  • 안녕하세요 두 번째 관찰까진 이해했는⋯
  • 갓
  • 네~!
  • 깔끔한 풀이네요~

공지사항

아카이브

  • 2021/03
  • 2020/11
  • 2020/08
  • 2020/02

분류 전체보기(135)

  • BOJ 13318 위험한 해싱

    2020.01.19
  • Blogewoosh #1 translated

    2020.01.14
  • Cayley's theorem in Combinatorics

    2019.12.11
  • solved.ac 티어 매긴 문제들 - Gold 편

    2019.12.08
  • 11/14 신입생세미나

    2019.11.14
  • ICPC Seoul Regional 2019 후기

    2019.11.13
BOJ 13318 위험한 해싱

https://www.acmicpc.net/problem/13318 13318번: 위험한 해싱 string matching 알고리즘에는 여러 가지가 있다. KMP 알고리즘이나 Boyer­Moore 알고리즘이 그 예시이다. 하지만 지구이는 KMP를 이해할 수 없었고, Boyer­Moore는 시간복잡도가 너무 컸다. 결국 지구이는 틀릴 확률이 있지만, 간단한 방법인 해싱을 즐겨 사용하게 되었다. 해싱은 문자열을 숫자 하나로 바꾸는 해시 함수를 하나 정의한 후, 이 값이 같은지 다른지를 통해 문자열이 같은지 판별하는 방법이다. 지구이는 해시 함수를 다음 www.acmicpc.net 풀이 두 해시값을 뺀 다항식을 생각하면, 그 다항식은 아래와 같은 조건을 만족해야 한다. \(\deg f < 300000\) \(..

2020. 1. 19. 13:48
Blogewoosh #1 translated

원본: https://codeforces.com/blog/entry/61205 Blogewoosh #1 - Codeforces codeforces.com Radewoosh의 블로그에 올라온 신기한 트릭을 리뷰한다. 해결해야 할 원본 문제는 여기서 볼 수 있다. https://szkopul.edu.pl/problemset/problem/wTy-sxQCIKry0Ml-6RvM0L78/site/?key=statement Zadanie Różne słowa (slo) - Problemset - SZKOpuł Congratulations, you solved it! The problemset isn't perfect, but we always aim to make it better. To do that we nee..

2020. 1. 14. 16:57
Cayley's theorem in Combinatorics

조합론에서의 Cayley's theorem은 완전그래프 \(K_{n}\)의 서로 다른 spanning tree가 \(n^{n-2}\)개라는 정리이다. 일반적으로는 그 쓰임보다도 아름다운 증명에 가치를 둔다. Functional graph를 알고 있다는 전제 하에 글을 작성했다. Reference : Miklos Bona - [A Walk through Combinatorics] cf : \([n] := \{1,\dots,n\}.\) Proof (By A. Joyal) \(K_{n}\)의 spanning tree의 개수를 \(t_{n}\)이라고 두고, \(n^{2}t_{n} = n^{n}\)임을 보인다. Definition. 정점 \(n \ge 1\)개의 트리 \(T\)에서 정점 \(a, b\)를 골라 \..

2019. 12. 11. 04:21
solved.ac 티어 매긴 문제들 - Gold 편

Baekjoon Online Judge에는 유용한 문제 난이도 기능 solved.ac 가 있다. 내가 기여한 문제들의 풀이를 간략하게 써보려고 한다. 아마 Gold, Platinum이 주류가 될 것 같고, Diamond 이상은 개별 풀이 포스팅을 할 것 같다. 형식은 문제 번호 (내가 준 티어) 순이다. Gold / Platinum / Diamond 수준의 구분은 신경을 쓰지만, Gold I ~ V의 세부적인 분류는 문제를 푼 직후에 즉흥적으로 내린 경우가 더 많다. 참고 정도만 하자! BOJ 1762. 평면그래프와 삼각형 (Gold II) 불러오는 중입니다... BOJ 2026. 소풍 (Gold III) Last update 19.12.16. 더보기 Maximal clique problem의 결정 문제..

2019. 12. 8. 20:16
ICPC Seoul Regional 2019 후기

스코어보드는 여기서 볼 수 있다. 5, 6위팀과 페널티 4분이라는 근소한 차이로 전체 4등 / 90팀으로 대회를 마무리했다. 예선 본선 모두 4등이다. 팀원은 imeimi, TAMREF, jhhope1. A Bus With No Drivers 팀처럼 컴공과가 한 명밖에 없는 팀이다 ㅋㅋ 팀 전략, 사전 연습, 팀노트 즈홒(jhhope1)은 풀이를 내는 능력이 뛰어난 데 비해 아직 구현이 익숙하지 않았고, 나는 코딩이 빠른 편이지만 풀이를 잘 못 만들었다. imeimi는 단점이 없다. 그냥 이멘이다 ㅋㅋㅋ 그래서 즈홒은 코딩을 잡지 않았고, 내가 Soulless Coding Machine 역할을 하면서 즈홒과 이멘이 주는 풀이를 구현하는 위주의 전략을 사용했다. 레드코더 2 ~ 2.5명 정도가 팀에서 낼 ..

2019. 11. 13. 12:25
1 2 3 4 5 ··· 23
Tistory Blog (here) Naver Blog
© 2018 T-Story. All right reserved.