Jieunny์ ๋ธ๋ก๊ทธ
[JS] ํ๋ก๊ทธ๋๋จธ์ค - ์บ์(LRU ์๊ณ ๋ฆฌ์ฆ) ๋ณธ๋ฌธ
๐ ๋ฌธ์
์บ์
์ง๋๊ฐ๋ฐํ์์ ๊ทผ๋ฌดํ๋ ์ ์ด์ง๋ ์ง๋์์ ๋์ ์ด๋ฆ์ ๊ฒ์ํ๋ฉด ํด๋น ๋์์ ๊ด๋ จ๋ ๋ง์ง ๊ฒ์๋ฌผ๋ค์ ๋ฐ์ดํฐ๋ฒ ์ด์ค์์ ์ฝ์ด ๋ณด์ฌ์ฃผ๋ ์๋น์ค๋ฅผ ๊ฐ๋ฐํ๊ณ ์๋ค.
์ด ํ๋ก๊ทธ๋จ์ ํ
์คํ
์
๋ฌด๋ฅผ ๋ด๋นํ๊ณ ์๋ ์ดํผ์น๋ ์๋น์ค๋ฅผ ์คํํ๊ธฐ ์ ๊ฐ ๋ก์ง์ ๋ํ ์ฑ๋ฅ ์ธก์ ์ ์ํํ์๋๋ฐ, ์ ์ด์ง๊ฐ ์์ฑํ ๋ถ๋ถ ์ค ๋ฐ์ดํฐ๋ฒ ์ด์ค์์ ๊ฒ์๋ฌผ์ ๊ฐ์ ธ์ค๋ ๋ถ๋ถ์ ์คํ์๊ฐ์ด ๋๋ฌด ์ค๋ ๊ฑธ๋ฆฐ๋ค๋ ๊ฒ์ ์๊ฒ ๋์๋ค.
์ดํผ์น๋ ์ ์ด์ง์๊ฒ ํด๋น ๋ก์ง์ ๊ฐ์ ํ๋ผ๊ณ ๋ฆ๋ฌํ๊ธฐ ์์ํ์๊ณ , ์ ์ด์ง๋ DB ์บ์๋ฅผ ์ ์ฉํ์ฌ ์ฑ๋ฅ ๊ฐ์ ์ ์๋ํ๊ณ ์์ง๋ง ์บ์ ํฌ๊ธฐ๋ฅผ ์ผ๋ง๋ก ํด์ผ ํจ์จ์ ์ธ์ง ๋ชฐ๋ผ ๋๊ฐํ ์ํฉ์ด๋ค.
์ดํผ์น์๊ฒ ์๋ฌ๋ฆฌ๋ ์ ์ด์ง๋ฅผ ๋์, DB ์บ์๋ฅผ ์ ์ฉํ ๋ ์บ์ ํฌ๊ธฐ์ ๋ฐ๋ฅธ ์คํ์๊ฐ ์ธก์ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ ํ์
- ์บ์ ํฌ๊ธฐ(cacheSize)์ ๋์์ด๋ฆ ๋ฐฐ์ด(cities)์ ์ ๋ ฅ๋ฐ๋๋ค.
- cacheSize๋ ์ ์์ด๋ฉฐ, ๋ฒ์๋ 0 โฆ cacheSize โฆ 30 ์ด๋ค.
- cities๋ ๋์ ์ด๋ฆ์ผ๋ก ์ด๋ค์ง ๋ฌธ์์ด ๋ฐฐ์ด๋ก, ์ต๋ ๋์ ์๋ 100,000๊ฐ์ด๋ค.
- ๊ฐ ๋์ ์ด๋ฆ์ ๊ณต๋ฐฑ, ์ซ์, ํน์๋ฌธ์ ๋ฑ์ด ์๋ ์๋ฌธ์๋ก ๊ตฌ์ฑ๋๋ฉฐ, ๋์๋ฌธ์ ๊ตฌ๋ถ์ ํ์ง ์๋๋ค. ๋์ ์ด๋ฆ์ ์ต๋ 20์๋ก ์ด๋ฃจ์ด์ ธ ์๋ค.
์ถ๋ ฅ ํ์
- ์ ๋ ฅ๋ ๋์์ด๋ฆ ๋ฐฐ์ด์ ์์๋๋ก ์ฒ๋ฆฌํ ๋, "์ด ์คํ์๊ฐ"์ ์ถ๋ ฅํ๋ค.
์กฐ๊ฑด
- ์บ์ ๊ต์ฒด ์๊ณ ๋ฆฌ์ฆ์ LRU(Least Recently Used)๋ฅผ ์ฌ์ฉํ๋ค.
- cache hit์ผ ๊ฒฝ์ฐ ์คํ์๊ฐ์ 1์ด๋ค.
- cache miss์ผ ๊ฒฝ์ฐ ์คํ์๊ฐ์ 5์ด๋ค.
๐ก ์์ด๋์ด
LRU ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ๋ผ๊ณ ๋ฌธ์ ์ ๋์์๋ค.
๊ทผ๋ฐ ๋ชฐ๋ผ์ ์ฐพ์๋ดค๋น..ใ ใ
โ LRU ์๊ณ ๋ฆฌ์ฆ(Least Recently Used)์ด๋?
โ๏ธ ๊ฐ์ฅ ์ค๋ ์๊ฐ ์ฌ์ฉ๋์ง ์์ ํ์ด์ง๋ฅผ ๊ต์ฒดํ๋ ํ์ด์ง ๊ต์ฒด ์๊ณ ๋ฆฌ์ฆ
โฐ ์ฃผ๋ก ์บ์์์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ค์ฐ๊ธฐ ์ํด ์ฌ์ฉํ๋ค.
โฐ ์บ์๋ ์์์ด ํ์ ๋์ด ์์ผ๋ฉฐ ์ด๋ค ๋ฐ์ดํฐ๋ฅผ ๋จ๊ธฐ๊ณ , ์ด๋ค ๋ฐ์ดํฐ๋ฅผ ์ง์ธ์ง์ ๋ํ ์๊ณ ๋ฆฌ์ฆ์ด ํ์ํ๋ค.
โฐ ์ค๋ ์ฐธ์กฐ๋์ง ์์ ๋ฐ์ดํฐ๋ฅผ ๋ด๋ณด๋ด๋ '์๊ฐ ์ง์ญ์ฑ'์ ์ฑ์ง์ ๊ฐ์ง๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
โฐ ์บ์ ์ฌ์ด์ฆ๊ฐ 5์ด๊ณ 1 2 3 4 5 ์์๋ก ์ ์ฅ๋์๋ค๋ฉด, 1์ด ๊ฐ์ฅ ์ต๊ทผ์ ์ฐ์ธ ์์ ์ด๊ณ 5๋ ๊ฐ์ฅ ์ค๋ซ๋์ ์ฐ์ด์ง ์์ ์์ ์ด๋ค.
โฐ Cache miss ์ธ ๊ฒฝ์ฐ
- ์บ์ ๋ฐฐ์ด์ ์ฒซ๋ฒ์งธ ์์์ ๊ฐ ์ถ๊ฐ
- ์บ์ ๋ฐฐ์ด์ ๋ง์ง๋ง ์์ ์ญ์ (๊ฐ์ฅ ์ค๋ ์ฌ์ฉ๋์ง ์์ ์์์ด๋ฏ๋ก)
โฐ Cache hit์ธ ๊ฒฝ์ฐ
- ์บ์ ๋ฐฐ์ด์์ hit ์ง์ ๊น์ง ์ด๋
- hit ๊ฐ์ ์บ์ ๋ฐฐ์ด 0๋ฒ์ผ๋ก ์ด๋(๋ฐฉ๊ธ ์ฌ์ฉ๋์๊ธฐ ๋๋ฌธ์)
์ ์ค๋ช ์ ๋ฐํ์ผ๋ก ๊ตฌํํด๋ดค๋ค.
โ๏ธ ํ์ด
function solution(cacheSize, cities) {
var answer = 0;
const cache = [];
for(let i=0; i<cities.length; i++){
cities[i] = cities[i].toLowerCase();
// ๋์๋ฌธ์ ๊ตฌ๋ถ ์ํ๋ฏ๋ก ์ผ๋จ ๋ชจ๋ ์๋ฌธ์๋ก ๋ฐ๊ฟ์ค๋ค.
if(cache.length < cacheSize){ // ์บ์ ์ฌ์ด์ฆ๋ณด๋ค ์บ์ ๋ฐฐ์ด์ด ์์ ๋
if(!cache.includes(cities[i])) {
// ์บ์๋ฏธ์ค๋ฉด ๋งจ ์์ ์์ ์ถ๊ฐํ๊ณ ์๊ฐ +5
cache.unshift(cities[i]);
answer += 5;
}
else {
// ์บ์ ํํธ๋ฉด ๊ทธ ์์น๋ก ๊ฐ์ ๊ทธ ์์๋ฅผ ๋งจ ์์ผ๋ก ๋นผ์ค๊ณ ์๊ฐ +1
let idx = cache.indexOf(cities[i]);
cache.unshift(cities[i]);
cache.splice(idx+1, 1);
answer +=1;
}
}
else{ // ์บ์ ์ฌ์ด์ฆ๋ณด๋ค ์บ์ ๋ฐฐ์ด์ด ํด ๋
if(!cache.includes(cities[i])) {
cache.unshift(cities[i]);
cache.pop();
answer += 5;
}
else {
let idx = cache.indexOf(cities[i]);
cache.unshift(cities[i]);
cache.splice(idx+1, 1);
answer +=1;
}
}
}
return answer;
}
์ ๋ฟ๋ฏํด
'Study > Coding Test' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[JS] ํ๋ก๊ทธ๋๋จธ์ค - ์์ฅ (0) | 2023.02.27 |
---|---|
[JS] ํ๋ก๊ทธ๋๋จธ์ค - ํ๋ ฌ์ ๊ณฑ์ (0) | 2023.02.27 |
[JS] ํ๋ก๊ทธ๋๋จธ์ค - ๊ดํธ ํ์ ํ๊ธฐ (0) | 2023.02.22 |
[JS] ํ๋ก๊ทธ๋๋จธ์ค - H-index (0) | 2023.02.22 |
[JS] ํ๋ก๊ทธ๋๋จธ์ค - ๋ฉ๋ฆฌ๋ฐ๊ธฐ (0) | 2023.02.21 |