주요 알고리즘 설명

정렬 알고리즘 ==== 병합 정렬 ---- `안정적` 시간 복잡도: O(n log n) 공간 복잡도: O(n)

코드 보기

class Sorter {
    public int[] sort(int[] arr) {
        divide(arr, 0, arr.length - 1);
        return arr;
    }

    private void divide(int[] arr, int start, int end) {
        if (start >= end) return;

        int mid = (start + end) / 2;
        divide(arr, start, mid);
        divide(arr, mid + 1, end);
        combine(arr, start, mid, end);
    }

    private void combine(int[] arr, int leftStart, int leftEnd, int rightEnd) {
        int[] temp = new int[rightEnd - leftStart + 1];
        int i = leftStart, j = leftEnd + 1, k = 0;

        while (i <= leftEnd && j <= rightEnd) {
            if (arr[i] <= arr[j]) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }

        while (i <= leftEnd) temp[k++] = arr[i++];
        while (j <= rightEnd) temp[k++] = arr[j++];

        System.arraycopy(temp, 0, arr, leftStart, temp.length);
    }
}

빠른 정렬 ---- `불안정적` 평균 시간 복잡도: O(n log n), 이미 정렬되어 있거나 역순일 경우 최악의 경우 O(n^2) 공간 복잡도: O(log n)

코드 보기

class QuickSorter {
    public int[] sort(int[] arr) {
        quick(arr, 0, arr.length - 1);
        return arr;
    }

    private void quick(int[] arr, int start, int end) {
        if (start >= end) return;

        int pivotIndex = partition(arr, start, end);
        quick(arr, start, pivotIndex - 1);
        quick(arr, pivotIndex + 1, end);
    }

    private int partition(int[] arr, int start, int end) {
        int pivot = arr[start];
        int i = start;
        for (int j = start + 1; j <= end; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, start, i);
        return i;
    }

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

메모리 교체 알고리즘 ====== 최근 사용되지 않은 것 제거 (LRU) ------------------------------- LeetCode 146. LRU 캐시

코드 보기

class LRUCache {
    private static class CacheNode {
        int key, value;
        CacheNode prev, next;
        CacheNode(int k, int v) {
            key = k;
            value = v;
        }
    }

    private final Map map = new HashMap<>();
    private final CacheNode dummy = new CacheNode(0, 0);
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.next = dummy;
        dummy.prev = dummy;
    }

    public int get(int key) {
        CacheNode node = fetchNode(key);
        return node != null ? node.value : -1;
    }

    public void put(int key, int value) {
        CacheNode node = fetchNode(key);
        if (node != null) {
            node.value = value;
            return;
        }
        node = new CacheNode(key, value);
        map.put(key, node);
        appendToEnd(node);
        if (map.size() > capacity) {
            CacheNode first = dummy.next;
            map.remove(first.key);
            remove(first);
        }
    }

    private CacheNode fetchNode(int key) {
        if (!map.containsKey(key)) return null;
        CacheNode node = map.get(key);
        remove(node);
        appendToEnd(node);
        return node;
    }

    private void remove(CacheNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void appendToEnd(CacheNode node) {
        CacheNode last = dummy.prev;
        last.next = node;
        node.prev = last;
        dummy.prev = node;
        node.next = dummy;
    }
}

만료 시간이 있는 LRU ---------

코드 보기

public class TimedLRUCache {
    private static class TimedNode {
        int key, value;
        long expiry;
        TimedNode prev, next;
        TimedNode(int k, int v, long e) {
            key = k;
            value = v;
            expiry = e;
        }
    }

    private final int capacity;
    private final long duration;
    private final TimedNode sentinel = new TimedNode(0, 0, 0);
    private final Map keyMap = new HashMap<>();

    public TimedLRUCache(int cap, long dur) {
        capacity = cap;
        duration = dur;
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    public int get(int key) {
        TimedNode node = retrieveNode(key);
        return node != null ? node.value : -1;
    }

    public void put(int key, int value) {
        long currentTime = System.currentTimeMillis();
        TimedNode node = retrieveNode(key);
        if (node != null) {
            node.value = value;
            node.expiry = currentTime + duration;
            return;
        }
        node = new TimedNode(key, value, currentTime + duration);
        append(node);
        keyMap.put(key, node);
        if (keyMap.size() > capacity) {
            TimedNode oldest = sentinel.prev;
            keyMap.remove(oldest.key);
            remove(oldest);
        }
    }

    private TimedNode retrieveNode(int key) {
        if (!keyMap.containsKey(key)) return null;
        TimedNode node = keyMap.get(key);
        if (System.currentTimeMillis() > node.expiry) {
            remove(node);
            keyMap.remove(key);
            return null;
        }
        remove(node);
        append(node);
        return node;
    }

    private void remove(TimedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void append(TimedNode node) {
        node.prev = sentinel;
        node.next = sentinel.next;
        sentinel.next.prev = node;
        sentinel.next = node;
    }
}

태그: 자바 정렬 LRU캐시 알고리즘

10월 9일 16:30에 게시됨

괴물 클럽

주요 알고리즘 설명

인기 태그