์๋ ํ์ธ์ 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
- https://school.programmers.co.kr/learn/courses/30/lessons/17680
- https://leetcode.com/problems/lru-cache/
Reference
'๐ฅ Computer Science > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algorithm] Floyd's Cycle Detection์ด๋? (feat. Linked List) (2) | 2022.09.18 |
---|---|
[Algorithm] ์์์ ๊ด๋ จ๋ ์๊ณ ๋ฆฌ์ฆ(feat. ์๋ผํ ์ค ํ ๋ค์ค์ ์ฒด) (0) | 2022.01.19 |
[Algorithm] ๋์ ๊ณํ๋ฒ(Dynamic Programming)์ด๋? (0) | 2021.12.09 |
[Algorithm] ํต ์ ๋ ฌ(Quick Sort)๋? (feat. Swift) (0) | 2021.10.25 |
[Algorithm] ํ ์ ๋ ฌ(HeapSort)์ด๋? (feat.Swift) (0) | 2021.10.19 |
๋๊ธ