アルゴリズム#アルゴリズム#

n/a.ターゲット

概要

ナビゲーションアルゴリズム

정렬된 리스트에 대해서 특정 요소를 탐색하는 알고리즘

중간값과 탐색하려는 요소를 비교하고,
일치하지 않으면 중간값을 기준으로 리스트를 분할하고,
대소 비교를 통해 탐색하려는 요소가 포함되어 있지 않는 리스트를 버리고
탐색하려는 요소가 포함되어 있는 리스텡 대해서 위 과정을 반복하여 요소를 찾는 알고리즘.

* 평균 시간 복잡도 - O(logn)
* 중간 값이 탐색 요소인 경우 - O(1)

public class Solution {

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

        int index = binarySearch(nums,11);
        System.out.println(index);
    }

    public static int binarySearch(int[] nums, int element) {

        int low = 0;
        int high = nums.length;

        while(low < high) {
            int mid = (low + high) / 2;

            if(nums[mid] == element) {
                return mid;
            }

            if(nums[mid] < element) {
                low = mid + 1;
                continue;
            }

            if(nums[mid] > element) {
                high = mid - 1;
                continue;
            }
        }

        return -1;
    }
}

ソートアルゴリズム-O(n^2)

리스트의 앞 부분부터 정렬된 상태를 만들어가는 알고리즘
리스트를 순회하면서 다음 요소의 적절한 위치를 찾아 삽입하여 정렬된 상태를 유지하기 때문에,
적절한 위치에 넣기 위해 이미 정렬된 요소들을 한칸씩 뒤로 미루는 작업이 필요하다.
전체 요소에 대한 순회 * 정렬된 요소를 한칸씩 미루는 작업으로 O(n^2) 복잡도를 가진다.
이미 정렬이 된 상태라면 그만큼 뒤로 미루는 작업을 하지 않기 때문에 O(n) 복잡도를 가진다.

* 제자리 정렬 알고리즘 - 입력 배열 이외에 추가 메모리를 요구하지 않는다.
* 평균, 최악의 경우 복잡도 - O(n^2)
* 최선의 경우 O(n)

리스트의 앞 부분부터 순회하면서 회차마다 최소값을 찾아 앞 부분부터 정렬된 상태를 만들어가는 알고리즘
전체 회차 * 최소값을 찾기 위한 요소 탐색으로 인해 O(n^2) 복잡도를 가진다.
삽입정렬과 다르게 이미 정렬이 되어있더라도 전체 회차, 최소값 탐색을 위한 순회여 영향이 없기 때문에 최선의 경우에도 O(n^2) 복잡도를 가진다.

* 제자리 정렬 알고리즘 - 입력 배열 이외에 추가 메모리를 요구하지 않는다.
* 모든 경우의 O(n^2) 복잡도

리스트의 인접한 요소끼리 비교하여 뒷 부분부터 정렬된 상태를 만들어가는 알고리즘
리스트의 인접한 요소를 계속 비교하고,
정렬을 위한 교체가 필요하다면 교체하여 가장 마지막 요소를 최대값을 가지도록 교체한다.
위 과정을 가장 마지막 요소를 제외하고 수행하여 뒤에서 두번째 요소를 리스트에서 두번째 큰 값을 배치한다.
이 과정을 반복하여 정렬을 완료한다.

* 제자리 정렬 알고리즘 - 입력 배열 이외에 추가 메모리를 요구하지 않는다.
* 모든 경우의 O(n^2) 복잡도

버블 정렬은 구현 방식에 따라 최선의 경우에 O(n)로 구현할 수 있다.
매회차마다 인접한 요소끼리 교체가 되었는지 확인을 하고,
교체가 이루어지지 않았다면 남은 요소에 대해서는 정렬된 상태이므로
작업을 완료한다.

ソートアルゴリズム-O(nlogn)

퀵 정렬, 합병 정렬, 힙 정렬이 있습니다.

병합 정렬은 전체 경우에서 O(nlogn)의 시간 복잡도를 가지지만
퀵 정렬은 최악의 경우 O(n^2)의 시간 복잡도를 가지므로
병합 정렬이 시간복잡도에 있어서는 효율적입니다.

하지만 대규모 데이터셋일 경우에는 공간 복잡도도 고려해야 합니다.
전체 데이터셋을 메모리에 모두 담을 수 없다면 실행시간이 늘어나거나 실행조차 할 수 없는 경우가 생깁니다.
또한 메모리를 적게 사용할 수록 CPU 캐시를 더 잘 활용할 수 있습니다.

힙 정렬의 경우 힙을 사용하여 새로운 객체를 생성하므로 O(n) 공간 복잡도를 가집니다.
배열 그 자체로 힙으로 만들 수 있기 때문에 O(1) 공간 복잡도로도 구현할 수 있습니다.

일단 힙은 모든 요소를 정렬된 상태로 유지하는 완전 정렬 형태가 아니고,
완전 이진 트리이기 때문에 일차원 배열로 선언하고 index만으로 부모 자식 관계를 찾을 수 있으므로 성능이 좋습니다.

최대 원소를 찾는데 복잡도 O(1)
원소 삽입 삭제 모두 O(logn)
최초 힙 구성을 하는데 O(n)으로 모든 연산이 가능합니다.

