코드일기장

유클리드 호제법은 Euclidean Algorithm 은 두 개의 수에서 최대공약수를 구하는 알고리즘이다. 최대공약수를 간단하게 말하자면 두 수 사이의 소인수들의 곱이 최대공약수이다. 우리가 흔히 수기로 최대공약수를 구할 때 소인수분해를 프로그래밍 코드 작성하면 시간 복잡도가 매우 큰 프로그램이 될 것이다. 그 이유는 간단하다. 소인수분해를 하기 위해 소수를 찾아야 하고 그 소수가 두 개의 수에 공통적으로 나눌 수 있는지 여부를 확인해야 하기 때문이다. 코딩으로 최대공약수를 구한다면 시간 복잡도를 줄이기 위해 유클리드 호제법을 사용한다. 유클리드 호제법은 아주 간단하다. 예로 바로 들자면 정수 A = 24 정수 B = 18 두 수의 최대 공약수를 유클리드 호제법으로 구한다고 치자. 24%18 = 6 나머..

에라토스테네스의 체는 소수를 구하는 알고리즘으로 유명하다. "소수가 되는 수의 배수를 지우면 남은 건 소수가 된다는 알고리즘이다." 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 소수가 되는 수의 배수를 지우면 남은 건 소수이다. 2로 예를 들면 자기 자신을 제외한 2의 배수를 지운다. 3도 2처럼 3 자기 자신을 제외한 3의 배수들을 지운다. 특정 숫자만큼 이 과정을 반복한다. 에라토스테네스의 소수 찾기를 다시 간단히 정리해서 설명하면 i=2 일 때, 2를 제외한 2의 배수는 모두 2로 나뉘니 소수가 아니다. import java.io.*; public class PrimeNumber { public static void main(String[] args) throws IOException ..

이진 검색은 선형 검색보다 빠르게 검색할 수 있는 검색 알고리즘이다. 이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서만 사용할 수 있는 알고리즘이다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("요솟수를 입력하세요: "); int N = sc.nextInt(); int[] arr = new int[N]; System.out.println("오름차순으로 입력하세요."); System.out.print("arr[0]: "); arr[0] = sc.nextInt(..

이번 포스팅 글에서는 배열에서 검색하는 방법 가운데 가장 기본적인 알고리즘을 알아보겠다. 이 알고리즘을 선형 검색이라고 한다. 선형 검색의 정의 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞에서부터 순서대로 요소를 비교(검색)를 한다. 이것을 선형 검색(Linear Search)또는 순차 검색(Sequential Search)라고 한다. 선형 검색 기본적인 알고리즘 static boolean SerchMethod(int[] arr, int n, int key) { int i = 0; while (true) { if (i == n) { // i==n이 같다는 것은 키 값과 같은 요소값을 찾지 못한 것 (검색 실패) return false; } if (arr[..