💡 유클리드 호제법이란?유클리드 호제법은 두 수의 최대 공약수(GCD)를 구하는 효율적인 알고리즘입니다.일반적으로 최대 공약수를 구할 때 소인수분해를 이용할 수 있지만, 유클리드 호제법을 사용하면 더욱 간단하게 해결할 수 있습니다.유클리드 호제법(euclidean-algorithm)은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법을 사용하면 좀 더 간단하게 구현 가능하다💡 유클리드 호제법의 핵심 원리이 알고리즘은 MOD(나머지 연산)을 기반으로 작동합니다.MOD 연산: 두 수를 나눈 후 나머지를 구하는 연산예) 10 MOD 4 = 2🔢 유클리드 호제법 구현 과정1️⃣ 두 수 중 더 큰 ..

📌 오일러 피 함수 P[N]란?오일러 피 함수 'φ(N)'은 1부터 N까지의 자연수 중에서 N과 서로소인 자연수의 개수를 구하는 함수서로소란 두 수의 최대공약수(GCD)가 1인 경우를 의미예를 들어, φ(6) = 2 ➡️ 1과 5가 6과 서로소이기 때문😊📌  오일러 피 함수의 핵심 이론✨오일러 피 함수는 에라토스테네스의 체와 유사한 방식이라고 생각할 수 있다.1️⃣ 구하고자 하는 범위만큼 배열 초기화P[i]=i로 초기화하여 각 숫자 i에 대해 일단 후보 값을 그대로 설정2️⃣ 소수인 경우만 처리2부터 시작하여 P[i]=i인 경우, 해당 숫자는 소수이때, 현재 선택된 숫자 K의 배수에 해당하는 값들을 업데이트업데이트 방식:P[i]=P[i]−P[i]/K (소수 K에 대해 모든 배수 i에 적용)3️⃣ 모..

📌 소수(Prime Number)란?소수는 자신보다 작은 두 개의 자연수를 곱해 만들 수 없는, 1보다 큰 자연수를 말한다.즉, 1과 자기 자신 외에는 약수가 존재하지 않는 수예) 2, 3, 5, 7, 11, 13, ... 📌  소수 구하기의 핵심 이론✨💡에라토스테네스의 체 원리소수를 구할 때 가장 널리 사용되는 알고리즘! 빠르고 효율적으로 소수를 찾을 수 있다. 🌟 1️⃣ 구하고자 하는 소수의 범위만큼 1차원 배열 생성배열의 각 값을 "소수인지 아닌지"를 나타내는 플래그로 사용한다.예를 들어, true면 소수, false면 소수가 아니다.2️⃣ 2부터 시작해서, 현재 숫자가 소수일 때, 그 배수들을 모두 제거배수는 소수가 될 수 없으므로 지워준다.단, 처음 선택한 숫자는 지우지 않음!3️⃣ 다음..

📌  그리디 알고리즘이란?그리디 알고리즘(탐욕 알고리즘)은 문제를 해결하는 과정에서 현재 상황에서 가장 최선이라고 생각되는 선택을 반복적으로 하여 최적의 해를 구하려고 하는 알고리즘이다.  즉, "지금 가장 좋아 보이는 것을 선택하는 것이 최종적으로도 가장 좋은 선택!" 이라는 가정을 기반으로 동작한다. 하지만 항상 최적의 해를 보장하지는 않는다! 그리디 알고리즘이 성공하려면 특정한 조건들이 충족되어야 한다. 😅🔍 그리디 알고리즘의 주요 특징1️⃣ 지역 최적해(Local Optimal Solution)현재 단계에서 가장 최선의 선택을 반복적으로 선택이 선택이 전역 최적해(Global Optimal Solution)가 될 것이라고 가정2️⃣ 단순하고 빠른 해결 방법복잡한 계산 대신 현재 상태에서 최선..