urlscan.io logo urlscan.io
SecurityTrails logo

qwerasdfzxcl.tistory.com Open in urlscan Pro
211.249.222.33  Public Scan

Back to summary
Submitted URL: http://qwerasdfzxcl.tistory.com/
Effective URL: https://qwerasdfzxcl.tistory.com/
Submission: On November 20 via api from US — Scanned from DE

Form analysis 1 forms found in the DOM

GET 

<form action="" method="get">
  <legend><span class="blind">컨텐츠 검색</span></legend>
  <input type="text" name="search" title="Search" placeholder="Search" value="" class="inp_search" onkeypress="if (event.keyCode == 13) { try {
    window.location.href = '/search' + '/' + looseURIEncode(document.getElementsByName('search')[0].value);
    document.getElementsByName('search')[0].value = '';
    return false;
} catch (e) {} }">
  <button type="button" title="검색어 삭제" class="btn_search_del"></button>
</form>

Text Content

 * 홈
 * 태그
 * 방명록

 * 분류 전체보기 (38)
   * 공지 (1)
   * 문제풀이 (8)
   * 일기장 (22)
   * 알고리즘 (6)


인기포스트

 * imos-Hanbyeol Trick and its ap⋯
 * 코드포스 IGM 달성 후기
 * 오일러 경로?
 * IOI 2023 후기


ABOUT ME



 * 트위터
 * 인스타그램

Today 27 Yesterday 21 Total 51,757


QWERASDFZXCL의 PS 블로그 QWERASDFZXCL의 PS 블로그

메뉴 검색
컨텐츠 검색


