Java/자료구조 (7) 썸네일형 리스트형 3-3 이진 검색 1. 이진 검색 이진 검색(binary search) - 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 - pl = 검색 범위의 맨 앞 인덱스 , 0 - pr = 검색 범위의 맨 끝 인덱스 , n-1 - pc = 검색 범위의 중앙 인덱스 , (n-1)/2 - 이진 검색을 한 단계씩 진행할 때마다 검색범위가 반으로 좁혀짐 1) a[pc] key일 때 - a[pc] ~ a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외 - 검색 범위를 중앙 요소 .. 3-2 선형 검색 1. 선형 검색 선형 검색(linear search) - 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색 - 선형 검색에서의 배열 검색의 종료 조건 1) 종료 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 -> 검색 실패 2) 종료 검색할 값과 같은 요소를 발견한 경우 -> 검색 성공 - 배열의 요솟수가 n개 일때 종료 조건 1,2를 판단하는 횟수는 평균 n/2회 ex) 2를 검색 5를 검색 - 요솟수가 n인 배열 a에서 값이 key인 요소를 검색하는 코드 int i=0; while(true) { if(i==n) return -1; //검색 실패(-1을 반환) if(a[i] == key) return i; //검색 성공(인덱스를 반.. 3-1 검색 알고리즘 1. 검색과 키 - 데이터 집합에서 원하는 값을 가진 요소를 찾아냄 ex) - 주소록 검색 1. 국적이 한국인 사람을 찾습니다. 2. 나이가 21세 이상 27세 미만인 사람을 찾습니다. 3. 찾으려는 이름과 가장 비슷한 이름을 가진 사람을 찾습니다. - 이러한 검색은 특정 항목에 주목한다는 공통점이 있음 - 키(key) = 주목하는 항목 1. 키값과 일치하도록 지정(한국) 2. 키값의 구간을 지정(21세 이상 27세 미만) 3. 키값과 비슷하도록 지정(발음이 가장 비슷한 이름) - 조건은 하나만 지정하기도 하지만 논리곱이나 논리합을 사용하여 여러 조건을 복합해서 지정하기도 함 2. 배열에서 검색하기 활용 알고리즘 1) 선형 검색 - 무작위로 늘어서 있는 데이터 모임에서 검색을 수행 2) 이진 검색 - 일.. 2-2 클래스 1. 클래스 다루기 클래스(class) - 여러 형의 요소를 조합하여 만든 자료구조 ex) //클래스 XYZ class XYZ { int x; long y; double z; } - 클래스 XYZ는 3개의 데이터 요소를 가지고 있음 - 데이터 요소를 필드(field)라고 함 - 클래스형 변수를 사용할 때는 먼저 클래스형 변수(실체를 참조하는 변수)를 만들고, 그와 동시에 실체인 클래스 인스턴스를 생성 XYZ a; //XYZ형의 클래스형 변수 a 선언 a = new XYZ(); //XYZ형의 클래스 인스턴스를 생성하고 참조하는 곳을 대입 - 클래스형 변수 a가 참조하는 클래스 인스턴스 안의 필드는 멤버 접근 연산자 (.)를 사용하는 a.x, a.y, a.z로 접근 2. 클래스에서 배열 구현하기 - 신체검사.. 2-1 배열 자료구조 - 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계 1. 배열 다루기 1) 배열(Array) - 같은 자료형의 변수인 구성 요소(component)가 모인 것 ex) 구성 요소의 자료형이 int형이고 구성 요소가 5개인 배열 int[] a; //구성 요소의 자료형이 int형인 배열 a = new int[5]; //new를 사용하여 배열 본체를 생성한 뒤 배열 변수 a와 연결 - 배열 본체를 생성하고, 본체에 대한 참조를 생성 - 배열 본체를 생성하는 new 식을 배열 변수의 초기자(initializer)로 사용 int[] a = new int[5]; 2) 인덱스 식과 구성 요소 - 배열 본체 안의 구성요소에 접근(access)하려면 정수형 인덱스를 연산자 [ ]안에 넣은 인덱스 식을.. 1-2. 반복 1. 1부터 n까지 정수의 합 구하기 - while문으로 n까지의 정수의 합 구하기 //while문으로 1,2,...,n의 합을 구함 import java.util.Scanner; public class SumWhile { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("1부터 n까지의 합을 구합니다."); System.out.print("n값: "); int n = sc.nextInt(); int sum =0; int i=1; while(i 1-1 알고리즘이란? 알고리즘 - 어떤 문제를 해결하기 위한 절차로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합 1. 세 값의 최댓값 구하기 - 3개의 정숫값 가운데 '최댓값'을 구하는 프로그램 import java.util.Scanner; public class Max3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("세 정수의 최댓값을 구합니다."); System.out.print("a의 값: "); int a = sc.nextInt(); System.out.print("b의 값: "); int b = sc.nextInt(); System.out.print("c의 값: ".. 이전 1 다음
