Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바 편 (p.~110) [ 검색 알고리즘 ]

시박거 개빡친다.

글 다썻는데, 노트북 이 개자식 지 혼자 꺼져서 글이 다 날라갔다 진짜 열받는다 아 열받아

아니야..후....

하....열받아...하....아니야...화내지마 히히낙락..

---

검색 알고리즘 ㅣ 검색과 키

(1) 배열에서 검색

 1. 선형 검색 : 무작위로 늘어서 있는 데이터 모임에서 개빠른검색

 2. 이진 검색 : 일정한 규칙에서 ! ~

 3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 ~

    - 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결

    - 오픈 주소법 : 데이터를 위한 해시갑싱 충돌할 때 재해시하는 방법

 

1. 선형검색 : 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 순서대로 검색

[ 검색 종료 조건 ]

(1) 종료 검색할 값을 발견하지 못하고 배열이 끝

(2) 종료 검색할 값과 같은 요소를 발견

 

* 무한 루프

(1) while (true) ///do while문에서도 마찬가지임

(2) for ( ; true ; )

 

* 보초법   (cf/ 보초병세우는 것처럼, 배열 맨 마지막에 보초를 세우고 그 놈이랑 앞에있는 배열이랑 비교하는거)

package algo;
import java.util.*;

public class uyf {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.print("요솟수: ");
		int num = sc.nextInt();
		int[] x = new int[num + 1];	//요솟수가 num+1인 배열
		
		for (int i = 0; i < num; i++) {
			System.out.print("x[" + i + "]: ");
			x[i] = sc.nextInt();
		}
		
		System.out.print("검색할 값: "); //키값을 입력받음
		int ky = sc.nextInt();
		
		int idx = seqSearchSen(x, num, ky); //배열x에서 값이 ky인 요소를 검색
		
		if (idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println("그 값은 x[" + idx +"]에 있습니다.");

	}
	
	static int seqSearchSen(int[] a, int n, int key ) {
		int i = 0;
		
		a[n] = key; //보초를 추가
		
		while(true) {
			if (a[i] == key) //검색 성공 (보초에 들어가있는 값이랑 비교하는거임ㅇㅇ) 종료조건1을 고려안해도 되므로
				break;
			i++;
		}
		return i == n ? -1 : i;
	}
	



}

 

2. 이진 검색 : 요소가 오름차 혹은 내림차순으로 정렬된 배열에서 검색하는 알고리즘

[ 검색 과정 ]

(1) 중앙 요소 선택 -> 검색할 값이랑 비교

(2) 검색 값이 더 크면 그 뒤쪽을 검색 범위로 두고 중앙 요소 재 선택

-> 해당 과정을 반복하면서 최종적으로 원하는 값을 검색

package algo;
import java.util.*;

public class uyf {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.print("요솟수: ");
		int num = sc.nextInt();
		int[] x = new int[num];	
		
		System.out.print("x[0]: ");
		x[0] = sc.nextInt();
		
		for (int i = 1; i < num; i++) {
			do {
				System.out.print("x[" + i + "]: ");
				x[i] = sc.nextInt();
			} while (x[i] < x[i-1]);
			
		}
		
		System.out.print("검색할 값: "); //키값을 입력받음
		int ky = sc.nextInt();
		
		int idx = binSearch(x, num, ky); //배열x에서 값이 ky인 요소를 검색
		
		if (idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println("그 값은 x[" + idx +"]에 있습니다.");

	}
	
	static int binSearch(int[] a, int n, int key ) {
		int pl = 0;
		int pr = n - 1;
		
		do {
			int pc = (pl + pr) / 2; //중간 요소 가져오려고
			if (a[pc] == key) //검색할 값이랑 같냐?
				return pc; //검색 성공
			else if (a[pc] < key) //겁색할 값이 더 크면
				pl = pc + 1; //큰 쪽을 검색 범위로 한정할거야
			else
				pr = pc - 1; //작으면 작은 쪽을 검색 범위로 한정할거야
		} while (pl <= pr);
		
		return -1; //실패
	}
	



}

소감 : 화를 내어서 무엇하리... 글이 날라갔다 == 공부를 한 번 더할수 있다 == 똑똑해진다 == 개이득이다 == 기분이좋다

           요약하면,, 글이 날아갔다 == 기분이좋다