🎯 To-do List

---

✅ 남은 백준 문제 풀기 | 1700 멀티탭 스케줄링
☑️ CSAPP 저자 직강 유튜브 보기
☑️ 운영체제 영상 보기
☑️ 운영체제 블로그 보기

📝 배운 것들

---

🏷️ Cache Replacement Policies

Cache replacement policies (또는 cache replacement algorithms)은 캐시 메모리가 가득 찼을 때, 캐시에서 어떤 데이터를 교체할지 결정하는 알고리즘입니다. 캐시 성능을 최적화하기 위해 이러한 알고리즘은 매우 중요합니다. 몇 가지 주요 정책은 다음과 같습니다:

1. FIFO (First-In-First-Out):

   • 가장 먼저 들어온 데이터를 가장 먼저 교체합니다. 구현이 간단하지만, 항상 효율적이지는 않습니다.

2. LRU (Least Recently Used):

   • 가장 오래 사용되지 않은 데이터를 교체합니다. 이는 데이터 접근 패턴이 최근에 사용된 데이터가 다시 사용될 가능성이 높다는 가정에 기반합니다.

3. LFU (Least Frequently Used):

   • 가장 적게 사용된 데이터를 교체합니다. 자주 사용되지 않는 데이터를 우선적으로 제거합니다.

4. OPT (Optimal Replacement):

   • 미래에 가장 늦게 사용될 데이터를 교체합니다. 이론적으로 최적의 성능을 보장하지만, 실제로 구현이 어렵습니다. 이는 미래의 접근 패턴을 알아야 하기 때문입니다. 종종 "Belady's Min Algorithm"이라고도 불립니다.

5. Random Replacement:

   • 임의의 데이터를 교체합니다. 간단하지만 성능이 일관되지 않을 수 있습니다.

6. Second-Chance Algorithm:

   • FIFO를 개선한 방법으로, 교체할 데이터를 선택할 때 한 번 더 기회를 줍니다. 만약 해당 데이터가 최근에 사용되었다면 교체하지 않고 다시 큐의 끝으로 이동시킵니다.

Bélády's Min Algorithm

"Bélády's Min Algorithm"은 OPT (Optimal Replacement)로도 알려져 있으며, 미래에 가장 늦게 사용될 페이지를 교체하는 알고리즘입니다. 이는 이론적으로 최적의 성능을 제공하지만, 실제 구현이 불가능한 경우가 많습니다. 이는 미래의 데이터 접근 패턴을 예측해야 하기 때문입니다. 따라서 일반적으로 실제 시스템에서는 사용되지 않지만, 다른 알고리즘의 성능을 평가하는 기준으로 사용됩니다.

추가 정보

• Cache replacement policies - Wikipedia
• Page replacement algorithm - Wikipedia

⚔️ 백준

---

📌 1700 멀티탭 스케줄링

from collections import defaultdict, deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
L = list(map(int, input().split()))
# 삭제 연산 비싸지 않은 큐를 사용
order = defaultdict(deque)
for i in range(len(L)):
    order[L[i]].append(i)

cnt = 0
box = set()
# 다음에 가장 늦게 나올 물건을 먼저 뽑아버린다
for j in range(max(N,K)):
    # 현재 들어갈 물건의 현재 order 제거
    order[L[j]].popleft()
    if len(box) < N:
        # 현재 들어가 있는 물건 수보다 박스 크기가 더 크다면
        box.add(L[j])
    else:
        if L[j] in box:
            # 현재 들어갈 물건이 박스에 이미 있다면 스킵
            continue
        else:
            # 다음에 가장 늦게 나올 물건 고르기
            latest_order, latest_obj = 0, 0
            for obj in box:    
                # 앞으로 안 나올거면 빼버려도 상관 없음
                if not order[obj]:
                    latest_obj = obj
                    break        
                elif latest_order < order[obj][0]:
                    latest_order = order[obj][0]
                    latest_obj = obj
            box.remove(latest_obj)
            box.add(L[j])
            cnt += 1

print(cnt)

이게 아닐까? 반례 못 찾겠네? 그럴듯하네? 하고 구현해봤는데 풀렸다.
기분은 좋은데 풀어도 푼 것 같지가 않다.

dp가 작은 문제를 찾는 것부터 어려웠다면,
그리디는 내가 쓰는 방법이 정말 완벽할까? 라는 증명을 하기가 어려운 것 같다.

해결책이 대충 예전 문제들과 비슷하니 그런갑다 할 수 있겠지만
100%의 확신이 들질 않는다.

찾아보니 지금 푼 이 방식이 belady's min algorithm이고,
이 알고리즘은 또 다시 Cache Replacement Policies와 연관이 되어 있는듯 하다.

나중에 찾아봐야될듯.

📌 11053 가장 긴 증가하는 부분 수열

# 인덱스를 매번 이전과 비교하여 각각 큰지 아닌지, 작아야 +1
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
dp = [1]*N

for i in range(1,N):
    for j in range(i):
        if A[j] < A[i] and dp[j]+1 >= dp[i]:
            dp[i] = dp[j]+1
print(max(dp))

사실상 이거 보고 베낌

2중 for문은 당연히 안될거라는 생각하고 배제했는데
이렇게 푸는 방법도 있었다.

(max(dp)가 아니라 print(i) 때려놓고 왜 안되지? 이런 실수도 햇었다)

자꾸 너무 fancy한 풀이, 문제의 매커니즘을 완벽하게 이해한 풀이를 지향하는데,
한 번 쯤은 컴퓨터식으로 생각해도 좋을 것 같다.

설명은 여기가 더 잘돼있는듯

위 링크의 O(N log N) 풀이

수열 10 20 30 40 11 12 13 14가 주어진다.
10 20 30 40 부분을 먼저 생각해보자.

수열을 순회하며 '해당 길이를 갖는 수열의 마지막 숫자가 될 수 있는 것 중에 제일 작은 숫자'를 배열에 넣어야 한다.
당연히 무슨 소리일지 이해가 안 될 것이다. 일단 예시를 보자.

배열에는 똑같이 10 20 30 40가 들어갈 것이다.
(길이 2를 갖는 수열은 10 20이므로 20이 들어간다.
길이 3을 갖는 수열은 10 20 30이므로 30이 들어간다.)

여기에 11 12 13 14 15가 차례대로 주어진다고 해보자.
10 20 30 40이 들어가 있던 배열이
10 11 12 13로 바뀌고, 거기에 14가 들어간다.

자세한 과정을 살펴보겠다.
11을 발견했다. 10 20 30 40을 봤더니 10보다는 크고 20보다는 작다.
10으로도 10을 만들 수 있고, 11로도 11을 만들 수 있다. 둘 다 길이가 1인 수열이다.
하지만 10이 11보다 작다. 그러므로 11은 배열에 넣지 않는다.

다음으로 12를 발견했다. 10 20 30 40을 봤더니 10보다는 크고 20보다는 작다.
12로 10 12를 만들 수 있고,
20으로 10 20을 만들 수 있다.
12가 더 작으니 10 12 30 40으로 갱신한다.

대충 이런식인듯.