전체 글
-
boj 2436 - 공약수문제풀이/초급 2022. 6. 28. 22:21
http://boj.kr/2436 Baekjoon Online Judge Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다. www.acmicpc.net 문제 설명 최대 공약수와 최소 공배수 a,b가 주어질때 이를 만족하는 수 n,m의 합이 최대가 되도록 하는 문제입니다. 풀이 과정 1 n = a*n' m = a*m' a는 최대 공약수를 의미합니다. 최소 공배수는 두 수의 곱 나누기 최대 공약수 즉 b = n*m/a n,m을 치환 한다면 b = (a * n') * (a * m') / a 이므로 b = a * n' * m'입니다. 풀이 과정 2 일단 a,b의 범위가 1억까지 주어진 것을 보면 O(n)이하의 시간복잡도가 요구 됩니다. 근데 무작위로 두 수를 ..
-
boj 2609 - 최대공약수와 최소공배수문제풀이/초급 2022. 6. 26. 23:50
boj.kr/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 설명 간단한 문제이다. a와 b의 최소 공배수,최대 공약수를 구하면 된다. 풀이 전 게시글에서 최소 공배수에 대해 다루었으니 최대 공약수인 gcd값을 구하는 것만 알아보자. 증명은 넘어가고 코드를 보도록 하겠다. (유클리드 호제법 - 나무위키 (namu.wiki)) 주의할 점은 a가 b보다 크도록 하고 실행해야한다. int gcd(int a,int b){ if(a%b==0)return b; else return gcd(b,a%b); } 더 간결하게 짜는 법은 이와 같다. (삼항 연산자를 사용하도록 하자..
-
boj 5347 - 최소공배수문제풀이/초급 2022. 6. 26. 23:42
boj.kr/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 데이터 케이스 수 n이 주어지고, a,b가 주어지는데 a와 b의 최소 공배수를 구하는 문제이다. 풀이 먼저 간단한 풀이이다. a와 b의 최대 공약수를 gcd이라고 보자. 그렇다면 a=A*gcd,b=B*gcd꼴로 나타낼 수 있다. (단 A,B는 서로소여야한다) ㄴgcd가 최대공약수니 자명하게 서로소다. a와 b의 최대공약수는 a*b/gcd 코드는 위 내용처럼 a와 b를 받고 a*b/gcd를 하면 되는 것이다. a와 b가 백만임으로 int 형으로는 오버플로우가..