jhno

이진 검색(binary search) 이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다. 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 검색을 반복할 때마다 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n이다. 실패할 경우는 log(n+1)회, 검색에 성공한 경우는 log(n-1)회이다 n개의 요소가 오름차순으로 늘어선 배열 a에서 키를 검색하는 과정을 일반적인 방법으로 표현하면 검색 범위 맨 앞 인덱스를 pl, 맨 끝 인덱스를 pr, 중앙 인덱스를 pc라고 지정 검색을 시작할 때는 pl은 0으로, pr은 n-1로, pc는 (n-1)/2로 초기화된다. public class BinSearch { //요솟수가 n인 배열 a에서 key와 같..

선형 검색 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색이다. public class SeqSearch { //요솟수가 n인 배열 a에서 key와 같은 요소를 선형 검색합니다. static int seqSearch(int[] a, int n, int key) { for(int i=0; i

# 다차원 배열 > 배열을 구성 요소로 하는 것이 2차원 배열, 2차원 배열을 구성 요소로 하는 것이 3차원 배열이고, > 이런 배열을 보통의 배열(1차원 배열)과 구별하기 위해 다차원 배열이라고 한다. ## 한 해의 경과 일 수를 계산하는 프로그램 예를 들어 4월 15일의 경과 일 수를 구하면 -> 1월의 일 수 + 2월의 일 수 + 3월의 일 수 + 15 일반적으로 나타내면 m월 d일의 그 해의 경과 일 수는 ->1월,2월....m-1월일 일 수의 합 + d public class DayOfYear { // 각 달의 일수 static int[][] mdays = { {31,28,31,30,31,30,31,31,30,31,30,31}, //평년 {31,28,31,30,31,30,31,31,30,31,3..

소수의 나열 소수는 자신과 1 이외의 정수로 나누어떨어지지 않는 정수 ex) 1,3,5..... 2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않음 package ch2; public class PrimeNumber1 { public static void main(String[] args) { int counter = 0; for (int n = 2; n < 1000; n++) { int i; for (i = 2; i < n; i++) { counter++; if (n % i == 0) // 나누어 떨어지면 소수가 아님 break; // 더 이상의 반복은 불필요 } if (n == i) // 마지막까지 나누어떨어지지 않음 System.out.println(n); } System.out.println("..