[Inflearn] Least Recently Used

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 손으로 풀어보면서 해결 방법을 찾아보자.

     캐시의 크기 : 5   (3 <= S <= 10)

     작업의 개수 : 9   (5 <= N <= 1000)

     1 2 3 2 6 2 3 5 7  이 입력되었을 때,

     두 가지 경우가 있다.

     1. 해야할 작업이 캐시에 없다면 새로운 작업은 맨 앞으로 오고 모든 작업은 뒤로 밀린다.

     2. 해야할 작업이 캐시에 있다면 해당 작업은 맨 앞으로 오고 앞에 있던 작업은 한 칸씩 뒤로 밀린다.

     작업 1이 들어오면

     1 0 0 0 0

     작업 2가 들어오면

     2 1 0 0 0

 

    작업 3이 들어오면

    3 2 1 0 0

    작업 2가 들어오면

    작업 2는 캐시에 있는 상태이므로 2는 맨 앞으로 오고 2 앞에 있는 3은 밀리게 된다.

    2 3 1 0 0     

    작업 6이 들어오면

    6 2 3 1 0

    ...

    우선 작업을 캐시에 저장하기 전 캐시에 해당 작업이 있는지 확인한다.

    1. 해당 작업이 없을 경우, 맨 앞에 위치시키고 기존 작업들은 뒤로 한 칸씩 밀어준다.

       여기서 temp 변수에 밀 작업 번호를 잘 저장해주어야 할 것이다.

    2. 해당 작업이 캐시에 있을 경우, 작업의 index를 0으로 변경 후 탐색을 break;

       여기서도 1번과 동일하게 작업한다. 단 밀면서 0을 만나게 되면 더이상 뒤로 밀어줄 필요가 없기 때문에

       0 자리에 밀린 작업을 채워주고 break 해주면 된다.

    이렇게 구현해보면 될 텐데, 말은 쉽지~?!

    

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int main(void) {     freopen("input.txt", "rt", stdin);       int s, n, oper, i, j, tmp;       scanf("%d %d", &s, &n);     vector<int> cache(s);       for (i = 0; i < n; i++)     {         scanf("%d", &oper);           for (j = 0; j < s; j++)         {             if (cache[j] == oper)             {                 cache[j] = 0;                 break;             }         }           for (j = 0; j < s; j++)         {             tmp = cache[j];             cache[j] = oper;             oper = tmp;               if (!oper)                 break;         }     }       for (j = 0; j < s; j++)         printf("%d ", cache[j]);       return 0; } Colored by Color Scripter

cs

짜면서 뭔가 꼬여서 수정하면서 짜느라 solve 에 설명해놓은 방법과 약간(?) 다를 수 있다.

하지만 로직은 같을 것이다 !

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <stdio.h>   int C[20];   int main() {     int s, n, a, i, j, pos;       scanf("%d %d", &s, &n);       for(i=1; i<=n; i++){         scanf("%d", &a);           pos=-1;            for(j=0; j<s; j++)              if(C[j]==a)                  pos=j;           if(pos==-1){             for(j=s-1; j>=1; j--)                  C[j]=C[j-1];         }         else{             for(j=pos; j>=1; j--)                  C[j]=C[j-1];         }           C[j]=a;     }     for(i=0; i<s; i++) p         rintf("%d ", C[i]);       return 0; }

cs

강사님의 코드를 보고 현타(?)가 왔다.. 

나름 잘 짰다고 생각했는데.. 내 코드는 완전 비효율적인 코드였다..

우선 Cache Miss 나 Cache Hit 발생 시 작업이 밀리게되면 어차피 맨 마지막 작업은 날아가게 된다.

그 점을 이용해서 for 문을 역방향으로 돌리면서 c[i] = c[i-1] 해준다면 복잡하게 생각할 필요 없이

편하게 해결할 수 있었을 텐데 나는 정방향으로 돌리면서 코드가 더 복잡하게 되었다.

또, 해당 작업이 이미 캐시에 있을 경우 0으로 치환하는 방법보다 그 index 를 저장해준 후 

저장된 인덱스부터 마찬가지로 for 문을 역방향으로 돌려주면 된다. 어차피 이미 캐시에 있는 작업이니까 

C[0] 에 들어오게 될 것이고, 그 위치는 비어있는 상태가 될 것이니까..

이렇게 쉽게 풀릴 수 있던 문제였는데 너무 복잡하게 생각했다. 

기초부터 차근차근 열심히 쌓아가야지..

강사님이 짜신 코드의 동작은 다음과 같다.

입력된 작업을 순차적으로 받아오고, 해당 작업이 캐시에 있는지 확인을 한다. 

캐시에 해당 작업이 없을 경우 position 은 -1, 캐시에 있을 경우 해당 작업이 있던 index가 position에 저장 될 것이다.

다음으로, position 에 저장된 값이 -1일 경우와 아닐 경우를 분리해서 처리해주어야 한다.

position 이 -1 일 경우는 Cache Miss, position 이 -1이 아닐 경우는 Cache Hit 상태이다.

먼저 position 이 -1 일 경우,

s-1 부터 1 까지 역방향으로 반복문을 돌려주는데 이 때, c[i] = c[i-1] 로 캐시에 작업들을 뒤로 밀어준다.

반대로 position 이 -1 이 아닐 경우,

position 부터 1 까지 역방향으로 반복문을 돌려준다. position 이 -1일 때와 마찬가지로 c[i] = c[i-1] 로 캐시에 작업들을 뒤로 밀어준다.

여기서 1까지만 밀어주는 이유는 0 자리에 최근 사용된 작업이 들어와야 하기 때문에!

그래서 마지막으로 0 자리에 최근 사용된 작업을 넣어주면 된다.

이렇게 단순한 문제를 왜 이렇게 어렵게 생각하고 복잡하게 풀어냈는지.. 나중에 다시 생각해보고 풀어봐야겠다..

#. Result

  - Input --------------------------------------------------------

5 9

1 2 3 2 6 2 3 5 7

------------------------------------------------------------------

  - Output --------------------------------------------------------

7 5 3 2 6

------------------------------------------------------------------