[알고리즘] 검색 알고리즘 기초 개념 잡아가기

 

https://www.youtube.com/shorts/uglkfaI6mBU

https://www.youtube.com/shorts/uglkfaI6mBU

최근 이 영상을 보고 정신이 번쩍 들었다.

이 영상은 확신 있는 노력과 확신 없는 노력에 대해 쇼츠로 간단하게 알려주는데,

나 자신을 되돌아보니 아직 부족한 점도 많고 부족한 부분을 채우기 위해

기초부터 개념부터 천천히 다지기로 결심했다.

 

https://www.youtube.com/watch?v=WjIlVlmmNqs&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=3 

 

알고리즘 테스트 = 코딩 테스트라 뭔가 더 어렵게 느껴지고 그랬다. 괜히 쭈글쭈글되기도 하고 ㅠㅠ

하지만, 노마드 코더 영상에 니콜라스쌤의 설명을 듣고 왜 알고리즘과 데이터 구조가 중요한지! 더 확 와닿게 되었다!

알고리즘과 데이터 구조는 서로 엮여져있는 관계로 알고리즘이 여러 가지인 경우에는 용도나 목적, 실행 속도, 자료 구조 등을 고려하여 알고리즘을 선택해야 한다!

 

차근차근 영상을 보며 기반을 다져야겠다!

알고리즘에서는 스텝이 많으면 많을수록 속도가 느려진다고 했다.

"오잉? 왜 알고리즘을 x초 걸려요! 이런 식으로 말하지 않나요?"라고 생각할 수 있다.

알고리즘에서 걸리는 속도를 시간으로 말하지 않는 이유는 

같은 알고리즘이라도 컴퓨터의 성능에 따라 더 빠르거나 느릴 수 있기 때문이다.

그렇기 때문에 알고리즘 스피드는 완료까지 걸리는 절차의 수로 결정이 된다.

 

그럼 본격적으로 영상에서 설명해주는 선형 검색과 이진 검색에 대해 정리해보겠습니다!

 

선형 검색은 첫 번째 인덱스부터 검색을 수행하는 것이고, 이진 검색은 선형 검색과 다르게 중간에서 시작한다!

하지만 이진 검색을 할 땐 전제 조건이 있는데 그것은 바로 Sorted Array(정렬된 배열)에서만 사용한다. 

(여기에서 이진은 010101이 아닌 반으로 쪼개는 것)

 

그렇기 때문에 이진 검색은 정렬하는 것에 시간을 투자해야 한다.

그럼에도 투자해야 하는 이유는 무엇인지 확인해보겠다.

 

[1], [8], [5] [2], [6], [3], [7], [4], [10], [9] 배열에서

6을 검색해보겠다.

 

선형 검색으로 할 경우 

1->8->5->2->6

첫 번째 요소, 두 번째 요소.. 순차적으로 값이 6이 될 때까지 검색할 것이다.

그렇게 선형 검색으로 할 경우 5번 스텝이 나왔다.

 

이진 검색으로 할 경우

앞서 이진 검색의 전제 조건은 이미 정렬되어야 한다는 점이다!

그럼 오름 차순으로 배열을 정렬하고 6를 검색을 해보겠습니다!

 

[1], [2], [3], [4], [5], [6], [7], [8], [9], [10]

 

이진 검색은 말 그대로 반으로 쪼개는 것이기 때문에 중간에서 시작합니다!

중앙에 위치한 5가 원하는 값인지 확인해보면 검색하려는 값인 6보다 작은 값입니다.

그러므로 [1]]~[5]은 검색 대상에서 제외되기 때문에 검색 대상을 뒤쪽의 [6]~[10]으로 좁힐 수 있습니다!

 

[6], [7], [8], [9], [10]

여기에서도 중앙에 위치한 8이 원하는 값인지 확인 해보면 검색하려는 값인 6보다 큰 값입니다

그러므로 [8], [9], [10]은 검색 대상에서 제외되기 때문에 검색 대상의 앞쪽의 [6], [7]으로 좁힐 수 있습니다.

 

[6], [7]

이렇게 값이 6이 될 때까지 검색했습니다.

이렇게 이진 검색으로 할 경우 3번의 스텝이 나왔습니다

 

자!! 그러면 만약 1만 개의 배열로 검색을 해본다고 가정해보겠습니다.

선형 검색을 한다면 최악의 경우 10,000 스텝이

이진 검색은 최악의 경우에도 14번 스텝입니다.

이처럼 알고리즘은 중요합니다!! 👍

 

 

 

왜 해야 하는지 명확하게 알고 나니 더 재밌다~! 

package search;

import java.util.Arrays;

public class searchEx {

    static int linearSearch(int[] arr, int key) {
        int i = 0;
        while (true) {
            if(i== arr.length-1) {
                return  -1;
            }
            if(arr[i] == key) {
                return i;
            }
            i++;
        }
    }

    static int binarySearch(int[] arr, int key) {
        int firstIndex = 0;
        int lastIndex = arr.length-1;

        do {
            int searchIndex = (firstIndex + lastIndex) / 2;

            if (arr[searchIndex] == key) {
                return searchIndex;
            }
            if(arr[searchIndex] < key) {
                firstIndex = searchIndex+1;
            } else {
                lastIndex = searchIndex-1;
            }
        } while (firstIndex <= lastIndex);

        return -1;
    }
    
    static int[] arraySorting(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int tmp;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        return arr;
    }

    public static void main(String[] args) {

        int[] arr = new int[]{ 1, 8, 5, 2, 6, 3, 7, 4, 10, 9};

        linearSearch(arr, 6);
        binarySearch(arraySorting(arr), 6);

    }
}