"탐색 (Search)" 알고리즘에 대해 알아보자.

"탐색 (Search)" 알고리즘에 대해 알아보자.

탐색 알고리즘은 "저장된 데이터들 중 원하는 데이터를 찾는 알고리즘" 이다.

다양한 탐색 방식의 알고리즘이 존재한다.

각각의 탐색 방식과 시간복잡도 등 다양한 형태에 따라 적절한 탐색 알고리즘을 적용한다.

---

탐색 알고리즘

 

1. 선형탐색 (Linear Search)

: 한쪽 끝에서 하나하나 순서대로 탐색하여 원하는 값을 찾는 알고리즘.

(- 정렬되지 않은 배열도 가능)

 

선형 탐색은 순차 탐색 이라고도 불린다.

장점은 탐색 알고리즘의 가장 간단하고 직접적인 방법으로, 구현하기 쉽다.

그러나, 배열의 크기에 직접적인 영향을 받는다. (일반적으로 배열이 클수록 시간이 많이 든다.)

 

* 시간복잡도

Best Case : 배열의 첫 부분(탐색하는 첫 데이터)이 key값 인 경우 : 1

Worst Case : 마지막 요소에 원하는 데이터가 존재한다면, 마지막 요소까지 순서대로 탐색해야 함으로, 

"O(N)" 의 시간 복잡도를 갖는다.

 

[JAVA 코드]

	public static int[] arr; // 배열
	static int key; // 찾고자 하는 데이터

	public static int LinearSearch(int[] arr, int key){
		int Idx = -1;
		
		for(int i=0; i<arr.length; i++){
			if (key == arr[i]){
				Idx = i;
				break;
			}
		}

		return Idx;
	}

 

[프로그램 실행]

public class Main {
    public static void main(String[] args) throws IOException{
		
		arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

		System.out.print(LinearSearch(arr, 6));

	}

	public static int[] arr; // 배열
	static int key; // 찾고자 하는 데이터

	public static int LinearSearch(int[] arr, int key){
		int Idx = -1;
		
		for(int i=0; i<arr.length; i++){
			if (key == arr[i]){
				Idx = i;
				break;
			}
		}

		return Idx;
	}
}


/*출력값
5
*/

---

 

2. 이진탐색 (Binary Search)

: 중간 지점을 기준으로 데이터를 반으로 나눠 탐색하는 방식.

(- 정렬된 배열에서 사용)

 

1. 배열 중 중간 지점에 있는 값을 기준으로 key 값이 좌 / 우 에 있는지 판단하여 key값이 있는 부분을 남긴다.

2.  key 값이 있는 부분에서 다시 중간 지점을 선택한 후, 다시 key 값이 존재하는 부분을 남긴다.

3. key값을 발견할 때 까지 반복한다.

 

* 시간복잡도

Best Case : 중간 지점의 데이터가 key 값인 경우 : 1

Worst Case : 배열에 key 값이 존재하지 않는 경우 : log2(n) - 1

 

배열의 크기 : n  , 탐색 횟수 : k

n/2 <= 2^k 가 되는 시점이 Worst Case이다.

log2(n) - 1 <= k 이므로, 

시간 복잡도는 O(logN) 이다.

 

[JAVA 코드]

	public static int[] arr; // 배열
	static int key; // 찾고자 하는 데이터

	public static int BinarySearch(int[] arr, int key){
		int Idx = -1;
		int left = 0, right = arr.length-1, mid;
		while(left <= right) {
			mid = (left + right) / 2;

			// key가 오른쪽 부분에 존재
			if (arr[mid] <= key){
				Idx = mid;
				left = mid + 1;
			}
			// key가 왼쪽 부분에 존재
			else {
				right = mid - 1;
			}
		}

		return Idx;
		
	}

---

3. 해시탐색 (Hash Search)

: 해시 함수를 사용하여 데이터를 보관한 후, 해시 함수를 사용하여 데이터를 한 번에 탐색하는 방식.

선형 / 이진 탐색은 배열 내 데이터에 대한 정보가 없이 탐색을 하는 방식인 반면, 해시 탐색은 데이터와 index에 대한 사전 정보가 존재하는 상태에서 탐색을 한다.

 

[ HashMap 의 다양한 함수 활용 - JAVA ]

.put / .get / .getOrDefault

import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // key : value 순으로 입력
        HashMap<Integer, String> hash = new HashMap<>();
        
        // HashMap에 값 삽입 : put
        hash.put(1, "첫번째 value");
        hash.put(2, "두번째 value");
        hash.put(3, "세번째 value");
        hash.put(4, "네번째 value");

        // HashMap에서 key를 이용하여 value 추출
        bw.write(hash.get(3) + "\n");

        // 존재하지 않는 key로 호출 => error!
        bw.write(hash.get(7) + "\n");

        // getOrDefault : 존재하지 않는 key로 호출 => 특정값 반환
        bw.write(hash.getOrDefault(7, "false") + "\n" );

        bw.flush();
        bw.close();
        br.close();
    }
}

/*
세번째 value
null
false
*/

 

HashMap 값 수정

import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // key : value 순으로 입력
        HashMap<Integer, String> hash = new HashMap<>();
        
        // HashMap에 값 삽입 : put
        hash.put(1, "첫번째 value");
        hash.put(2, "두번째 value");
        hash.put(3, "세번째 value");
        hash.put(4, "네번째 value");

        // HashMap에서 key를 이용하여 value 추출
        bw.write(hash.get(3) + "\n");

        // HashMap 데이터 수정
        hash.put(3, "수정된 세번째 value");
        bw.write(hash.get(3) + "\n");


        bw.flush();
        bw.close();
        br.close();
    }
}

/*
세번째 value
수정된 세번째 value
*/

---

4. 이진탐색트리 (Binary Search Tree)

: 트리 자료구조를 사용하여 탐색하는 방식.