하지만 초기 원소 배치 상태에 따라 더 짧은 시간내에 정렬이 끝나는 특성을 가지지 못하고
힙 구조에 대한 재조정을 하는 연산이 배열을 전체적으로 참조하며 지나가기 때문에 참조 지역성의 장점을 활용하기 어렵습니다.

퀵 정렬은 최악의 경우 O(n^2)을 가지지만
최악의 경우가 발생하는 경우는 pivot을 제일 작은수 제일 큰수로 잡는 경우입니다.
pivot을 적당한 값으로 잡아주면 최악의 경우는 생기지 않기 때문에 O(nlogn)에 가까운 시간 복잡도를 유지할 수 있고
공간 복잡도 다른 객체를 사용하지 않기 때문에 상수 복잡도를 가집니다.
따라서 CPU 캐시를 다른 알고리즘에 비해서 더 잘 활용할 수 있습니다.

이런 예외정인 상황을 고려하여 더 보편적인 퀵 정렬을 사용한다고 생각합니다.

クイックソート

분할 정복 알고리즘 중 하나로 합병 정렬과 다르게 불균등하게 분리한다.
리스트 안에 있는 한 요소를 선택한다. 이것을 피벗이라고 한다.
피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮긴다.

피벗을 제외한 왼쪽 리스트와 오른쪽 리스트에서 위 로직을 반복한다.
왼쪽/오른쪽 리스트의 크기가 0이나 1이 될때까지 반복한다.

* 제자리 정렬 알고리즘 - 입력 배열 이외에 추가 메모리가 필요하지 않다.
* 분할 정복 알고리즘 - 불균등 분배
* 복잡도
퀵 정렬 알고리즘은 평균 시간 복잡도가 O(nlogn)이다.
하지만 최악의 경우 O(n^2)이 될 수도 있다.

퀵 정렬 피벗으로 매번 균등하게 분배가 된다면 logn만큼 분할이 이루어지지만,
불균등하게 분배가 되면 최악의 경우 n번 만큼 분할이 이루어진다.
매번 분할마다 n번만큼이 비교가 필요하므로 최악의 경우에는 O(n^2)의 복잡도를 가진다.

1. 피벗으로 인한 불균등 문제를 개선하기 위해 난수 분할을 사용하거나
3. 중간값을 사용하여 재귀의 깊이를 줄이는 방식으로 퀵 소트를 개선하는 방법이 있다.
2. 크기가 작은 구간에 대해서 삽입 정렬을 사용하거나 두 개의 피봇을 사용해서 불균등하게 분리되는 확률을 줄이는 알고리즘으로 개선

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

        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        int low = left;
        int high = right;
        int pivot = arr[left];

        while (low < high) {
            while (arr[high] > pivot && low < high) {
                high--;
            }

            while (arr[low] <= pivot && low < high) {
                low++;
            }

            swap(arr, low, high);
        }

        swap(arr, left, low);

        return low;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

連結ソート

주어진 리스트를 절반으로 분할하여 부분 리스트로 나눈다.
분할 된 부분리스트 길이가 1이 될때까지 과정을 되풀이한다.
인접한 부분리스트끼리 정렬하여 합친다.

* 제자리 정렬 알고리즘 X - 입력 배열 이외에 추가 메모리가 필요하다.
* 분할 정복 알고리즘 - 균등 분배
* 모든 경우, O(nlogn) 복잡도를 보장한다.

お尻の位置合わせ

힙 자료구조를 기반으로 하는 정렬

힙은 최소값 또는 최대값을 빠르게 찾아내기 위한 완전이진트리 형태의 자료구조이다.
힙은 부모 노드는 항상 자식 노드보다 우선순위가 높다라는 규칙을 가지고 완전이진트리형태로 채우는 방식이다.

최대값 또는 최소값을 빨리 찾아낼 수 있으므로 전체 요소를 힙으로 구성하고
힙에서 최소값이나 최대값을 계속 뽑아내는 방식으로 정렬을 할 수 있다.

초기 배열을 최대 힙을 만족하도록 구성하고
최대 값을 배열의 제일 뒤로 보내고 나머지 배열을 최대 힙을 구성하는 걸 반복하면서
정렬을 구성한다.

* 제자리 정렬 알고리즘 - 입력 배열 이외에 추가 메모리가 필요 없다.
* 분할 정복 알고리즘 - 불균등 분배

2개로 크기가 고정된 최소 힙 자료구조를 사용한다.
전체 리스트에 대해서,
힙이 비어있는 경우 힙에 추가한다.
힙이 비어있지 않은 경우,
현제 데이터와 힙의 최소값과 비교한다.
힙의 최소값보다 현재 데이터가 크면 최소힙을 제거하고 힙에 새로운 데이터를 추가한다.

힙의 크기는 2로 고정되어 있기때문에 힙 삽입으로 발생하는 복잡도는 log2로 고정된다.

전체 n개에 대해서 이 작업을 반복하면

전체 복잡도는 O(n * log2)로 O(n)으로 두번째로 큰 수를 찾을 수 있다.


중복을 제거한다면
HashMap을 사용하여 중복을 제거하고 위에 작업을 수행한다.

Hashmap을 사용하여 중복을 제거하면 hash를 위한 복잡도 * O(1)로 중복 제거가 가능하다.

Hashmap의 삽입 후 전체 키에 대해서 위 작업을 하게되면 전체 복잡도는 O(N)으로 모든 작업이 가능하다.