유클리드 호제법5 [C/C++] 프로젝트 오일러 #94 Almost Equilateral Triangles(수학) Project Euler #94: Almost Equilateral Triangles 문제는 “거의 정삼각형” 성질을 가진 삼각형 중에서 주어진 조건을 만족하는 삼각형의 합을 구하는 문제입니다. 정삼각형은 세 변의 길이가 모두 같은 삼각형입니다. 그러나 이 문제에서는 거의 정삼각형(Almost Equilateral Triangles)을 다룹니다. 거의 정삼각형은 다음 조건을 만족하는 삼각형입니다:1. 두 변의 길이가 같고, 나머지 한 변의 길이가 이와 1 차이가 난다. 예: \(a, a, a+1\) 또는 \(a, a, a-1\) 형태2. 삼각형의 세 변이 정수이고, 넓이도 정수여야 한다.삼각형의 넓이 계산 (헤론의 공식)삼각형의 넓이를 구할 때는 헤론의 공식을 사용합니다.세 변이 \(a, b, .. 2024. 11. 16. [C/C++] 프로젝트 오일러 #91 Right Triangles with Integer Coordinates(전체 탐색) Project Euler #91 문제는 좌표 평면에서 원점을 포함하여 세 점을 선택해 직각삼각형을 구성하는 경우의 수를 찾는 문제입니다. 문제의 주요 요구 사항은 다음과 같습니다:1. 평면의 오른쪽 위에 있는 정사각형 영역(예를 들어, 크기  내의 점)을 대상으로 합니다.2. 직각 삼각형의 세 꼭짓점 중 하나는 항상 원점(0,0)에 고정됩니다.3. 나머지 두 점을 선택해 직각이 될 수 있는 경우를 찾습니다.4. 삼각형의 직각은 두 변이 x축 또는 y축과 평행한 경우로 한정됩니다.이 문제는 가능한 모든 점 조합을 조사하여 직각 조건을 만족하는 경우를 계산해야 하므로, 효율적인 알고리즘과 중복을 방지하는 로직이 필요합니다. 제가 작성한 소스는 다음과 같습니다.//-----------------------.. 2024. 11. 11. [C/C++] 백준 #2981 검문(유클리드 호제법) 백준 온라인 저지 문제 2981번 "검문"을 해결하기 위해서는 주어진 수들로부터 차이들의 최대공약수를 구하고, 그 공약수의 약수들을 찾아 출력하는 것입니다. 최대공약수를 찾을 때에는 유클리드 호제법을 이용하면 됩니다. 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2981 ### 주요 함수 및 흐름 설명#### 1. **`gcd(int a, int b)` 함수:** - 두 수의 **최대공약수(GCD, Greatest Common Divisor)**를 구하는 함수입니다. - 유클리드 호제법(Euclidean Algorithm)을 사용하여 `a`와 `b`의 GCD를 구합니다. - **유클리드 호제법**은 다음의 과정을 반복하는 알고리즘입니다: 1.. 2024. 9. 20. [C/C++] 백준 #1850 최대공약수(수학) 이번문제는 문제를 살짝 꼬았지만, 결국 최대 공약수를 구하는 문제입니다. 유클리드 호제법을 이해하고 있다면, 이 문제를 쉽게 풀 수 있습니다. 유클리드 호제법에서 큰수에서 작은수로 나눈 나머지를 가지고 우리는 최대 공약수를 구할 수 있습니다. \[ g = gcd(a, b) = gcd(a-b, b) \] 형태가 성립하기 때문이죠. 위식에서는 뺄셈을 했지만, 나눈 나머지를 해도 됩니다. a 개의 연속된 1이 있는 숫자와 b개의 연속된 1이 있는 숫자 역시 마찬가지죠. \(a \gt b\)라고 한다면, a개의 연속된 1이 있는 숫자를 b개의 연속된 1이 있는 숫자로 나눈 나머지는 a를 b로 나눈 나머지의 개수만큼 1이 연속된 수가 됩니다. 예를 들어서 5개의 1이 연속된 11111 과 3개의 1이 연속된 11.. 2022. 10. 25. 소수 판별하기 우리가 컴퓨터에서 합당한 시간안에 결과를 찾을 수 있는 것은 과연 어느정도의 시간일까라는 생각을 많이 해봅니다. 암호학이라고 한다면, 적어도 100년? 아니면 그 이상일 수도 있겠다는 생각도 하죠. 주어진 수가 소수인지 아닌지, 판별하는 방법은 고전적인 방법에서부터 정수론에 기초한 방법까지 다양하게 있습니다. 소수판별법은 암호학에서 아주 중요합니다. 실제 소수판별을 쉽게 하는 방법이 있다면, 암호 해독도 더 쉬워집니다. 제일먼저 유클리드 호제법을 응용한 방법입니다. [유클리드 호제법을 이용한 소수 판별] bool isPrimeBF(_int64 n) { if( n%2 == 0 ) return false; for( unsigned __int64 r = 3 ; r*r >=1 ) ; for( int i = 0 .. 2014. 10. 7. 이전 1 다음
