알고리즘2 유클리드 호제법 유클리드 호제법(Euclidean Algorithm)유클리드 호제법은 두 수의 최대공약수(GCD)를 효율적으로 구하는 알고리즘이다. 기원전 300년경 유클리드가 저술한 『기하학 원론』에서 소개된 방법이며, 오랜 시간이 지났지만 여전히 가장 널리 사용되고 있다.이론 설명유클리드 호제법은 다음과 같은 성질을 기반으로 한다.a와 b의 최대공약수는 b와 a를 b로 나눈 나머지 r의 최대공약수와 같다.즉, GCD(a, b) = GCD(b, a % b)이 과정을 나머지가 0이 될 때까지 반복하면, 그 마지막 b 값이 최대공약수이다. 이를 간단히 요약하면 다음과 같다.a를 b로 나눈 나머지 r을 구한다.a ← b, b ← r로 값을 갱신한다.b가 0이 될 때까지 위 과정을 반복한다.최종적으로 b가 0이 되었을 때의 .. 2025. 7. 28. 백준 2557번 / B5 / C++ 문제주소 : https://www.acmicpc.net/problem/2557 문제이름 : Hello World 문제번호 : 2557 난이도 : B5 풀이 : 단순 출력 Hello World 성공 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 1119306 451611 315345 39.390% 문제 Hello World!를 출력하시오. 입력 없음 출력 Hello World!를 출력하시오. 예제 출력 1 Hello World! /* 문제주소: https://www.acmicpc.net/problem/2557 문제이름: Hello World 문제번호: 2557 난이도: B5 소요시간: 1m 21s 풀이: 단순 출력 */ #include using namespace std; vo.. 2024. 3. 12. 이전 1 다음