[프로그래머스/Lv.2 (Swift)] LRU 알고리즘

2018 KAKAO BLIND RECRUITMENT - [1차] 캐시

 

 

해당 문제는 LRU 알고리즘만 구현하면 쉽게 해결됩니다.

 

 

캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
cache hit일 경우 실행시간은 1이다.
cache miss일 경우 실행시간은 5이다.

(2018 KAKAO BLIND RECRUITMENT - [1차] 캐시)

 

 

---

 

그렇다면 LRU 알고리즘이란 무엇일까요?

 

Least Recently Used,

말 그대로 가장 오랫동안 사용되지 않은 데이터를 의미합니다.

 

즉, 오랫동안 사용되지 않은 데이터는 제거하고

최신 데이터를 유지하는 알고리즘입니다.

 

 

 

주어진 캐시 크기만큼의 공간이 할당된 모습인데요.

 

새로운 값을 참조할 때,

 

1. 해당 값이 캐시 안에 없을 경우 ➡️ Head 부분에 add

    1-1) 만약 캐시 크기를 초과할 경우 ➡️ Tail 부분 drop

2. 해당 값이 캐시 안에 있을 경우 ➡️ Head 부분으로 move

 

의 과정을 거칩니다.

 

 

쉽게 말해,

head 쪽으로 올수록 최신값,

tail 쪽으로 갈수록 이전값이 되도록 유지하면 됩니다.

 

 

여기서 Hit과 Miss는 각각 참조 시에
✅ Hit: 캐시 안에 이미 값이 존재하는 경우
❎ Miss: 캐시 안에 값이 없어, add 해주어야 하는 경우
입니다.

 

 

---

 

 

LRU 알고리즘을

해시 테이블과 Double Linked List를 이용해서 풀어봅시다.

 

 

우선, 각 노드들은 위와 같은 구조를 가지는데요.

 

Double Linked List를 구현하기 위해서는,

해당 Node의 앞뒤로 어떤 Node가 연결되어 있는지 알아야 합니다.

 

 

따라서

1. 해당 노드를 식별할 Key
2. 이전 Node
3. 이후 Node
4. 현재 Node의 데이터 (해당 문제에서는 불필요)

 

의 값을 가지고 있어야 하고,

 

 

이를 코드로 나타내면 아래와 같습니다.

private class Node {
    var key: Key
    var next: Node?
    var prev: Node?
    
    init(key: Key) {
        self.key = key
    }
}

 

 

 

---

 

다음으로는 Hit과 Miss,

각각의 경우에 대해 생각해보며 설계해보았습니다.

 

 

1. Miss

 

 

 

우선 2라는 값을 참조하고자 할 때,

Cache 안에 값이 없기 때문에 Miss인 경우를 살펴보겠습니다.

 

 

 

 

위와 같은 순서도를 생각해 볼 수 있겠는데요.

 

우선, Miss인지 Hit인지 따져보기 위해서는

캐시 안에 해당 키가 존재하는지를 확인해야 합니다.

 

 

캐시 안에 키가 없는, Miss의 경우이기 때문에

맨 앞(head)에 새로운 노드를 삽입합니다.

 

그런데 만약, 삽입했는데 캐시 크기보다 넘치면

맨 마지막(tail)의 노드를 지워줘야 합니다.

 

 

 

---

2. Hit

그렇다면 Hit의 경우는 어떨까요?

 

위와 같이, 이미 캐시 안에 존재하는 1을 참조해보았습니다.

 

 

이번에는 캐시 안에 해당 키가 존재하는 경우인데요,

 

해당하는 노드를 맨 앞(head)으로 가져옵니다.

 

이를 위해서는 직관적으로, 

원래 위치의 노드는 지워버리고

맨 앞에 그 노드를 넣어주면 될 것입니다.

 

 

---

 

 

이에 해당하는 put() 함수를 구현해보기 전에,

맨 처음에 만든 Node와 함께 LRUCache를 만들어줍니다.

 

class LRUCache<Key: Hashable> {
	private class Node {
    	var key: Key
        var prev: Node?
        var next: Node?
        
        init(key: Key) {
        	self.key = key
        }
    }
    
