TIL_20220903

오늘 할 일

• 1일 1커밋(알고리즘 문제 풀기)

오늘 배운 것

🌓 이진 탐색 | Binary Search

오름차순으로 정렬된 리스트에서 특정 값을 찾는 탐색 알고리즘이다. 처음 중간의 값을 임의의 값으로 으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

이진 탐색 쉽게 이해해보기

업-다운 게임

• 사실 이진 탐색은 우리의 생활과 밀접한 관련이 있었다.
• 소주 뚜껑 안에 적힌 숫자를 맞추는 업-다운 게임을 생각해보자.
• 뚜껑 안에 올 수 있는 숫자는 0~100 사이라고 가정하고, 숫자를 맞추기 위해 우리는 50을 부른다. 우리는 50을 부르면 두 개의 큰 덩어리로 나눌 수 있기 때문에 경우의 수를 크게 줄일 수 있음을 본능적으로 알고 있다.
• 맞다. 이것이 이진 탐색이다. 50을 부르고 업 혹은 다운을 들으면 0~49 또는 51 ~ 100의 중간 번호를 외칠 것이다.
• 이제 코드를 보면 이해할 수 있을 것이다. 😎

 

public int binarySearch(int[] arr, int target) {
    int start = 0; // 시작 인덱스는 0
    int end = arr.length - 1; // 끝 인덱스는 배열의 길이 - 1
    int mid = 0;

    while (start <= end) { // 시작 인덱스가 끝 인덱스보다 커지면 while문을 종료한다.
        mid = (start + end) / 2; // 시작 인덱스와 끝 인덱스를 더하고 2로 나누면 중간 인덱스가 선택된다.
        if (target == arr[mid]) { // 목표값이 배열의 중간 인덱스와 일치하면 중간 인덱스 리턴
            return mid;
        } else if (arr[mid] < target) { // 목표값이 배열의 중간 인덱스보다 크면 시작 인덱스 1 증가
            start = mid + 1;
        } else if (target < arr[mid]) { // 목표값이 배열의 중간 인덱스보다 작으면 끝 인덱스 1 감소
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("can't find target."); // 예외처리
}

• 위의 코드에서 우리가 외쳤던 50은 mid, 업인지 다운인지 확인하는 것은 arr[mid]와 target 중 누가 더 큰지 확인하는 것과 같다.
• 이 방법을 목표값을 찾을 때까지 반복한다.

알아두어야 할 것!

1. 이진 탐색을 사용하기 위해서는 정렬이 되어있어야 한다. 보통 오름차순 정렬을 사용한다.

2. 살펴보는 범위를 절반씩 줄여가면서 사용한다.

3. 이진 탐색만 수행하는 경우의 시간 복잡도는 O(logN)으로 상당히 빠른 편에 속한다. 하지만 정렬을 수행하는 경우의 시간 복잡도가 O(N)이므로 정렬과 이진 탐색을 같이 수행했을 경우의 시간 복잡도는 O(NlogN)이다.

느낀점

• 이진 탐색을 활용해서 문제를 풀어본 기억이 거의 없었는데, 이번에 문제를 풀면서 제대로 정리했습니다. 개념이 이해되니 코드 자체가 눈에 쏙쏙 잘 들어와서 신기했습니다.
• 사실 오늘은 복습을 하고 싶었는데, 내일로 미루었습니다. 그 이유는 결혼식에 다녀오면서 친구들과 티-타임(이라 쓰고 하이볼이라 읽는다.)을 가졌기 때문이죠. 하하. 그래도 돌아와서 이렇게 블로그를 쓰고 있습니다. ^~^
• 미리 핑계를 좀 대자면 내일은 외삼촌의 팔순 잔치라 오후 6시부터는 콤푸타를 만지지 못합니다. 그래서 아침부터 일어나 공부를 해야합니다. ㅠㅠ

내일 할 일

• 1일 1커밋
• 복습: 자바 심화 문제 풀기, 자주 사용하는 메서드 정리하기, 이해 안갔던 부분 다시 읽어보기