알고리즘/이론4 [JAVA]검색(2) - 이진 검색(Binary Search) 1. 이진 검색(Binary Search)이란? ㆍ정렬되어 있는 데이터에서 원하는 값을 찾는 방법 ㆍ대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾음 ㆍ자료는 정렬된 상태여야 함 2. 검색 과정 ㆍ자료 중앙에 있는 원소를 고름 ㆍ중앙 원소의 값과 찾고자 하는 값을 비교 ㆍ찾고자 하는 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 데이터에 대해서 새로 검색하고, 크다면 자료의 오른쪽 데이터에 대해 새로 검색을 수행 ㆍ 찾고자 하는 값을 찾을 때 까지 반복 3. 이진 검색의 특징 ㆍ검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행 ㆍ자료에 삽입이나 삭제가 발생하게 되는 경우, 항상 정렬 상태로 유지하는 추가 작업이 필요 4. 시간복잡도 ㆍO(log n) 5. 코드 예.. 2023. 1. 12. [JAVA] 검색(1) - 순차 검색(선형 검색, Sequential Search) 0. 검색(Search)이란? ㆍ여러 개의 데이터 안에서 원하는 데이터를 찾아내는 알고리즘 ㆍ탐색키(search key, 자료를 구별하여 인식할 수 있는 키)를 가진 항목을 찾는 것 ㆍ검색 종류 : 순차 검색(선형 검색, Sequential Search), 이진 검색(Binary Search) 1. 순차 검색(선형 검색, Sequential Search) ㆍ일렬(배열)로 되어 있는 자료를 순서대로 검색하는 방법 - 가장 간단하고 직관적인 방법 - 순차구조로 된 자료구조에서 원하는 항목을 찾을 때 유용 - 단순하여 구현은 쉽지만, 검색 대상의 수가 많은 경우 수행시간이 증가하여 비효율적인 부분이 있음 2. 검색 과정 1) 정렬되어 있지 않은 경우 검색 과정 ㆍ첫 번째 원소부터 순서대로 검색 대상과 키 값이.. 2023. 1. 11. [JAVA]정렬(2) - 선택 정렬(Selection Sort) 1. 선택 정렬(Selection Sort)이란? ㆍ대상 데이터에서 최대나 최소 데이터를 나열된 순으로 찾아가며 선택하는 방법 2. 정렬 과정 ㆍ최소값을 찾는다. ㆍ가장 앞에 있는 데이터와 선택된 데이터를 swap ㆍ남은 부분이 없을 때까지 반복 3. 시간복잡도 ㆍO(n²) 4. 코드예제 import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { // TODO Auto-generated method stub // 5개의 원소를 가지는 배열을 생성 int[] arr = new int[5]; // arr배열에 1~6까지의 난수를 넣는다. for (int i = 0; i < arr.length; i+.. 2023. 1. 10. [JAVA] 정렬(1) - 버블 정렬(Bubble Sort) 1. 버블 정렬(Bubble Sort)이란? ㆍ두 인접한 데이터의 크기를 비교해 정렬하는 방법(오름차순, 내림차순) ㆍ인접한 데이터 간의 swap 연산으로 정렬 ㆍ교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라 함 2. 정렬 과정 ㆍ인접한 데이터 값을 비교 ㆍ조건에 부합하면 swap 연산을 수행 ㆍ범위가 끝날 때까지 반복 3. 시간복잡도 ㆍ O(n²) 4. 코드 예제 import java.util.Arrays; public class BubbleSort { public static void main(String[] args) { // TODO Auto-generated method stub // 배열을 선언하고 원소를 5개로 초기화 int[] arr = { 42,.. 2023. 1. 10. 이전 1 다음
