섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 4. Least Recently Used

문제

• 캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가
• 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다.
• 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다.
• LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다.
• 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.

• 캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후
• 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.

입력

• 첫 번째 줄에 캐시의 크기인 S(3<=S<=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다.
• 두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~100 이다.

출력

• 마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.

입출력 예제

---

풀이방식

이번 문제는 배열을 사용하여 푸는 문제이다.

예시를 통해 문제를 자세히 이해해보자.

---

크기가 5인 캐시 배열에 1이라는 값이 들어왔다.

다음으로는 2가 들어왔다.

다음으로는 3가 들어왔다.

다음으로는 2가 들어왔다. 이 값은 배열에 이미 있다는 점에 주의하자.

2가 있는 위치에서 앞으로 이동하며 앞에 있는 값을 뒤로 넣어준다.

그러면 다음과 같은 배열이 만들어진다.

이제 새로 들어온 2를 0번째에 넣어준다.

다음으로 6이 들어왔으므로 다음과 같은 배열이 완성된다.

해당 과정을 반복한다.

---

설계과정

1. 캐시 배열에 새로 들어오는 값과 동일한 값이 없으면 기존 값의 인덱스에 1을 더하고 신규 값을 0번째에 넣는다.

2. 캐시 배열에 이미 있는 값이 또다시 들어오면 있는 값의 인덱스 위치를 저장한다.

3. 저장한 인덱스 위치부터 1번째까지 돌면서 값을 뒤로 하나씩 밀어준다.

4. 그 후에 0번째에 새로 들어온 값을 넣는다.

5. 새로 들어오는 값은 무조건 0번째에 위치한다. 

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. int[ ] 형으로 메소드를 작성한다.

 

3. cache 배열을 선언한다.

 

4. pos 변수를 선언하고 -1로 초기화한다.

• pos : 인덱스 번호를 저장할 변수

5. 0부터 cache 배열의 크기만큼 도는 for문을 작성한다.

• size : cache 배열의 크기이다.

5. x 값이 cache 배열에 있는지 없는지 확인한다.

• x 값이 캐시 배열에 있으면 hit 라고 생각하자.
• hit 이면 값이 있는 인덱스 값을 저장한다.
• 배열에 값이 없으면 miss 라고 생각하자.
• miss 라면 pos가 -1로 유지된다.

5. x 값이 캐시 배열에 없으면 앞의 값을 뒤로 하나씩 이동한다.

• pos가 -1이라는 것은 캐시 배열에 값이 없다는 의미이다.
• size-1 부터 1까지 1씩 주는데, 이는 인덱스는 0부터 시작하므로 1을 빼줘야 맨 끝 값을 가져올 수 있기 때문이다.
• cache[ i ] 번째에 그보다 앞 인덱스인 cache[ i-1 ] 값을 넣어서 한칸씩 뒤로 밀어준다.

5. x 값이 캐시 배열에 있으면 hit 된 지점부터 1번째까지 하나씩 줄면서 앞뒤 값을 바꿔준다.

• pos 변수에는 hit 된 변수의 인덱스 값이 들어있다.
• 즉 배열에 존재하는 값의 인덱스부터 1번째까지 돌면서 한칸씩 뒤로 민다는 의미이다.

5. 새로 들어온 값을 0번째에 넣어준다.

• 0번째에는 무조건 새로 들어온 값이 들어간다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.