승코딩당당당

문제[C++] 백준 1850: 최소공약수 SILVER 1 https://www.acmicpc.net/problem/1850 접근 방법백준 1850번은 두 정수 A와 B가 주어졌을 때, 각각이 1로만 이루어진 수(1111… 형태) 라고 생각하고그 둘의 최대공약수에 해당하는 1의 개수를 출력하는 문제다. 핵심 아이디어는 다음과 같다.111…(A개) 와 111…(B개)의 최대공약수는1이 GCD(A, B)개 있는 수가 된다. 즉,두 수의 최대공약수를 먼저 구하고그 개수만큼 1을 출력하면 된다.따라서 문제의 본질은 두 수의 최대공약수(GCD)를 구하는 것이다.유클리드 호제법을 이용하면 효율적으로 계산할 수 있다.int GCD(ll a, ll b){ if (a % b == 0) return b;..

문제[C++] 백준 1934: 최소공배수 BRONZE 1https://www.acmicpc.net/problem/1934 접근 방법백준 1934번은 두 수의 최소공배수(LCM) 를 구하는 문제다.최소공배수를 직접 구하기보다는, 다음 공식을 이용하면 훨씬 쉽게 해결할 수 있다.LCM(a, b) = a × b ÷ GCD(a, b) 따라서 문제의 핵심은 최대공약수(GCD) 를 구하는 것이다.최대공약수는 유클리드 호제법을 이용하면 효율적으로 구할 수 있다.https://xeungcoding.tistory.com/106 유클리드 호제법 (euclidean-algorithm)코딩 테스트에서 수학 알고리즘 문제를 풀다 보면 자주 등장하는 개념이 바로 최대공약수(GCD)이다. 최대공약수를 구하는 가장 기본적인 방법은..

코딩 테스트에서 수학 알고리즘 문제를 풀다 보면 자주 등장하는 개념이 바로 최대공약수(GCD)이다. 최대공약수를 구하는 가장 기본적인 방법은 두 수를 소인수 분해한 뒤, 공통된 소수들의 곱을 구하는 것이다.하지만 이 방법은 구현이 번거롭고, 큰 수에 대해서는 비효율적이다. 이를 훨씬 간단하고 빠르게 구할 수 있는 방법이 바로 유클리드 호제법(Euclidean Algorithm) 이다.이번 글에서는 유클리드 호제법의 원리와 동작 과정, 그리고 왜 이 방법이 효율적인지 정리해보려고 한다. ✍️ 유클리드 호제법이란?유클리드 호제법은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘이다.이 알고리즘의 핵심 아이디어는 다음과 같다.두 수 A와 B에 대해 A를 B로 나..

문제[C++] 백준 11689: GCD(n, k) = 1 GOLD 1https://www.acmicpc.net/problem/11689 접근 방법이 문제는 어떤 수 n에 대해, 1부터 n까지의 수 중에서 n과 서로소인 수의 개수를 구하는 문제다.이는 곧 오일러 피 함수 φ(n)를 구하는 문제이고, 공식을 이용하면 다음처럼 쓸 수 있다.여기서p∣n 은 “p가 n의 약수(소인수)”라는 뜻곱은 “n의 서로 다른 소인수들”에 대해서만 한 번씩 해주면 된다.즉,n을 소인수분해해서 서로 다른 소인수 p 들을 찾고ret에 ret = ret * (1 - 1 / p)를 순서대로 적용해 주면 최종적으로 ret이 φ(n)이 된다.이 공식을 그대로 구현하면, n이 최대 범위일 때도 O(√n) 안에 해결할 수 있다. 상세 아..

수학 기반 알고리즘 문제 중에서는 정수론(Number Theory) 개념을 묻는 문제가 종종 등장한다.그중 대표적인 개념이 바로 오일러 피 함수(Euler’s Totient Function) 이다.처음 보면 다소 생소할 수 있지만, 원리를 이해하면 에라토스테네스의 체와 매우 유사한 구조를 가진다.https://xeungcoding.tistory.com/58 소수(prime number) 구하기 - 에라토스테네스의 체그래프나 탐색 알고리즘뿐만 아니라, 코딩 테스트에서는 수학적 개념을 코드로 구현하는 문제도 자주 출제된다.그중 대표적인 주제가 바로 소수 구하기이다.소수는 정의 자체는 단순하지만, 입xeungcoding.tistory.com 이번 글에서는 오일러 피 함수의 정의와 원리,그리고 배열을 이용한 계..

문제[C++] 백준 1016: 제곱 ㄴㄴ 수 GOLD 1https://www.acmicpc.net/problem/1016 접근 방법구간 [Min,Max][Min, Max][Min,Max] 안에 있는 수들 중에서 어떤 소수 p에 대해 p^2로 나누어떨어지지 않는 수(= 제곱 ㄴㄴ 수)의 개수를 세는 문제이다. 즉, 구간 안에서 2^2, 3^2, 5^2, ... 이런 제곱수들로 나누어 떨어지는 수는 다 제외하고 남는 숫자의 개수를 세면 된다. 하지만 여기서 중요한 제약은 이와 같기 때문에,단순히 1 ~ Max까지 배열 만들어서 에라토스테네스 같은 걸 돌리거나매 수마다 제곱수 나눠보는 방식으로는 시간/메모리 초과가 난다.그래서 이 문제는 “전체를 다 보는 게 아니라, [Min, Max] 구간만 슬라이딩해서 ..