    private var capacity: Int
    private var dict: [Key: Node] = [:]
    private var head: Node?
    private var tail: Node?
    
    init(capacity: Int) {
    	self.capacity = capacity
    }
    
    // 값을 참조합니다.
    func put(_ key: Key) { }
}

 

 

캐시의 크기를 지정할 capacity와

캐시에 들어갈 노드들을 저장할 dict,

head와 tail 노드를 저장할 변수들을 지정합니다.

 

 

 

그리고 put의 구현부를 완성해봅시다.

 

// 캐시에 값을 넣습니다.
func put(_ key: Key) {
    // 키가 이미 존재하면
    if let existingNode = dict[key] {
        moveToHead(existingNode)
    } else {
        // 새로운 키 삽입
        let newNode = Node(key: key)
        dict[key] = newNode
        addToHead(newNode)

        if dict.count > capacity {
            removeLeastRecentlyUsed()
        }
    }
}

 

 

그 아래로,

필요한 함수들의 구현부를 각각 완성해봅시다.

 

// 가장 최근에 사용된 값을 맨 앞으로 가지고 옵니다.
private func moveToHead(_ node: Node) {
    // 해당 위치의 노드를 제거하고
    removeNode(node)
    // 맨 앞에 추가합니다.
    addToHead(node)
}

 

 

// 노드를 제거합니다.
private func removeNode(_ node: Node) {
    let prevNode = node.prev
    let nextNode = node.next

    if let prevNode = prevNode {
        prevNode.next = nextNode
    } else {
        head = nextNode
    }

    if let nextNode = nextNode {
        nextNode.prev = prevNode
    } else {
        tail = prevNode
    }
}

 

// 노드를 맨 앞에 추가합니다.
private func addToHead(_ node: Node) {
    node.next = head
    node.prev = nil

    if let headNode = head {
        headNode.prev = node
    }

    head = node

    if tail == nil {
        tail = node
    }
}

 

private func removeLeastRecentlyUsed() {
    guard let tailNode = tail else { return }
    dict[tailNode.key] = nil
    removeNode(tailNode)
}

 

 

---

 

코드가 다소 길지만,

 

해시 테이블과 이중 연결리스트를 사용해 O(1)의 시간복잡도를 가지고,

이를 배열 N만큼 수행하기 때문에 최종 O(N)의 시간복잡도를 가집니다.

 

import Foundation

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    
    var cache = LRUCache<String>(capacity: cacheSize)
    
    for city in cities {
        let city = city.uppercased()
        cache.put(city)
    }
    
    return cache.result
}

class LRUCache<Key: Hashable> {
    private class Node {
        var key: Key
        var next: Node?
        var prev: Node?
        
        init(key: Key) {
            self.key = key
        }
    }
    
    private var capacity: Int
    private var dict: [Key: Node] = [:]
    private var head: Node?
    private var tail: Node?
    
    var result = 0
    
    init(capacity: Int) {
        self.capacity = capacity
    }
    
    // 값을 넣음
    func put(_ key: Key) {
        // hit
        if let existingNode = dict[key] {
            // head로 옮김
            moveToHead(existingNode)
            result += 1
        } else { // miss
            // head에 값 추가
            let newNode = Node(key: key)
            dict[key] = newNode
            addToHead(newNode)
            result += 5
            if dict.count > capacity {
                removeLeastRecentlyUsed()
            }
        }
    }
    
    private func moveToHead(_ node: Node) {
        removeNode(node)
        addToHead(node)
    }
    
    private func removeNode(_ node: Node) {
        let prevNode = node.prev
        let nextNode = node.next
        
        if let prevNode = prevNode {
            prevNode.next = nextNode
        } else {
            head = nextNode
        }
        
        if let nextNode = nextNode {
            nextNode.prev = prevNode
        } else {
            tail = prevNode
        }
    }
    
    private func addToHead(_ node: Node) {
        node.next = head
        node.prev = nil
        
        if let headNode = head {
            headNode.prev = node
        }
        
        head = node
        
        if tail == nil {
            tail = node
        }
    }
    
    private func removeLeastRecentlyUsed() {
        guard let tailNode = tail else { return }
        dict[tailNode.key] = nil
        removeNode(tailNode)
    }
}