알고리즘 공부4 [Algorithm] 소수 구하기 알고리즘 3 (에라토스테네스의 체) 소수 판별 알고리즘 3 (에라토스테네스의 체) 알고리즘 목적 1부터 어떠한 수까지 중에 소수인지 아닌지를 판별하는 알고리즘 에라토스테네스의 체 : 소수를 구하는 대표적인 방법 중 하나로 k = 2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수를 제외시키는 방법 알고리즘 방법 k = 2부터 (2부터 소수의 시작임.) √N 이하까지 반복 ( = 소수 판별 알고리즘 2) √N 이하까지 k를 제외한 k의 배수를 제외시키기!! ( 배수를 제외시킨다는 것은 그들은 약수가 있다는 것이기 때문에 소수가 아닌 것.) 나머지가 모두 소수임. *시간복잡도 : N㏒N 실제 알고리즘 구현 (Java) import java.util.Scanner; public class Prime_3 { public stati.. 2023. 2. 16. [Algorithm] 소수 구하기 알고리즘 2 (√N 활용) 소수 판별 알고리즘 2 (√N 활용) 알고리즘 목적 1부터 어떠한 수까지 중에 소수인지 아닌지를 판별하는 알고리즘 알고리즘 원리 : √N 이하의 자연수들로 모두 나눠본다 N 이 약수 p와 q로 이루어져 p x q = N 을 만족할 때 ( 1 ≤ 𝑝 , 𝑞 ≤ 𝐍 ) 의 부등식을 만족함. 즉, p와 q는 반비례관계 (p가 증가하면 q는 감소)로 p와 q 중 하나는 " 무조건 " 제곱근인 √N보다 작거나 같다 √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면, 이는 1 과 N 을 제외한 다른 자연수가 N 의 약수라는 의미로 소수가 아님. √N 이하의 자연수 중에 나누어 떨어지는 수가 없다면, 소수로 판별 * 시간복잡도 (걸리는 시간) : 대략 √N (√N 이하의 자연수들로만 나누기 때문) 실제 알고리즘 .. 2023. 2. 16. [Algorithm] 소수 구하기 알고리즘 1 소수 판별 알고리즘 알고리즘 목적 1부터 어떠한 수까지 중에 소수인지 아닌지를 판별하는 알고리즘 알고리즘 원리 : n-1 이하의 모든 수로 나눠본다. n < 2 이하 (0과 1)은 소수가 아니므로 return n == 2 일 때는 소수 n 을 2부터 n-1까지 나눈 나머지( n%i )가 존재하지 않으면 소수 (약수를 1과 자신만을 가지기 때문. 나머지로는 나눠떨어지지 않기 때문) * 시간복잡도 (걸리는 시간) : 대략 n (n 이하의 모든 수를 검사하기 때문) 실제 알고리즘 구현 (Java) // 소수 판별 메소드 public static void is_prime(int number) { // 0 과 1 은 소수가 아니다 if(number < 2) { System.out.print("소수가 아닙니다");.. 2023. 2. 16. [Algorithm] 이진탐색(Binary Search) 알고리즘 이진탐색 (Binary Search) 이진탐색이란? 이분탐색으로도 불리며 말 그대로 일정한 구간, 범위 등을 2개로 나누어 탐색 범위를 좁혀나가는 탐색 과정 즉, 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘으로 탐색속도가 빠르다는 장점이 있다. 이진탐색 소스코드 구현 (Java) public int binarySearch(int[] arr, int target) { int start = 0; int end = arr.length - 1; int mid = 0; while (start 2023. 2. 15. 이전 1 다음
