[알고리즘 #6] 최대공약수 최소공배수 구하는 알고리즘 정리
** Responsive Ad ** 1. 최대공약수 (Greatest Common Factor, GCF) 두 개 이상의 수가 공통으로 가지고 있는 약수 중 가장 큰 수 8의 약수 : 1, 2, 4, 8 12의 약수 : 1, 2, 3, 4, 6, 12 8과 12의 최대공약수 : 4 2. 최소공배수 (the Least Common Multiple, LCM) 두 개 이상의 수가 공통으로 가지는 배수 중 가장 작은 수 3의 배수 : 3, 6, 9, 12, 15.. 5의 배수 5, 10, 15, 20.. 3과 5의 최소공배수 : 15 3. 서로소 (relative prime) 1 외의 공약수를 갖지 않는 두 수 ex) 7, 11 는 1 외의 공약수가 없으므로 서로소이다. 4. 최대공약수 구하는 알고리즘 1) 유클..
2017. 3. 22.
[알고리즘 #4] 약수(divisor) 구하는 알고리즘 정리
** Responsive Ad ** 1. 약수 (divisor, aliquot)어떤 수를 나누었을 때 나머지가 0이 되는 수, 제수(除數) 2. N의 약수를 구하기 위한 접근방법 1) 1부터 N까지 차례로 나누어 나머지가 0이 되는지 확인 2) sqrt(N) 보다 작은 약수를 먼저 구한 뒤 이를 이용하여 sqrt(N) 보다 큰 약수 구하기 100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100 sqrt(100) = 10 이므로 1,2,4,5 를 구한 뒤,100 / 1 = 100100 / 2 = 50100 / 4 = 25100 / 5 = 20 으로 sqrt(100)보다 큰 약수를 구한다. ** 큰사각형 광고 **
2017. 3. 22.
[알고리즘 #3] 소수 판별 알고리즘
** 반응형 광고 ** 1. 소수 (prime number) 란? 1과 자기 자신만을 약수로 가지는 수로 1보다 큰 수 (2, 3, 5, 7, 11, 13 ..) 2. 소수 판별법 1) 나머지가 0인 수 검사어떤 수 A가 소수인지 판별하기 위해서는 A를 2부터 A보다 1작은 수까지 나누어서 나머지가 0인 경우가 있는지 검사함.MOD(A, 2) ~ MOD(A, A-1) = 0 인 경우를 check 2) 제곱근 이용 어떤 수 A의 제곱근까지의 수 중 한 개의 수에 대해서라도 나누어 떨어지면 소수가 아님.MOD(A, 2) ~ MOD(A, SQRT(A)) = 0 인 경우를 check당연히, 1) 의 방식보다 성능이 좋다. 3. 에라토스테네스의 체 1~N 까지의 수 중에서 소수를 구하고자 한다면 에라토스테네스의 ..
2017. 3. 16.
[알고리즘 #2] 수열의 종류 정리
** 반응형 광고 ** 1. 수열이란? (series, progression, sequence) 일정한 규칙에 따라 차례대로 나열된 수의 열 2. 등차수열 (Arithmetical Series) 1,3,5,7.. => A + (n-1) * D (A: 초기값, n: 차수, D: 증분) 3. 등비수열 (Geometric Series)1,2,4,8.. => 2e(n-1) 4. 계차수열수열 A의 이웃한 두 항의 차로 이루어진 수열 B가 있을 때, 수열 B를 수열 A의 계차수열이라고 함.수열 A : 3,5,9,15,23.. 수열 B : 2,4,6,8.. => ne2 - n + 3 5. 조화수열분수형태의 수열의 역수를 취하면 등차수열이 되는 수열1,1/3,1/5,1/7 => 1/2n-1 6. 누승수열 (Factor..
2017. 3. 8.
알고리즘 영상 강의 일목요연 정리하기
New-1 알고리즘 영상강의를 정리한 내용입니다. 많은 도움 되길 바랍니다. [강좌0]1. 시간복잡도2. O 분석 (N은 입력값) logN이 제일 좋음, N, NlogN이 다음으로 좋음 N 3승이 제일 안좋음 [강좌1. 알고리즘과 기초자료 구조]1. 알고리즘이란 * 요건 : 입력, 출력, 명확성, 유한성, 유효성 * 분석기준 : 정확성, 작업량, 사용공간, 단순성, 최적성 => 가장 효율적인 알고리즘을 개발, 구현 하여야 한다. 2. 자료구조란 * 정의 : 데이터와 그들의 관계를 조직화, 구조화 하는 것 (입력, 출력값을 조직화 구조화) * 형태 1) 선형 : 리스트, 스택, 큐 2) 비선형 : 트리, 그래프 3. 배열 * 특성 1) 같은 종류의 자료의 집합을 담는 가장 일반적인 자료구조 2) 연속된 메..
2015. 2. 1.
