최소공배수

[21919] 소수 최소 공배수(C++)

문제 행복이는 길이가 $N$인 수열 $A$에서 소수들을 골라 최소공배수를 구해보려고 한다. 행복이를 도와 이를 계산해주자. 입력 첫째 줄에 수열 $A$의 길이 $N$이 주어진다. $(1 \le N \le 10,000)$ 그 다음줄에는 수열 $A$의 원소 $A_{i}$가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 답이 $2^{63}$ 미만인 입력만 주어진다. 출력 첫째 줄에 소수들의 최소공배수를 출력한다. 만약 소수가 없는 경우는 -1을 출력한다. 해결 방법 이 문제의 핵심은 1️⃣ 수열의 원소는 중복될 수 있음 2️⃣ 소수들의 최소공배수를 구하는 것 위와 같다. {2, 3, 3, 4, 5, 5, 8}과 같이 수열에 중복된 원소가 들어갈 수 있는데 우리가 찾고자 하는..

Google SWE Online Coding Challenge Internship 2021

GOCC15: Google SWE Online Coding Challenge Internship 2021 - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org ✔️ Second Question: Divisibility Count Find the number of N digit integers divisible by b..

[2609] 최대공약수와 최소공배수(C)

문제 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 프로그래머스 1단계 두 문제 중에 첫번째 문제가 이 문제와 유사한 문제였다. 왠걸.... 알고리즘이 생각이 안나... 분명 이 문제를 풀고 심지어 발표도 했었는데 이게 기억이 안나다니 진짜 심각성을 느끼고 기초부터 다시 잡기 위해 10달전 문제를 리뷰해보려고 한다^^ 🔎 해결 방법 이 문제의 알고리즘이 기억나지 않았던 이유는 단순하다. 그 당시에 내것으로 만들지 않았기 때문... 최대공약수를 구하기 위해서는 유클리드 호제법이라는 알고리즘을 사용하면 되고 최소공배수를 구하기 위해서는 미리 구해두었던 최대공약수를 활용해서 구할 ..