-
2020.11.16
[Project Euler #5][C++] 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수
문제5 : 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수 문제 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. 그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.문제의 조건을 만족시키는 범위를 알 수 없는 수를 찾기 위해 unsigned long long int 자료형을 사용하였다.표현 가능 범위 : 0 ~ 18,446,744,073,709,551,6152중 for 문을 사용하였다.시간 복잡도 : O(n²)1부터 ULLONG_MAX까지 순회하는 for 문1부터 N(20)까지 순회하는 for 문1부터 ULLONG_MAX까지 순회하는 수 중에서,..
-
2017.11.12
[BOJ2609][C++] 최대공약수와 최소공배수
문제두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 예제 입력 24 18 예제 출력 6 72 힌트 출처Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 중등부 1번Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2004 > 고등부 1번 코드 123456789101112131415161718192021222324252627#include using namespace std; // GCD : 최대공약수..
-
2017.08.29
최대공약수 (The Greatest Common Denominator(GCD)), 최소공배수(The Least(Lowest) Common Multiple(LCM))
*최대공약수 (The Greatest Common Denominator(GCD)), 최소공배수(The Least(Lowest) Common Multiple(LCM)) # Algorithm 1 : 간단한 방법(Simple Way)을 이용한 최대공약수(GCD) 구하기 1 2 3 4 5 6 int min(int a, int b) { if (a > b) return b; else if (a =1; g--) if ((m % g == 0) && (n % g == 0)) return g; } Colored by Color Scripter cs # Algorithm 2 : 유클리드 호제법(Euclidean Algorithm)을 이용한 최대공약수(GCD) 구하기 1 2 3 4 5 6 7 8 9 10 11 12 13 14..
