Jieunny์˜ ๋ธ”๋กœ๊ทธ

[JS] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์บ์‹œ(LRU ์•Œ๊ณ ๋ฆฌ์ฆ˜) ๋ณธ๋ฌธ

Study/Coding Test

[JS] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์บ์‹œ(LRU ์•Œ๊ณ ๋ฆฌ์ฆ˜)

Jieunny 2023. 2. 24. 10:16

๐Ÿ“Œ  ๋ฌธ์ œ

์บ์‹œ

์ง€๋„๊ฐœ๋ฐœํŒ€์—์„œ ๊ทผ๋ฌดํ•˜๋Š” ์ œ์ด์ง€๋Š” ์ง€๋„์—์„œ ๋„์‹œ ์ด๋ฆ„์„ ๊ฒ€์ƒ‰ํ•˜๋ฉด ํ•ด๋‹น ๋„์‹œ์™€ ๊ด€๋ จ๋œ ๋ง›์ง‘ ๊ฒŒ์‹œ๋ฌผ๋“ค์„ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์—์„œ ์ฝ์–ด ๋ณด์—ฌ์ฃผ๋Š” ์„œ๋น„์Šค๋ฅผ ๊ฐœ๋ฐœํ•˜๊ณ  ์žˆ๋‹ค.
์ด ํ”„๋กœ๊ทธ๋žจ์˜ ํ…Œ์ŠคํŒ… ์—…๋ฌด๋ฅผ ๋‹ด๋‹นํ•˜๊ณ  ์žˆ๋Š” ์–ดํ”ผ์น˜๋Š” ์„œ๋น„์Šค๋ฅผ ์˜คํ”ˆํ•˜๊ธฐ ์ „ ๊ฐ ๋กœ์ง์— ๋Œ€ํ•œ ์„ฑ๋Šฅ ์ธก์ •์„ ์ˆ˜ํ–‰ํ•˜์˜€๋Š”๋ฐ, ์ œ์ด์ง€๊ฐ€ ์ž‘์„ฑํ•œ ๋ถ€๋ถ„ ์ค‘ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์—์„œ ๊ฒŒ์‹œ๋ฌผ์„ ๊ฐ€์ ธ์˜ค๋Š” ๋ถ€๋ถ„์˜ ์‹คํ–‰์‹œ๊ฐ„์ด ๋„ˆ๋ฌด ์˜ค๋ž˜ ๊ฑธ๋ฆฐ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค.
์–ดํ”ผ์น˜๋Š” ์ œ์ด์ง€์—๊ฒŒ ํ•ด๋‹น ๋กœ์ง์„ ๊ฐœ์„ ํ•˜๋ผ๊ณ  ๋‹ฆ๋‹ฌํ•˜๊ธฐ ์‹œ์ž‘ํ•˜์˜€๊ณ , ์ œ์ด์ง€๋Š” 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;
}

์™€ ๋ฟŒ๋“ฏํ•ด