[JAVA] 1700 - 멀티탭 스케줄링 💛1 : OS시간에 배웠던 Page Replacement 알고리즘 적용문제 (Optimal Page Replacement)

들어가며

https://www.acmicpc.net/problem/1700

콘센트 구멍의 갯수 N개와, 앞으로 어떤 전기용품을 콘센트에 꽃을 것인지에 대한 순서 정보 K개가 주어진다. 이때 하나씩 플러그를 빼는 최소의 횟수를 정답으로 출력하는 문제다.

본문으로

딱 읽었을 때 좀 막막했다. 그리디하게 선택하는 문제인 것은 느낌이 오는데, 그리디의 대표 풀이법인 정렬, PriorityQueue를 적용할 부분이 보이지도 않았다. 그리고 가장 막막한것이 무엇을 먼저 빼야 부분 최적해인지 판별해내는 아이디어를 떠올리는 것 자체가 어려웠다.

처음 생각했던 것은 기존 콘센트를 뽑아야하는 순간이 왔을때, 각 주어지는 종류와 순서를 저장하는 구조체 클래스를 만들어서 그것을 저장하는 인접리스트를 구현하고자 해봤는데... 구현자체가 너무 어려워져서 포기했다.

 

결론 먼저 말하자면 OS에서 자주 나오는 Page Replacement 알고리즘 중 Optimal Page Replacement 알고리즘을 구현하면 쉽게 풀리는 문제였다. ㅎㅎ 구현자체가 어려우니 구현에 들어가기 전에 잠시 OS시간에 배웠던 알고리즘을 정리해보고자 한다.

---

OS에서 Page Replacement 알고리즘은 메모리가 가득 찼을 때 어떤 page를 제거할지를 결정하는 방식이다. 대표적인 알고리즘들을 간단히 정리하면 다음과 같다.

1. FIFO Page Replacement

가장 먼저 들어온 페이지를 제거하는 방식이다. 큐처럼 동작하며 구현이 가장 간단하다.
다만 오래 사용되었다고 해서 중요도가 낮은 것은 아니기 때문에 비효율적일 수 있으며, 프레임 수를 늘렸음에도 page fault가 증가하는 Belady’s anomaly가 발생할 수 있다.

2. LRU (Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 제거하는 방식이다. 최근에 사용되지 않았다면 앞으로도 사용될 가능성이 낮다는 가정에 기반한다.

현실에서 널리 사용되며 Optimal에 가까운 성능을 보이지만, 시간 정보를 관리해야 하므로 구현 비용이 크다는 단점이 있다.

3. Optimal Page Replacement (이 문제에서 쓰이는 것)

앞으로 가장 늦게 사용될 페이지를 제거하는 방식으로, 이론적으로 가장 좋은 성능을 보인다. 하지만 실제 시스템에서는 미래의 접근 패턴을 알 수 없기 때문에 구현이 불가능하다.

다른 알고리즘들의 성능을 비교하는 기준으로 사용된다.

4. LFU (Least Frequently Used)

사용 횟수가 가장 적은 페이지를 제거하는 방식이다.
하지만 과거에 많이 사용되었다고 해서 앞으로도 사용된다는 보장이 없고, 오래된 사용 기록이 계속 영향을 주는 문제가 있다.

5. Second Chance (Clock)

FIFO를 개선한 방식으로, 최근에 사용된 페이지에 한 번 더 기회를 준다.
reference bit를 이용해 최근 사용 여부를 판단하며, LRU를 단순하게 근사한 알고리즘이다.

6. NRU (Not Recently Used)

reference bit와 modified bit를 기준으로 페이지를 분류하여 제거하는 방식이다. 최근 사용되지 않았고 수정되지 않은 페이지를 우선적으로 제거한다.

구현은 간단하지만 정확도는 낮은 편이다.

---

이중 유일하게 미래를 기반으로 선택하는 것은 Optimal Page Replacement 방식이다. 이론적으로는 미래의 올것들을 다 계산해놓고 교체하는 것이기에 최소 교체 횟수를 이룰 수 있다. 하지만 현실에서는 미래에 어떤 page를 정확히 필요로 할지 모르기 때문에 적용될 일은 거의 없다. 하지만 이 문제는 미래에 어떤 전기용품이 올지 알기 때문에 Optimal Page Replacement로 완벽한 최소 교체 횟수를 구할 수 있다. 정답 코드는 아래와 같다.

public class Main {

    static int N, K, ret;
    static int[] arr;
    static Set<Integer> plug;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 멀티탭 개수
        K = Integer.parseInt(st.nextToken()); // 사용 횟수

        arr = new int[K];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        plug = new HashSet<>();

        for (int i = 0; i < K; i++) {
            int now = arr[i];

            // 꽃혀있으면 넘어가기
            if (plug.contains(now)) {
                continue;
            }

            // 콘센트 비어 있으면 꽃기
            if (plug.size() < N) {
                plug.add(now);
                continue;
            }

            // 꽉 찼을때 하나 뺴야함.
            int target = -1; // 뽑을놈
            int pos = -1;

            for (int p : plug) {
                int nextUse = Integer.MAX_VALUE;

                // 뽑혀있는 애들중 다음에 나오는 것들 찾기
                for (int j = i + 1; j < K; j++) {
                    if (arr[j] == p) {
                        nextUse = j;
                        break;
                    }
                }

                // 뽑혀있는 애들중 다음에 나오는 것중 가장 뒤에 있는 것 뽑자 -> Optimal Page Replacement
                if (nextUse > pos) {
                    pos = nextUse;
                    target = p;
                }
            }

            plug.remove(target);
            plug.add(now);
            ret++;
        }

        System.out.println(ret);
    }
}

마무리하며

이 문제는 아이디어 떠올리는 것도 어려웠고, 그 유명한 알고리즘도 구현하는 거 자체도 어려웠던 문제이다. 이참에 Page Replacement 알고리즘에 대해 정리할 수 있어서 좋았다. 이러한 유명 알고리즘들은 알고 있어야 하지 않겠는가!

그리고 그리디 알고리즘 문제 특성상 굉장히 자주 쓰일 것 같은 아이디어다! 잘 익혀서 앞으로도 그리디하게 써먹자~

파이팅 🔥