[제주코딩베이스캠프] 눈떠보니 코딩테스트 전날 | 문제4. 자리를 양보해가며!

---

LRU 알고리즘 (Least Recently Used Algorithm)

: 메모리 상에서 가장 최근에 사용한 적이 없는 캐시의 메모리부터 대체하며

새로운 데이터로 갱신시켜준다.

 

즉, 부재가 발생했을 경우

가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘이다.

교체가 자주 일어나는 페이지의 자리를 보존해준다는 의미이다.

 

※ 페이지부재

: 메모리에 적재된 페이지중에 사용 페이지가 없을 때를 가리키는 말이다.

 

---

페이지교체 알고리즘

> 페이지 교체 알고리즘은 메모리를 관리하는 운영체제에서,

페이지 부재가 발생하여 새로운 페이지를 할당하기 위해

현재 할당된 페이지 중 어느 것을 교체할지를 결정하는 방법입니다.

 

---

 

HIT > 참조하는 값이 이미 페이지에 존재할 경우!

1회 false (척추동물)

2회 false (어류)

3회 hit (이미 페이지에 있었으니까) (척추동물)

4회 false (무척추동물)

5회 false (파충류)

6회 hit (척추동물)

7회 false (어류)

8회 hit (파충류)

 

동물= ['척추동물', '어류', '척추동물', '무척추동물', '파충류', '척추동물', '어류', '파충류']
def solution(동물,자리):
  의자=[]*자리
  answer = 0

  for i in 동물:
    if len(의자)<3: # 의자가 꽉 차있지 않은 경우
      if i in 의자:
        히트된페이지=의자.pop(의자.index(i))
        의자.append(히트된페이지) 
        answer+=1 # 종이 같을경우 무릎에 앉을 수 있는데 이때는 1초로 카운트한다. = hit일 경우
      else:
        의자.append(i)
        answer+=60 # 아무도 없거나 자리가 꽉차있을 때 이종이 들어올 경우 청소하는 시간 1분 = false일 경우
    
    else: # 의자가 꽉 차있는 경우
      if i in 의자:
        히트된페이지=의자.pop(의자.index(i))
        의자.append(히트된페이지) 
      else:
        의자.pop(0) # 가장 최근에 히트된 적이 없는 경우이다. 
        의자.append(i)
        answer+=60 #아무도 없거나 자리가 꽉차있을 때 이종이 들어올 경우 청소하는 시간 1분
  return f'{answer//60}분 {answer%60}초'
solution(동물,3)

리스트 앞쪽에 위치해있을 경우

오랫동안 사용하지 않은 페이지에 속한다.

그래서 페이지부재가 일어날 경우에는 pop(0)을 해서

가장 오랫동안 사용하지 않은 페이지와

새로 들어오는 페이지를 교체해준다 (LRU 알고리즘)

 

 

 

 

 

 

- by 제코베 서포터즈 2기 여니(yeony) -