[수학응용] 유클리드 호제법(Euclidean algorithm) 유클리드 호제법최대공약수(Greatest Common Divisor)를 구하는 유클리드 호제법(Euclidean algorithm) 다음 두 명제를 기반으로 한다.첫째, 어떤 두 수가 배수 관계에 있을 때, 두 수 중에서 작은 수는 최대공약수가 된다.둘째, 어떤 두 수의 최대 공약수는 큰 수(피제수 : 나누어지는 수)를 작은 수(제수 : 나누는 수)로 나누었을 때, 그 나머지와 작은 수의 최대공약수와 같다.예를 들어 A, B라는 두 정수의 최대공약수를 구하는 과정은 다음과 같다.A와 B는 Q(몫), R(나머지)와 함께 아래와 같이 나타낼 수 있다.A = Q1*B + R1여기서 A와 B의 최대공약수는 나머지 R1과 B(제수)의 최대공약수와 같다. 따라서 다시 아래와 같은 식을 만들 수 있다.B = Q2*R.. 더보기 [정렬] 선택 vs 버블 vs 삽입 정렬의 종류 - 교환(Exchange) : 버블(Bubble), 퀵(Quick) 정렬 - 삽입(Insertion) : 삽입(Intsertion), 셀(Shell) 정렬 - 병합(Merging) : 2-way 병합, n-way 병합 - 분배(Distribution) : 기수(Radix) 정렬 - 선택(Selection) : 선택(Selection), 힙(Heap) 정렬 선택정렬(Selection Sort) 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환(Exchange)하는 정렬 방식이다. - STEP.1 - STEP.2 - STEP.3 - STEP.4 특성 : 평균 시간복잡도 O(n^2)으로 느린 알고리즘이다. 하지만 최악의 경우도 O(n^2)으로 평균(최선)과 동일하다.정렬의 안정성을 .. 더보기 알고리즘 문제풀이 주의사항 int, long(int)의 범위를 벗어나는 정수를 사용할 때 32비트를 벗어나는 범위의 값을 계산해야 할 때 64비트가 보장되는 long long(int)를 사용한다. 상수를 사용하여 대입시에는 suffix를 붙여주어야 한다.(LL, ll) // 틀린 예 int a = 1000000 * 1024; int b = 1 더보기 이전 1 2 다음
