2022-10-24 Arrays클래스, Stack / Queue, 검색 알고리즘 - 선형검색, 이진검색, 정렬 알고리즘 - 단순 선택 정렬

Arrays클래스

 

---

: 배열을 다루기 위해 만들어진 클래스

- 배열을 다루기 위한 다양한 메소드 포함
- 많은 메소드가 static메소드이다.

- import java.util.Arrays;

 

 

- Arrays.sort 이용하여 배열 정렬하기

import java.util.Arrays;

public class ArraysTest {
	public static void main(String[] args) {
		int[] myarr = {19, 30, 89, 36, 82};
		display(myarr); // 정렬 하지 않고 그대로 출력됨
		
		// 배열의 모든 데이터를 오름차순으로 정렬, 매개변수로 정렬할 배열을 전달받음
		Arrays.sort(myarr);
		display(myarr);  // 정렬한 결과 출력됨

 

- Arrays.copyOfRange(복사할 배열, 시작int, 끝int) 이용하여 배열 복사하기

public class ArraysTest {

	public static void main(String[] args) {
    
		int[] otherArr = Arrays.copyOfRange(myarr, 2, 4);  //end-1
		display(otherArr);
		// 전달받은 배열에서 특정 값의 위치값를 반환
		// => 내부적으로 이진 검색 알고리즘을 사용하여 검색
		//    이진 검색 알고리즘을 사용하기 때문에 사용 전에 정렬이 되어 있어야 제대로 동작한다.
		System.out.println(Arrays.binarySearch(myarr, 89));  // 89의 위치 찾기
	}

* 끝int는 항상 -1해주기

 

 

 

 

 

 

Stack

 

---

스택의 기능

public class StackAPITest {
	public static void main(String[] args) {
		Stack<String> stack = new Stack<String>();
		// 스택에 데이터 저장
		stack.push("java");
		stack.push("js");
		stack.push("jsp");
		System.out.println("스택에 저장된 요소의 갯수 : "+stack.size());
		System.out.println("스택에 요소가 없나? "+stack.empty()); // 스택에 저장된 요소가 없을 때 true
		System.out.println("스택에 마지막에 저장된 요소 확인하기 "+stack.peek());
		System.out.println("스택에 저장된 요소의 갯수 : "+stack.size());
		System.out.println("스택에서 데이터 꺼내기 : "+stack.pop());
		System.out.println("스택에서 데이터 꺼내기 : "+stack.pop());
		System.out.println("스택에서 데이터 꺼내기 : "+stack.pop());
		System.out.println("스택에 저장된 요소의 갯수 : "+stack.size());
		System.out.println("스택에 요소가 없나? "+stack.empty());
		
		System.out.println("스택에 마지막에 저장된 요소 확인하기 "+stack.peek());
		// ㄴ> 스택이 비어있는데 peek하면 EmptyStackException발생함
		System.out.println("스택에서 데이터 꺼내기 : "+stack.pop());
		// ㄴ> 스택이 비어있는데 pop하면 EmptyStackException발생함
	}

}

 

 

 

 

 

 

Queue

---

큐의 기능

import java.util.LinkedList;

public class QueueTest {

	public static void main(String[] args) {
		
		Queue<Integer> queue = new LinkedList<Integer>();  // offer-저장, poll-추출
		queue.add(1); // 저장공간이 있으면 true 없으면 Exception을 발생시킴
		queue.offer(2); // 삽입성공 - true리턴, 실패 - flase리턴
		queue.offer(3);
		queue.offer(4);
		System.out.println(queue.peek());
		System.out.println(queue.isEmpty());
		System.out.println(queue.size());
		System.out.println(queue.poll()); // 
		System.out.println(queue.remove()); // 
		System.out.println(queue.poll()); //
		System.out.println(queue.remove()); //
		//System.out.println(queue.poll()); // front의 요소를 조회하고 제거(비어있으면 null)
		//System.out.println(queue.remove()); // front의 요소를 조회하고 제거(비어있으면 Exception을 발생시킴)
	}

}

 

 

 

 

 

 

검색 알고리즘

 

- 선행 검색(순차 검색)

import java.util.Scanner;
public class SequenceSearchTest {

	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int[] arr = {77, 88, 99, 34, 23};
		int searchValue = key.nextInt();
		int result = search(arr, searchValue);
		if(result == -1) {
			System.out.println("찾는 데이터가 없습니다.");
		}else {
			System.out.println("데이터의 위치 : "+result);
		}

	}
	// 요소의 위치를 리턴, 없으면 -1리턴
	public static int search(int[] arr, int searchValue) {
		int result = 0;
		for (int i = 0; i < arr.length; i++) {
			if(arr[i]==searchValue) {
				result = i; // 찾으면 인덱스를 리턴
				break;
			}
			result = -1;
		}
		return result;
	}
    
}

 

 

- 이진검색

import java.util.Arrays;
import java.util.Scanner;

public class BinarySearchTest {
	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int[] arr = {77, 88, 99, 34, 23, 6, 1};
		int searchValue = key.nextInt();
		Arrays.sort(arr);
		display(arr);
		int result = search(arr, searchValue);  // return한 searchIndex의 값을 변수 result를 만들어서 받아줌
		if(result == -1) {
			System.out.println("찾는 데이터가 없습니다.");
		}else {
			System.out.println("데이터의 위치 : "+result);
		}
	}
    
	// 요소의 위치를 리턴, 없으면 -1리턴
	public static int search(int[] arr, int searchValue) {
		int searchIndex = -1;
		//시작인덱스, 중간인덱스, 끝인덱스가 존재해야 함
		int startIndex = 0;
		int endIndex = arr.length-1;
		int mediumIndex = 0;
		while(startIndex<=endIndex) {
			mediumIndex = (startIndex+endIndex)/2;
			System.out.println(startIndex+","+mediumIndex+","+endIndex);
			if(arr[mediumIndex]==searchValue) {
				System.out.println("같다.");
				searchIndex = mediumIndex; // 원하는 값을 찾음!
				break;
			}else if(arr[mediumIndex]>searchValue) {
				System.out.println("크다.");
				// 중간 인덱스 앞의(왼쪽) 인덱스를 엔드인덱스를 이동
				endIndex = mediumIndex-1;
			}else {
				// 찾는 값보다 중간값이 작으면 앞의 요소는 검색하지 않아도 되므로 시작인덱스를 중간인덱스의 다음(오른쪽)인덱스로 이동
				System.out.println("작다.");
				startIndex = mediumIndex+1;
			}
		}
		return searchIndex;
	}
	
	public static void display(int[] myarr) {
		for (int i = 0; i < myarr.length; i++) {
			System.out.print(myarr[i]+"\t");
		}
		System.out.println();
	}
}

* 인덱스의 위치값을 비교하기 때문에 조건 설정할 때 잘 생각하고 코드짜기!!!

 

 

 

 

 

 

 

정렬 알고리즘

---

- 단순 선택 정렬

import java.util.Scanner;

public class SelectionSortTest {

	public static void main(String[] args) {
		Scanner key = new Scanner(System.in);
		int[] arr = {77, 88, 99, 34, 23, 6, 1};
		for (int i=0; i<arr.length; i++) {
			// 순서대로 앞에서부터 작은 값을 위치할 것이므로 i값을 min index로 정의하고 작업\
			int minIndex = i; //최초작업은 minIndex=0
			for(int j=i+1; j<arr.length; j++) {
				if(arr[minIndex]>arr[j]) { //기준값을 제외한 나머지 값들과 반복해서 비교
					minIndex = j;
				}
			}// 최종작업이 완료되면 minIndex는 제일 작은 값이 있는 인덱스가 저장됨
			 // swap하기
			int temp = arr[i]; // i번(기준값)요소의 값을 임시변수에 저장
			arr[i] = arr[minIndex]; // 최소값을 앞으로 이동
			arr[minIndex] = temp;
			display(arr);
		}
		System.out.println("============================================================");
		display(arr); // 디스플레이 메소드로 결과 출력해보기
	}

	public static void display(int[] myarr) {
		for (int i = 0; i < myarr.length; i++) {
			System.out.print(myarr[i]+"\t");
		}
		System.out.println();
	}
}