[TIL] 13-05-2021

LRU 알고리즘(Least Recently Used Alghorithm)

• 페이지 교체 알고리즘은 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다.
• 페이지 교체 알고리즘의 예로, FIFO, LFU, LRU 알고리즘 등이 있다.

LRU 알고리즘

• LRU 알고리즘: 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법
  단점 : 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야 함. 큰 오버헤드가 발생
  Input : 123145
  Output : 5413
  
  4초 : 1은 재참조된 것이므로, 가장 오랫동안 참조되지 않은 순으로 저장된 순서를 변경한다.
  6초 : cache size가 가득차 5가 들어갈 수 없으므로, 가장 오랫동안 참조되지 않은 2를 제거한 후 저장한다.

LRU를 적용한 프로그래머스 알고리즘 문제

def solution(cacheSize, cities):
    answer = 0
    count = 0
    temp = []
    if cacheSize == 0:
        answer = len(cities) * 5
    else:
        for city in cities:
            city = city.lower()
            if city in temp:
                temp.remove(city)
                temp.append(city)
                count += 1
            elif len(temp) < cacheSize:
                temp.append(city)
                count += 5
            else:
                temp.remove(temp[0])
                temp.append(city)
                count += 5
        answer = count
    return answer

list에서 인덱스 찾기

list 전체 범위에서 인덱스 찾기

list에서 인덱스를 찾기 위해선 index함수를 사용한다.

a = ["hello", "new", "world"]
print(a.index("hello")) # 0
print(a.index("new")) # 1
print(a.index("world")) # 2

list 특정 범위에서 인덱스 찾기

특정 범위에서 인덱스를 찾으려면 범위를 설정해준다.
범위 내에 찾는 문자가 없으면 ValueError를 출력한다.

a = ["hello", "new", "world"]
print(a.index("hello", 0, 1) # 0
print(a.index("new", 1, 3) # 1
print(a.index("world", 0, 1)) # ValueError: 'world' is not in list

range함수에서 발생할 수 있는 오류

range의 시작과 끝

• ValueError: max() arg is an empty sequence
  빈 문자열을 입력하고 range의 끝 범위가 0이 될 경우
• ValueError: min() arg is an empty sequence
  빈 문자열을 입력하고 range의 첫 범위가 0이 될 경우

출처 :
LRU 알고리즘