관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 프로그래머스 캐시 -2018 KAKAO BLIND RECRUITMENT- 본문

알고리즘/일반(단순구현)

[알고리즘] 프로그래머스 캐시 -2018 KAKAO BLIND RECRUITMENT-

막무가내막내 2020. 3. 29. 20:31
728x90

 

 

https://programmers.co.kr/learn/courses/30/lessons/17680

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

캐시 문제를 풀어 봤습니다. ㅎㅎ

이 문제는 교체 알고리즘으로 LRU 를 사용하는 캐시 메모리의 hit 값을 구하는 문제입니다.

LRU 운영체제 시간에 보고 정보처리기사 시험준비때 보고 오랜만에 보네요.

LRU란 Least Recently Used 를 의미하며 캐시 교체알고리즘으로 사용되기도 합니다.

간단하게 설명하자면 캐시는 특정 크기의 메모리를 갖고 있는데 캐시 메모리가 꽉 찼을 때 새로운 값이 들어온다면 영어 해석 그대로 가장 최근에 사용되지 않은 값이 새로들어오는 값과 교체가 되야합니다. 

그러므로 캐시는 최근에 사용한 값을 알고 있어야하고 교체시 마다 갱신해줘야 합니다.

LRU만 이해한다면 쉬운 문제였네요.

 

설명과 코드는 밑과 같습니다.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();

    }

    public int solution(int cacheSize, String[] cities) {
        List<String> cityList = new ArrayList<>(cacheSize); // 큰 인덱스일 경우 최근에 사용
        int answer = 0;

        for (int i = 0; i < cities.length; i++) {
            //캐시사이즈 0인 경우
            if (cacheSize == 0) {
                answer = 5 * cities.length;
                break;
            }
            String city = cities[i].toUpperCase();
            // 캐시 꽉찬 경우
            if (cityList.size() >= cacheSize) {
                // 이미 캐시에 있는 경우 hit 하고 LRU 우선순위 재조정
                if (cityList.contains(city)) {
                    cityList.remove(city);
                    cityList.add(cityList.size(), city);
                    answer += 1;
                } else {
                    //캐시에 없는 경우 cache miss 하고 LRU 우선순위 변경
                    cityList.remove(0);
                    cityList.add(cityList.size(), city);
                    answer += 5;
                }
            } else { //캐시 아직 비어있는 경우
                if (cityList.contains(city)) { // hiy
                    cityList.remove(city);
                    cityList.add(cityList.size(), city);
                    answer += 1;
                } else { //miss
                    cityList.add(cityList.size(), city);
                    answer += 5;
                }
            }
        }
        return answer;
    }
}

 

 

이제 BFS, DFS, DP, 백트랙킹 다시 공부해야겠습니다... 귀차니즘 탈출해야겠씀다

댓글과 공감은 큰 힘이 됩니다. 감사합니다!

728x90
Comments