정렬과 이진 탐색 이해하기

정렬과 이진 탐색 이해하기

코딩 테스트 준비 과정에서 중요한 알고리즘중 두 가지, 정렬과 이진탐색에 대해 간단하게 정리해보려고 작성한 글입니다.

정렬 (Java Collection) : 데이터를 체계적으로 배치하기

정렬은 데이터를 일정한 순서대로 나열하는 처리 방법입니다.
Java에서는 Collections와 Arrays 클래스를 통해 컬렉션과 배열의 데이터를 손쉽게 정렬할 수 있습니다.

Java의 정렬 알고리즘 : Tim Sort를 사용한(생략가능)

• Java의 정렬 메소드들은 내부적으로 Tim Sort 알고리즘을 사용합니다.
  
• Tim Sort는 병합 정렬과 삽입 정렬의 장점을 결합한 안정적인 정렬 알고리즘으로, 최악의 경우에도 O(n log n)의 시간 복잡도를 보장합니다.
• 큰 데이터 세트에 대한 효율성과 작은 데이터 세트에 대한 민첩함을 동시에 제공하기 때문에, 다양한 크기의 데이터를 처리하는 데 유용합니다.

Tim Sort 알아볼때 봤었던 글들(생략가능)

• Tim sort에 대해 알아보자
• Java - Tim Sort
• Tim sort_Wiki

정렬 설명

Array와 Collection의 경우에 대한 예제 코드는 다음과 같습니다:

• Array의 경우 예제코드

  Integer[] array = {9, 5, 3, 7, 2};
  Arrays.sort(array);
  System.out.println(Arrays.toString(array)); // [2, 3, 5, 7, 9]
  

• Collection의 경우 예제코드

List<Integer> list = new ArrayList<>(Arrays.asList(9, 5, 3, 7, 2));
Collections.sort(list);
System.out.println(list); // [2, 3, 5, 7, 9]

정렬 알고리즘에서 Stream 활용 방법

Java 8 이상부터 Stream API를 사용해 간결하게 사용가능합니다.
Stream API는 데이터를 효율적으로 처리할 수 있는 기능을 제공하며, sorted() 메소드를 사용하면 데이터를 쉽게 정렬할 수 있습니다.
sorted() 메소드는 Tim Sort 알고리즘을 사용합니다.

List<Integer> sortedList = list.stream().sorted().collect(Collectors.toList());
System.out.println(sortedList); // [2, 3, 5, 7, 9]

Stream 학습

이진 탐색(Binary Search)

• 이진 탐색은 정렬된 배열에서 특정한 값을 찾아내는 효율적인 방법입니다.
• 이진 탐색은 시작할 때 중간값을 선택하고, 찾고자 하는 값이 중간값보다 큰지 작은지를 판단하여 탐색 범위를 줄여나갑니다.
• 이진탐색은 데이터가 정렬되어있어야지 사용가능합니다.

시간복잡도

• O(log n). 탐색할 때마다 범위를 절반으로 나누어서 빠른 탐색속도 보장합니다.

구현 코드

이진 탐색을 구현한 코드는 다음과 같습니다:

public int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while(low <= high) {
        int mid = low + (high - low) / 2; // 중간값 계산
        if(arr[mid] == target) {
            return mid; // 타겟을 찾은 경우
        } else if(arr[mid] < target) {
            low = mid + 1; // 타겟이 중간값보다 큰 경우
        } else {
            high = mid - 1; // 타겟이 중간값보다 작은 경우
        }
    }

    return -1; // 타겟을 찾지 못한 경우
}

코딩 테스트에서의 활용

이진 탐색은 주어진 문제의 데이터가 정렬되어 있어야 사용 가능하며, 특정 값을 찾거나, 가장 가까운 값을 찾아야 할 때 유용합니다.
예를 들어, 정렬된 배열에서 특정 값의 위치를 찾는 문제나, 정렬된 배열에서 특정 값보다 큰 가장 작은 값을 찾는 문제 등에서 이진 탐색을 활용할 수 있습니다.

Upper Bound 와 Lower Bound

Upper Bound, Lower Bound 는 이진탐색의 확장 개념이며, 경곗값을 찾는 알고리즘이다.
이진탐색의 확장 개념이어서 해당 알고리즘도 데이터가 정렬되어야만 한다.

Lower Bound

• Lower Bound는 찾으려는 키 값이 “없으면” 키 값보다 큰 가장 작은 정수 값을 찾습니다.
• 중복된 값이 있어도 상관없으며, 항상 유일한 해를 구할 수 있습니다.
• Lower Bound는 원하는 값이 처음 나오는 위치를 찾는 과정이다.

Upper Bound

• Upper Bound는 찾으려는 키 값보다 큰 첫 번째 위치를 찾습니다.
• Upper Bound는 원하는 값이 나오는 마지막 위치를 찾는 과정입니다.

구현 코드

// Lower Bound
public int lowerBound(int[] arr, int target) {
    int low = 0;
    int high = arr.length;

    while(low < high) {
        int mid = low + (high - low) / 2;
        if(arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    return low;
}

// Upper Bound
public int upperBound(int[] arr, int target) {
    int low = 0;
    int high = arr.length;

    while(low < high) {
        int mid = low + (high - low) / 2;
        if(arr[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    return low;
}

코딩 테스트에서의 활용

Upper Bound와 Lower Bound는 주어진 문제의 데이터가 정렬되어 있어야 사용 가능하며, 특정 값을 찾거나, 그 값의 경곗값을 찾아야 할 때 유용합니다.
예를 들어, 정렬된 배열에서 특정 값보다 큰 가장 작은 값을 찾는 문제나, 특정 값이 처음 또는 마지막으로 나타나는 위치를 찾는 문제 등에서 Upper Bound와 Lower Bound를 활용할 수 있습니다.

Reference

백준 알고리즘-이진탐색 lower_bound,upper_bound