$$\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)}$$

'알고리즘 문제풀이/SNUPS PS Intro 2019' 카테고리의 글 목록::::Gratus' Blog

"알고리즘 문제풀이/SNUPS PS Intro 2019" 관련 글 3

SNUPS PS-INTRO 4주차 풀이 (3)
알고리즘 문제풀이/SNUPS PS Intro 2019 2019. 5. 21. 04:01
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)
알고리즘 문제풀이/SNUPS PS Intro 2019 2019. 5. 20. 03:32
풀이 포스팅 (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 PS Intro 2019 2019. 5. 19. 21:25
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/..
admin

티스토리툴바