코딩테스트 - 패스트캠퍼스 챌린지 14일차

수강한 강의
Chapter 16 순차 탐색 알고리즘
- 정렬 알고리즘 몸풀기: 순차 탐색
- 정렬 알고리즘 몸풀기: 이진 탐색

학습 후기
강사님이 중간에 쉬어가는 코너라고 말씀하시며 오늘 강의를 시작하셨다. 계속 어려운 알고리즘 강의만 하기보다 중간에 쉬어 가는 것도 좋은 거 같다.

순차 탐색(Sequential Search)
탐색은 여러 데이터 중에서 원하는 데이터를 찾는 것이다. 그중 순차 탐색 방법은 데이터가 담겨 있는 배열을 처음부터 끝까지 확인해서 찾는 방법이다.

public int search(ArrayList<Integer> list, Integer target) {
    for (int i = 0; i < list.size(); i++) {
        if (target.equals(list.get(i))) {
            return i;
        }
    }
    return -1;
}

search 함수는 데이터 배열과 찾을 데이터를 파라미터로 받고 해당 배열에 찾을 데이터가 있으면 배열에서 데이터 위치를 리턴해 주고 없으면 -1을 리턴한다.
for문을 사용하여 탐색함으로 시간 복잡도는 O(n)이다.

이진 탐색(Binary Search)
이진 탐색은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 먼저 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고 하자 하는 값의 크고 작음을 비교하는 방식으로 채택하고 있다. 찾는 값이 중간값보다 크면 중간값은 새로운 최솟값이 되고, 찾는 값이 중간값보다 작으면 중간값은 새로운 최댓값이 된다. 이러한 이유로 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만 검색 속도가 빠르다는 장점이 있다.
이전 강의에서 배운 재귀 함수를 이용하여 binarySearch를 구현해보는 연습을 했고, 위키피디아에서는 재귀 함수 대신 while문을 사용하여 구현되어있었다.

public int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid = 0;
    while (start <= end) {
        mid = (start + end) / 2;
        if (target == arr[mid]) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else if (target < arr[mid]) {
            end = mid - 1;
        }
    }
    throw new NoSuchElementException("can't find target.");
}

이진 탐색의 복잡도는 탐색할 때마다 중간값을 구하고 중간값과 같지 않으면 중앙값의 왼쪽이나 오른쪽만 다시 탐색하면 되기 때문에 O(log n)이다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.