2609번: 최대공약수와 최소공배수

2609번: 최대공약수와 최소공배수사용 언어: C++문제 요약두 수의 최대공약수와 최소공배수를 출력하라!풀이문제는 브론즈 수준이지만, 일단 최대공약수와 최소공배수를 구하는 가장 효율적인 방법을 아는 것은 중요한 법!유클리드 호제법을 통해 최대공약수(GCD)를 구하고, 이를 이용해 최소공배수(LCM)를 구할 수 있다. 유클리드 호제법은 다음과 같다.두 수 a, b의 GCD는 다음 재귀 공식으로 구한다.GCD(a, b) = {a (if b =0) {GCD(b, a%b) otherwise코드로 표현하면 다음과 같다.int gcd(int a, int b){ if(b==0) return a; return gcd(b, a%b);}그리고 LCM는 GCD를 이용해서 ..

1978번: 소수 찾기 (BOJ C++)

1978번: 소수 찾기 사용 언어: C++ 풀이 아래의 코드는 O(n)이지만, O(루트n)에 코드를 짤 수 있다. 해당 숫자의 루트 n까지만 확인하면 된다는 사실을 사용하는 것이다. for(int i=2; i*i> num; bool flag; while(num--) { int isPrime; flag = true; cin >> isPrime; if(isPrime == 1) continue; for(int i=2; i

1990번: 소수인팰린드롬 (BOJ C/C++)

1990번: 소수인팰린드롬 사용 언어: C 문제 151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되고 이 두 수가 다르기 때문에 팰린드롬이 아니다. 두 정수 a, b가 주어졌을 때, a이상 b이하인 소수인 팰린드롬을 모두 구하는 프로그램을 작성하시오. 입력 입력은 첫째 줄에 공백으로 구분된 두 자연수 a, b가 주어진다. 단 5 ≤ a < b ≤ 100,000,000 이다. 출력 첫째 줄부터 차례로 증가하는 순서대로 한 줄에 한개씩 소수인 팰린드롬을 출력한다. 마지막 줄에는 -1을 출력한다. 틀린 풀이 결과적으로는 메모리 초과가 떴다. 아마도 arr[10..