๐Ÿ–ฅ Computer Science/Algorithm

[Algorithm] LRU(Least Recently Used) Cache ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€? (feat. ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜)

Fomagran ๐Ÿ’ป 2022. 9. 22. 10:55
728x90
๋ฐ˜์‘ํ˜•

 

์•ˆ๋…•ํ•˜์„ธ์š” Foma ์ž…๋‹ˆ๋‹ค.

 

์˜ค๋Š˜์€ ํšจ๊ณผ์ ์œผ๋กœ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๊ด€๋ฆฌํ•  ์ˆ˜ ์žˆ๋Š” ํŽ˜์ด์ง€ ๊ต์ฒด ๊ธฐ๋ฒ• ์ค‘ ํ•˜๋‚˜์ธ LRU Cache ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด์„œ ๋‹ค๋ค„ ๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

 

๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~


Least Recently Used Cache Algorithm์ด๋ž€?

 

LRU ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ FIFO, LFU, MFU ๋“ฑ๊ณผ ๊ฐ™์€ ํŽ˜์ด์ง€ ๊ต์ฒด ๊ธฐ๋ฒ• ์ค‘ ํ•˜๋‚˜์ธ๋ฐ์š”.

 

(ํŽ˜์ด์ง€ ๊ต์ฒด ๊ธฐ๋ฒ•์— ๋Œ€ํ•œ ๊ฒƒ์€ ์—ฌ๊ธฐ ์—์„œ ํ™•์ธํ•ด ์ฃผ์„ธ์š” ใ…œ)

 

๊ทธ ์ค‘์—์„œ๋„ ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉํ•˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ๊ต์ฒดํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.


LRU Design

 

LRU Cache ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉํ•˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ์‚ญ์ œํ•ด ์ฃผ๊ณ  ์ƒˆ๋กญ๊ฒŒ ์‚ฌ์šฉ๋œ ํŽ˜์ด์ง€๋ฅผ ์ถ”๊ฐ€ํ•ด ์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค.

 

์‚ญ์ œ์™€ ์ถ”๊ฐ€๋ฅผ ํšจ์œจ์ ์œผ๋กœ ๋น ๋ฅด๊ฒŒ ํ•˜๋Š” ๊ฒƒ์ด ํ•ต์‹ฌ์ธ๋ฐ์š”.

 

์ฆ‰, O(1) ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ํ•ด๋‹น ๊ธฐ๋Šฅ์„ ์ˆ˜ํ–‰ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

 

์ƒˆ๋กญ๊ฒŒ ์‚ฌ์šฉ๋œ ํŽ˜์ด์ง€๋ฅผ ๊ฐ€์žฅ ์ตœ๊ทผ์— ์‚ฌ์šฉ๋œ ๊ฒƒ์œผ๋กœ ๋น ๋ฅด๊ฒŒ ์ถ”๊ฐ€ํ•˜๊ณ  ์‚ญ์ œํ•˜๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

 

O(1)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋กœ ๊ฐ’์„ ์ถ”๊ฐ€ํ•˜๊ธฐ ์œ„ํ•ด์„  Linked List ์ž๋ฃŒ๊ตฌ์กฐ๊ฐ€ ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.

 

(Linked List์— ๋Œ€ํ•ด ์ž์„ธํžˆ ์•Œ๊ณ  ์‹ถ๋‹ค๋ฉด ์—ฌ๊ธฐ ์—์„œ ํ™•์ธํ•ด ์ฃผ์„ธ์š”!)

 

Linked List์˜ ๊ฐ€์žฅ ์•ž ๋…ธ๋“œ๋ฅผ head, ๊ฐ€์žฅ ๋’ค ๋…ธ๋“œ๋ฅผ tail์ด๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

head๋Š” ๊ฐ€์žฅ ์ตœ๊ทผ์˜ ํŽ˜์ด์ง€๋ฅผ ์ €์žฅํ•˜๊ณ  tail์€ ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉ๋˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค.

 

๋งŒ์•ฝ ๊ธฐ์กด Linked List์— ์ƒˆ๋กญ๊ฒŒ ์‚ฌ์šฉ๋œ ํŽ˜์ด์ง€๊ฐ€ ์ด๋ฏธ ์กด์žฌํ•œ๋‹ค๋ฉด ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ๋งจ ์•ž์œผ๋กœ ์ด๋™์‹œ์ผœ ์ค˜์•ผ๊ฒ ์ฃ ?

 

์•„๋ž˜์™€ ๊ฐ™์ด Linked List๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

๋งŒ์•ฝ ์ƒˆ๋กญ๊ฒŒ ์‚ฌ์šฉ๋œ ๋…ธ๋“œ๊ฐ€ 4๋ผ๋ฉด ๊ธฐ์กด์— ์žˆ๋˜ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•ด ์ค˜์•ผ ํ•  ๊ฒƒ ์ž…๋‹ˆ๋‹ค.

 

Linked List์—์„œ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•ด ์ฃผ๋Š” ๋ฐฉ๋ฒ•์€ ํ•ด๋‹น ์ž๋ฆฌ์˜ ๋…ธ๋“œ์˜ ์•ž ๋’ค๋ฅผ ์—ฐ๊ฒฐ์‹œ์ผœ ์ฃผ๋ฉด ๋˜์ฃ .

 

