$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

본문 바로가기

전체 글

(113)
Little Piplup 5월 19일 팀연습 Little Piplup의 두 번째 팀 연습 문제셋은 Codeforces Round 500 (Based on EJOI) 로, 지금 우리는 일단 Div.2 수준 문제들을 확실히 푸는게 필요하기 때문에 당분간은 이정도 느낌의 셋으로 연습하는게 좋을 것 같다. 조금 실력 쌓고나면 ARC랑, 쉬운 리저널부터 돌아야지. 3명 팀이 대충 1900정도 되는 퍼플 1명이랑 비슷해 보인다. 레이팅 자체는 내가 1870이긴 한데, 최소 150점은 거품인게 내 눈에도 보이기 때문에(...) 1700정도 레이팅 문제부터 고전하기 시작한다. 문제 번호 A B C D E 문제 레이팅 800 1200 1500 1900 2000 AC 시간(+틀린 횟수) 00:22 (+2) 00:36 (+1) 00:42 (+1) 01:13 02:20..
SNUPS PS-INTRO 4주차 풀이 (3) 3문제 남았다! 원래는 3편 안써도 될거 같았는데, 생각보다 열심히 푸시는 분들이 있어서 굉장히 기쁜 마음으로 (진심입니다 ㅋㅋㅋ) 남은 3문제를 풀어 보자. 마지막 3문제는 더 많은 수학을 요구하는 문제 2개와, 조금 특이한 1문제가 들어가 있다. 11689. GCD(n, k) = 1 매우 유명한 함수인 오일러 피 함수를 구하는 문제이다. 어떤 자연수 $N$ 에 대하여, $1 \leq x \leq N$ 인 수 중 $N$과 서로소인 자연수의 개수를 구하면 된다. 먼저, $N$과 서로소라는 것은, 소인수를 공유하지 않는다 라고 해석할 수 있다. 따라서, $N$을 먼저 적당히 소인수분해해 주자. \[ N = p_1^{e_1} p_2^{e_2} ... \] 이제, $p_1$ 을 공유하지 않는 수를 세 보자. ..
SNUPS PS-INTRO 4주차 풀이 (2) 풀이 포스팅 (1) 에서 풀지 않은 아래 6문제 중 3문제를 먼저 풀자. 가능하면 월요일 중으로 (3) 도 쓰고 싶은데..흠.. 1676. 팩토리얼 0의 개수 이제부터 슬슬 IDE보다는 노트와 펜을 꺼내들어야 하는 문제들을 준비하려고 노력했다. 특히 프로그래밍은 해봤지만, PS 문제풀이 경험이 없는 사람을 대상으로 하는 스터디 특성상 그런 것들이 더 많이 필요하다고 생각하기도 하고.. 먼저, 끝에 0이 왜 많이 나오는지를 생각해 보자. 당연히, 10의 제곱이 많이 들어가기 때문이다. 10의 제곱은 왜 많이 들어갈까? 2랑 5의 제곱이 많이 들어가기 때문이다. 구체적으로, 다음을 간단히 보일 수 있다. 만약 어떤 수 $N$ 을 소인수분해 했을 때, $$ N = 2^m 5^n k$$ 형태이고, k에는 2와 ..
SNUPS PS-INTRO 4주차 풀이 (1) SNUPS에서 나랑 Coffeetea가 같이 PS를 처음 시작하는 사람들을 위한 스터디를 진행하고 있는데, 앞으로는 이 블로그에 내 문제 설명 능력/깔끔하고 알아보기 쉽게 코딩하는것도 연습할겸 해서 풀이를 올려보려고 한다. 이번 주차 주제는 PS를 위한 기초적인 수학으로 준비되었다. 2609. 최대공약수와 최소공배수 단순 구현 문항. 유클리드 호제법을 직접 구현하던가, 귀찮다면 그냥 GCC 내장 함수를 쓰자. 물론 MS C++에는 아마 없는 함수인걸로 알고있지만... 99%의 대회는 GCC니까. #include using namespace std; int main() { int a, b; scanf("%d %d",&a,&b); int g = __gcd(a,b); printf("%d\n%d",g,a*b/..
Codeforces Round 561 (Div. 2) 후기/풀이 이제 막 System Test 까지 끝난 라운드인데, 지금까지 뛰어본 코포 라운드 중 가장 큰 레이팅 상승을 받았다 :) :dhk: 전반적으로 수학적인 센스가 약간 필요했던 라운드라는 생각이 든다. 다른거보다 가장 마음에 드는건, 지난 몇번 라운드가 계속 40분만에 3~4문제 해결 -> 1시간 20분동안 멍때림 -> Hack이나 Systest Fail로 떡락 이 루틴을 따라가서 매우 재미가 없었는데, 오늘은 라운드 끝까지 계속 Active하게 참여할 수 있었다. 스포방지 A. Silent Classroom [문제] 이름의 앞자리를 기준으로 각 글자당 학생의 수를 센 다음, \[_{\frac{n}{2}}C_{2}\] 를 잘 계산해 준다. 홀짝에 따라서 실제로는 3이면 1, 2 식으로 나눠줘야 하지만. 코드..
Road to Expert Round 4 Road to Expert 라는, 그린~민트 -> 블루를 위한 한국인 Codeforce Group이 생겼다는 얘기를 듣고 블루에서 끝없이 뇌절로 떡락해서 온 민트지만 아무튼 민트니까 참여해 보기로 했다. 그룹장님이 3문제 단축셋을 준비해 주시는데, 월요일은 800-900-1000, 수요일은 900-1100-1300, 금요일은 1100-1300-1500 정도라고 한다. 사실 지금 현재 내 레이팅을 생각해보면 금요일 1500 외에는 바로바로 풀어내야 맞긴한데, 세세한 구현실력도 연습할겸 해서 그냥 앞으로 시간되는만큼은 돌아보려고 한다. A. Right-Left Cipher 원본 문제 : Technocup 2019 - Elimination Round 4 A번 어떤 String S에 대해서, T가 다음과 같이 ..
Little Piplup 5월 5일 팀연습 PS 늅늅으로 구성된 Little-Piplup 팀으로 앞으로 대회 등등을 위해 같이 공부하기로 헀다. 처음은 서로 어떤 느낌인지도 볼 겸 해서, Codeforces 에서 Div 1 + 2 Combined 인 라운드 하나 잡고 셋이 같이 돌았다. 팀원 : Coffeetea, Diordhd, Gratus907(나) http://codeforces.com/contest/914 우리한테는 먼 고대의 라운드. 우리가 대학 들어와서 프로그래밍을 처음 시작했고(기억이 맞다면, diordhd는 안드로이드 쪽은 조금 경험이 있지만 PS는 셋다 대학와서 시작했다) , 그게 2018년임을 생각하면 2018년 1월은 Hello World도 출력 못했을 시점이다. 우리가 지금 시점에서 풀 수 있는 문제는 다 풀었다고 생각하지만..
Profile 이제 막 수학이랑 알고리즘 공부하고 있는, 학부 2학년 컴퓨터공학 전공 대학생. 아마 이 블로그에는 공부한거 정리하는 위주로 쓸것 같다. 나름 포트폴리오 인 셈 치자 ㅋㅋㅋ Codeforces Handle : gratus907 Baekjoon Online Judge : gratus907 Project Euler : gratus907