전체 글

 * 오일러 경로?
   알고리즘 2024. 8. 27. 22:09
   
   오일러 경로를 구하는 알고리즘은 다음과 같다.void dfs(int now){ for(int nxt=1; nxt 0){
   g[now][nxt]--; g[nxt][now]--; dfs(nxt); } } printf("%d ", now);} 나는 이 코드와
   알고리즘에 대한 설명을 읽고 이해를 할 수 없었다. "dfs하면서 사이클을 찾으면 끼워 넣는다"로 보통 설명하는 것 같은데, 어떤 사고를
   거치면 저런 코드가 나오는 것일까? 이에 대해 오랜 시간 고민해봤지만 아직도 잘 모르겠다. 그래도 다행인 점은 적어도 내가 납득할 수 있는
   설명을 찾았다는 것이다. dfs(now)를 호출하면 현재 그래프에 남아있는 간선을 사용해서 now로 끝나는 오일러 경로를 출력하게 된다.
   정확히는, 기존에 출력했던 경로 ..
   
   Read More
   
 * PS 일지 (4/19 ~ 5/5)
   카테고리 없음 2024. 5. 4. 21:15
   
   오랜만에 AGC + 랭작을 했다. AGC066A. 체스보드 컬러링 후 mod 2d 기준 0/d로 맞추면 된다.B. 못 풀겠어서 풀이를
   봤다. 5^i는 2를 곱할 때마다 자릿수 합이 감소하는 경향을 보인다. 적당히 5의 거듭제곱을 많이 이어 붙여서 노이즈를 제거하자.C. 못
   풀겠어서 풀이를 봤다. 제거 가능할 필요충분조건은 A가 B의 2배면서 왼쪽이나 오른쪽 끝에 B가 있는 경우다. 이를 이용하면 dp를 할 수
   있다.D. 몇 개의 점은 고정하고 그 주변에 있는 A를 퍼뜨린다는 느낌으로 해를 표현할 수 있다. 각 점을 고정했을 때 영향을 받는 구간을
   모두 구한 후 dp를 돌리면 된다.E. BOJ 18873이랑 같다. 돌의 배치를 고정해두고 swap 가능한 두 점을 모두 찾아보자. 부모가
   자식과 swap 가능..
   
   Read More
   
 * 1^k + 2^k + ... + n^k를 O(k)에 구하기
   알고리즘 2024. 3. 26. 16:44
   
   당연한 말이지만 $\mathbb{Z}_p$에서 생각한다. Lagrange interpolation 구하려는 식은 $n$에 대한 $k+1$차
   다항식이라는 사실이 알려져 있다. 따라서, $k+2$개의 함숫값만 알고 있으면 Lagrange interpolation을 통해 값을 계산할
   수 있다. 함숫값을 구하는 건 거듭제곱을 해야 하기 때문에 $O(k \log k)$의 시간이 걸리고, $f(n)$을 계산하는 것은 역원을
   나이브하게 계산할 경우 $O(k \log p)$의 시간이 걸린다. 사실 이 정도면 충분히 빠르다. TLE가 난다면 쓰레기 문제라는 뜻이기
   때문에 풀지 않는 것을 권장한다. Linear sieve 사실 $i^k$를 $i=0, 1, \ldots, k+1$에 대해 계산하는 것은
   $O(k)$에 가능하다..
   
   Read More
   
 * AlphaGeometry 체험 후기
   일기장 2024. 1. 21. 11:55
   
   https://deepmind.google/discover/blog/alphageometry-an-olympiad-level-ai-system-for-geometry/
   AlphaGeometry: An Olympiad-level AI system for geometry Our AI system
   surpasses the state-of-the-art approach for geometry problems, advancing AI
   reasoning in mathematics deepmind.google 최근 구글 딥마인드에서 mo 기하 문제를 푸는 AI를 발표했다길래
   궁금해져서 직접 설치하고 실행해봤다. https://github.com/google-deepmind/alphageometry 에서 설치할
   수 있..
   
   Read More
   
 * N번째 페리 수열의 K번째 항을 빠르게 구하기
   알고리즘 2023. 11. 26. 23:46
   
   문제0 이상 1 이하인 분모가 $N$이하의 기약분수를 크기 순으로 나열한 수열을 $N$번째 페리 수열 (Farey Sequence)라고
   한다. $N$과 $K$가 주어졌을 때, $N$번째 페리 수열의 $K$번째 원소를 구하여라. BOJ 1882와 동일한 문제고, 올해 ICPC
   예선에도 출제된 문제이다. 이 글에서는 $N$이 고정이고 $K$가 쿼리로 주어질 때 전처리 $O(N^{\frac{2}{3}})$, 쿼리
   $O(\sqrt{N} \log^{1.5}{N})$ 시간에 이 문제를 해결하는 방법에 대해 다룬다. 문제 변형하기$n$번째 페리 수열의
   길이는 $\Theta(n^2)$임이 널리 알려져있다. (서로소인 쌍의 개수의 비율이 $\frac{6}{\pi^2}$에 수렴한다.) 따라서,
   페리 수열을 직접 구하는 방..
   
   Read More
   
 * IOI 2023 후기
   일기장 2023. 9. 11. 15:41
   
   8/28 ~ 9/4에 헝가리에서 열린 IOI 2023에 한국 국가대표로 참가했다. 한국 팀 멤버는 박상훈(qwerasdfzxcl),
   반딧불(79brue), 이동현(lisifu/kizen), 이성호(puppy/windva)였고, 작년에 비해 꽤 강한 멤버였기 때문에 4금을
   노려볼만하다고 생각했다. 나와 동현이는 금메달을 받았고, 딧불이와 성호는 은메달을 받으면서 2금2은의 성적을 기록했고, 국가 순위 5등을
   했다. 작년에도 IOI에 참가했지만 코로나 이슈로 온라인으로 참가하게 되어서 대회만 치고 끝났는데, 올해는 오프라인으로 직접 헝가리도 가고
   여러 행사나 관광을 즐길 수 있어서 매우 좋았다. 솔직히 말하자면 관광은 별 거 없어서 재미없었고 공통 관심사를 가진 외국인 친구들을 많이
   만날 수 있었던 것이 너..
   
   Read More
   
 * imos-Hanbyeol Trick and its applications
   알고리즘 2023. 6. 11. 15:55
   
   (2023.06.11 online IHT with linear memory 문단 추가) 이 글에서는 imos법을 확장한
   imos-Hanbyeol Trick (IHT)의 개념과 응용에 대해 설명한다. imos법 imos법이란 구간 덧셈 업데이트를 빠르게
   처리하는 테크닉이다. 다음과 같은 문제를 생각해보자. 0으로 초기화된 $N \times N$ 크기의 $2$차원 배열 $A$가 주어진다.
   다음 연산을 $Q$개 처리한 후 배열을 출력하여라. $x_1$ $y_1$ $x_2$ $y_2$ $z$:
   $A[x_1:x_2][y_1:y_2]$에 $z$를 더한다. (앞으로 모든 : notation은 닫힌 구간이다.) 나이브하게 했을 때
   시간복잡도는 최악의 경우 $O(QN^2)$이지만, imos법을 사용하면 $O(Q+N^2)..
   
   Read More
   
 * 2023 IOI 멘토교육 5주차
   일기장 2023. 5. 29. 17:17
   
   CEOI 2016을 돌았다. 0:00 ~ 1:47 1번과 2번을 읽었다. 1번은 나이브가 쉽고 풀태는 바로 안 떠올라서 2번을 읽고
   풀었다. 나이브랑 풀태 모두 자꾸 틀려서 시간을 많이 날렸다. 처음에 dnc opt 풀이랑 덱dp 풀이를 내서 둘다 짰는데 둘다 틀린
   풀이였다. 100점 받으려면 대충 비트스트링 들고 다니면서 적당히 dp 돌려주면 O(NTS)에 문제를 해결할 수 있다. 1:47 ~
   3:34 3번을 읽었다. input 노드 루트개 / output 노드 루트개 연결하는 노드들을 만들고 연결하면 47점을 받을 수 있다.
   100점을 받으려면 이를 다중으로 해주면 된다. i번째 층의 노드는 input 노드 P^(i/k)개, output 노드
   P^((k-i)/k)개를 연결하는 노드라고 놓으면 추가 노..
   
   Read More
   

이전
1 2 3 4 5
다음


인기포스트

 * imos-Hanbyeol Trick and its ap⋯
 * 코드포스 IGM 달성 후기
 * 오일러 경로?
 * IOI 2023 후기


ABOUT ME




LINK


ADMIN

admin 글쓰기
51,757 27 21
Designed by Tistory.


티스토리툴바

qwerasdfzxcl의 ps 블로그구독하기





닫기


단축키


내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W


블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C


모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.

(현재)1 / (전체)0


이미지뷰어 라이브러리








0도 회전됨
1배 확대됨