์ด ๋•Œ ํ•ด๋‹น ๋…ธ๋“œ์˜ ์ž๋ฆฌ๊ฐ€ ์–ด๋””์ธ์ง€ O(1) ์‹œ๊ฐ„ ๋ณต์žก๋„๋กœ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•ด์„œ Hash Table ์ž๋ฃŒ๊ตฌ์กฐ๊ฐ€ ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.

 

(Hash Table์— ๋Œ€ํ•ด ์ž์„ธํžˆ ์•Œ๊ณ  ์‹ถ๋‹ค๋ฉด ์—ฌ๊ธฐ ์—์„œ ํ™•์ธํ•ด ์ฃผ์„ธ์š”!)

 

๋…ธ๋“œ๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๊ฐ’์„ key๋กœ, ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ value๋กœ ๊ฐ€์ง€๊ณ  ์žˆ์–ด์•ผ ํ•˜์ฃ .

 

๊ทธ ๋‹ค์Œ ์ƒˆ๋กญ๊ฒŒ ์‚ฌ์šฉ๋œ ๋…ธ๋“œ๋ฅผ ํ—ค๋“œ๋กœ ์ด๋™ํ•ด ์ฃผ๋ฉด ๋˜์ฃ .

 

ํ—ค๋“œ๋กœ ์ด๋™์‹œ์ผœ ์ฃผ๋Š” ๋ฐฉ๋ฒ•์€ ์ด๋™์‹œํ‚ค๊ธฐ ์ „ ํ—ค๋“œ์˜ ์ด์ „ ๊ฐ’์œผ๋กœ ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐ์‹œ์ผœ ์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

๋งŒ์•ฝ Linked List์— ์—†๋Š” ๊ฐ’์ด ์ถ”๊ฐ€๋œ๋‹ค๋ฉด ์–ด๋–ป๊ฒŒ ํ•ด์ค˜์•ผ ํ• ๊นŒ์š”?

 

๊ธฐ์กด์˜ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œํ•˜๊ณ  ์ด๋™ํ•˜๋Š” ๊ณผ์ •์ด ํ•„์š”์—†์œผ๋ฏ€๋กœ ์œ„ ๊ณผ์ •์—์„œ head๋ฅผ ์ถ”๊ฐ€ํ•˜๋Š” ๊ฒƒ๋งŒ ํ•ด์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

์ด๋ ‡๊ฒŒ Linked List์™€ Hash Table ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ํ™œ์šฉํ•˜์—ฌ ๊ฐ€์žฅ ์ตœ๊ทผ์— ์ถ”๊ฐ€๋œ ๋…ธ๋“œ์™€ ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์“ฐ์ด์ง€ ์•Š์€ ๋…ธ๋“œ๋ฅผ head์™€ tail์— ์ €์žฅํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

 

๊ณ ๋กœ ๋งŒ์•ฝ ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉ๋˜์ง€ ์•Š์€ ๋…ธ๋“œ๋ฅผ ์‚ญ์ œ ํ•œ๋‹ค๋ฉด tail ๋…ธ๋“œ๋งŒ ์‚ญ์ œํ•ด ์ฃผ๋ฉด ๋˜๋Š” ๊ฒƒ์ด๋ฏ€๋กœ O(1)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋งŒ ๋ฐœ์ƒํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.


Source Code

 

(์ž์„ธํ•œ ์ฝ”๋“œ ์„ค๋ช…์€ ์—ฌ๊ธฐ ์—์„œ ํ™•์ธํ•ด ์ฃผ์„ธ์š”!)

 

class LRUCache {
    var head: Node?
    var tail: Node?
    var capacity = 0
    var cache = [Int: Node]()
    var count = 0
    
    init(_ capacity: Int) {
        self.capacity = capacity
    }
    
    func get(_ key: Int) -> Int {
        replace(key)
        return cache[key]?.val ?? -1
    }
    
    func put(_ key: Int, _ value: Int) {
        count += 1
        if head == nil {
            head = Node(key, value)
            tail = head
            cache[key] = head
            return
        }
        
        if cache[key] == nil {
            cache[key] = Node(key,value)
        } else {
            count -= 1
            cache[key]?.val = value
        }
        
        if count > capacity {
            delete(key)
        }
        
        replace(key)
    }
    
    func delete(_ key: Int) {
        cache[tail!.key] = nil
        if head === tail {
            head = cache[key]
            tail = head
        } else {
            tail = tail?.prev
            tail?.next = nil
        }
        
        count -= 1
    }
    
    func replace(_ key: Int) {
        if cache[key] == nil || head === cache[key] {
            return
        }

        cache[key]?.prev?.next = cache[key]?.next
        cache[key]?.next?.prev = cache[key]?.prev
        tail = cache[key] === tail ? cache[key]?.prev : tail
        
        cache[key]?.next = head
        head?.prev = cache[key]
        head = cache[key]
        head?.prev = nil
    }
}

Problem

 


Reference

 

728x90
๋ฐ˜์‘ํ˜•