-
구사과와 함께하는 PS-PT 2주차
Intro Greedy Termite (ICPC Tehran Site 2019) 다음으로 갈 위치를 빠르게 구할 수 있으면 문제를 풀 수 있습니다. 현재 $i$번째 막대기에 있다고 할 때, 다음으로 갈 막대기 $j$의 조건은 다음과 같습니다. $H_j - \vert X_i - X_j \vert$가 최대 $\vert X_i - X_j \vert$가 최소 $j$가 최소 절댓값 기호는 사회악이므로 $X_i$와 $X_j$의 대소 관계에 따라 식을 조건을 다시 정리해봅시다. $X_j < X_i$인 경우 (왼쪽으로 이동하는 경우) $H_j + X_j - X_i$가 최대 $X_i - X_j$가...
justiceHui's profile imagejusticeHui
2021-08-10 22:00
-
구사과와 함께하는 PS-PT 1주차
Intro justiceHui와 Ryute가 같이 작성했습니다. Virus Experiment (JOIOC 19 3번) Subtask 2 (6점) 적절한 전처리를 통해 $(r, c)$가 감염되기 위해서 이웃들이 감염되어야 하는 조합을 $O(16RC)$ 시간에 모두 구할 수 있습니다. (ex. 이웃이 감염된 상태가 $\left{ N, SW, WE, SE \right}$ 중 하나 이상을 포함하면 $(r, c)$도 감염됨) 위와 같은 전처리를 모두 수행했다면, $U_{r,c} \neq 0$인 모든 $(r, c)$에 대해 BFS 등을 이용해서 시뮬레이션을 하면 $O(R^2C^2)$ 시간에 문제를 풀 수 있습니다. 코드 Subtask 3 (100점) 깔끔한...
justiceHui's profile imagejusticeHui
2021-08-02 02:00
-
정확도 높은 FFT와 NTT
FFT에서는 실수 자료형을 사용하기 때문에 실수 오차가 발생할 수 있고, 이는 즐거운 PS생활에 큰 지장을 줄 수 있습니다. 특히 FFT 문제에서 수가 너무 크기 때문에 M으로 나눈 나머지를 출력한다.와 유사한 문장이 나온다면 실수 오차를 만나는 것을 각오해야 합니다.이 글에서는 M으로 나눈 나머지를 출력한다.같은 문장이 나오는 문제에서 약간의 속도를 희생해 FFT의 정확도를 높이는 방법과 정수만 이용해서 FFT를 하는 방법에 대해 다룹니다. ※ 이 글은 독자가 분할 정복을 이용한 FFT 알고리즘(쿨리-튜키 알고리즘)을 알고있다는 전제 하에 설명합니다.쿨리-튜키 알고리즘을...
justiceHui's profile imagejusticeHui
2020-05-20 16:00
-
랜덤으로 문제 풀기
서론 알고리즘 문제를 풀 때 랜덤을 사용해 문제를 해결하는 경우가 있습니다. 최악의 시간 복잡도와 평균 시간 복잡도가 많이 차이나는 알고리즘을 사용하는 경우에 최악의 상황을 피할 때 사용하기도 하고, 무작위 선택을 여러 번 시도하는 것으로 틀릴 확률을 줄이는 용도로 사용하기도 합니다. 이 글에서는 랜덤을 이용해 여러가지 문제를 통해 문제 풀이에 랜덤을 적용하는 방법을 다룹니다. 목차 랜덤을 이용해 평균 복잡도 보장시키기 퀵정렬 Smallest Enclosing Circle 재밌는 인터랙티브 문제 BOJ18192 보고 정렬 랜덤을 여러 번 시도해 틀릴 확률...
justiceHui's profile imagejusticeHui
2020-03-23 02:27
-
AlgoShitPo 규칙 (2020.02.17)
주제 Pool 글 안 쓰는 사람은 1개 이상의 주제 추가 외부에서도 주제 제안 받음 주제 추가는 깃허브 이슈로 관리 포스팅 주제 선정 주제 pool에서 원하는 주제 선택해서 작성 주제 겹치면 먼저 선점한 사람이 가져감 자신이 제안한 주제는 선택하지 않는 것이 강력히 권장됨 인원 부족시 인원이 모자르면 명시적으로 휴식기 선언 인원 Pool 인원 풀 고정 4명 작성, 나머지 검수 글 작성할 사람 4명 선발 하고 싶은 사람 + 가장 예전에 글 올린 사람 5명 이상 넘어가면 가장 최근에...
justiceHui's profile imagejusticeHui
2020-02-17 03:21
-
번사이드 보조 정리
첫 번째 주의 AlgoShitPo에서 ahgus89의 지목을 받아 Burnside’s Lemma를 작성하게 된 justiceHui입니다. 서론 번사이드 보조 정리는 원순열 등의 경우의 수를 구하는 문제에서 자주 나오는 정리입니다. 공부하기 위해 책을 보거나 검색을 하면, $\displaystyle \frac {1}{n}\sum_{k=1}^{n} c(k)$같은 공식만 나와있거나 Group Theory가 튀어나오는 경우가 대부분입니다. 저는 고등학교에 재학중인 학생으로써, 고등학교 수준에 맞춰 번사이드 보조 정리의 아이디어를 소개하는 것에 초점을 맞추도록 하겠습니다. 문제 1 위 그림처럼 구슬 4개로 구성된 목걸이가 있을 때, 각 구슬을 빨간색 혹은 파란색으로 색칠하는 경우의...
justiceHui's profile imagejusticeHui
2020-02-09 00:00
-
기여 방법 안내서
author 등록 /_authors/<username>.md 파일 생성 후 아래 내용 작성 (프로필 사진은 /files/authors/<profile_image>.jpg 형식으로 업로드) --- name: <username> title: <title> image: /files/authors/<profile_image>.jpg --- tag 등록 /_tags/<tag_name>.md 파일 생성 후 아래 내용 작성 (각각 약자/풀네임 추천) --- name: <tag_name> title: <title> --- post 등록 /_posts/YYYY-MM-DD-title.md 파일 생성 후 아래 내용 작성 --- layout: post title: '<title>' author: <username> date: YYYY-MM-DD mm:ss tags: [tag1,tag2,tag3,tag4] --- 내용 작성 이미지 첨부 files/<image.xxx> 형식으로 올려서 사용해도 되고, imgur 같은 서비스 이용해도...
justiceHui's profile imagejusticeHui
2020-02-04 03:10