[Algorithm] Euclidean algorithm GCD 유클리드 호제법 최대공약수
Euclidean algorithm 은 유클리드 호제법이라고도 하며,이 알고리즘으로 Greatest Common Divisor; GCD 최대공약수를 구할 수 있습니다.(GCD 를 응용해 Least Common Multiple; LCM 최소공배수도 구할 수 있어용) 유클리드 호제법 (GCD 최대공약수)두 양의 정수 a, b (a > b) 에 대하여, a = bq + r (0 a, b 의 최대공약수는 b, r 의 최대공약수와 같다. 즉,gcd(a, b) = gcd(b, r)r = 0 이라면, a, b 의 최대공약수는 b 가 된다. 쉽게 말하자면, 큰 놈과 작은 놈의 최대공약수는,큰놈 % 작은놈 = R 이라고 할 때, (큰놈을 작은놈으로 나눈 후 나머지를 R 이라고 할 때,)R 과 작은놈의 최대공약수와 같..
2025. 6. 15.
[Algorithm] Sorting Algorithms 정렬 알고리즘 <선택, 삽입, 버블, 병합/합병, 퀵, 힙, 카운팅/계수, 기수>
https://www.toptal.com/developers/sorting-algorithms Sorting Algorithms주어진 데이터들을 특정한 기준 혹은 순서(번호나 알파벳 순 같은 어휘)로 정렬하는 것은컴퓨터 뿐만 아니라 도서관의 도서 분류나 상품 진열과 같이 실생활에서도 아주 중요합니다. 특히, (정렬 가능한 형식일 때) 잘 정렬된 데이터들은 *이진탐색으로 빠르게 데이터에 접근할 수 있습니다.(* 이진탐색 : 정렬된 리스트에 중간을 골라, UP or DOWN? 물어보는 방식으로 반의 반의 반... 으로 탐색하는 것) 효율적인 탐색을 위해 다양한 정렬 알고리즘들이 존재하지만, 해당 포스트에서는[Selection, Insertion, Bubble, Merge, Heap, Quick, Count,..
2025. 4. 27.
