[Condingame] SUPER COMPUTER(가장 효율적인 스케쥴-탐욕 알고리즘)

문제 간략 설명: 데이터 센터에 슈퍼컴퓨터를 새로 들였습니다. 데이터 센터의 연구자는 모두 슈퍼컴퓨터를 이용하여 본인의 연구를 수행하길 원합니다. 최대한 많은 연구자의 요청을 충족시키기 위하여 슈퍼컴퓨터의 효율을 극대화해야 합니다.

여러분은 컴퓨터가 쉬는 시간 없이 최대한 많은 작업을 수행하도록 스케줄을 조정하는 프로그램을 작성해야 합니다.

[사진]

[Rules_규칙]

목표: 과학자들이 사용할 수 있는 슈퍼컴퓨터 사용 계획을 세우기 위해, 과학자들이 필요로 하는 연구 일정을 고려하여 가능한 최대한 많은 연구를 처리할 수 있는 방법을 찾는다.

 

규칙: 

• N개의 계산이 주어진다.
• 시작일과 연구 일수로 주어진다. 시작일과 연구 일수가 주어진다. 시작일부터 종료일(시작일+연구 일수-1)까지 해당 계산을 위해 슈퍼컴퓨터를 사용해야 한다.
• 서로 다른 계산은 동시에 처리할 수 없으므로, 겹치는 계산 기간이 있다면 하나의 계산만 선택 가능하다.
• 가능한 한 많은 계산을 처리하려고 한다.
• 최종적으로 선택된 계산의 수를 출력해야 한다.

[문제]

 

https://www.codingame.com/training/hard/super-computer

Practice Greedy algorithms and Scheduling with the exercise "Super Computer"

 

[난이도]

[학습 개념]

[풀이]

문제를 풀기 전에 생각을 해야 했습니다.

어떻게 이 많은 연구 과제들 중 최선의 연구 과제를 선택하여 다른 연구기간과 겹치지 않는 가장 많은 연구를 할 수 있는지 생각해봐야 합니다.

주어진 조건은 시작일, 연구일 수, 그리고 이 두 개를 계산한 연구 종료일입니다.

이 3가지 중 하나가 선택 기준이 최선의 연구 과제를 선택하는 기준이 될 겁니다.

• 연구 시작일이 가장 빠른 과제부터 선택
• 연구 기간이 가장 짧은 과제부터 선택
• 연구 종료일이 가장 빠른 과제부터 선택

그럼 하나하나 아래 표를 보면서 소거법으로 제거해 보겠습니다.

[표1]연구 기간을 한눈에 보기 쉽게한 표

1. 먼저 연구 시작일이 가장 빠른 과제부터 선택하면 D와 B를 비교해 보겠습니다.

지금도 연구 시작일은 같지만 B 때문에 D와 C를 할 수 있는데 못할 수 있습니다.

거기다 B의 시작일이 8부터 시작한다면 더더욱 시작일이 가장 빠른 과제부터 선택하면 안 될 거 같습니다.

이 조건은 제거됩니다.

 

2. 연구 기간이 가장 짧은 과제부터 선택한다고 생각해 보겠습니다.

[표2]

표 2를 보면 이 조건으로 결정하면 안 된다는 게 한눈에 보입니다. B 하나 때문에 E C가 안되기 때문입니다.

 

3. 마지막으로 연구 종료일이 가장 빠른 과제부터 선택하는 것입니다.

연구를 빨리 끝낼수록 새로운 연구를 바로 수행할 수 있기 때문에 이는 올바른 선택 기준이 됩니다.

표 1을 봐도 D를 선택하고 기간이 겹치는 B를 제외되므로 그다음 선택은 C가 됩니다.

표 2를 봐도 A를 선택하면 D가 제외되고 E를 선택하면 B가 제외되고 그다음 선택은 C가 되므로 정답은 3이 됩니다. 

 

[정답 소스 코드]

 

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

class Solution
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        var periodLists = new List<(int startDay, int endDay)>(); // ValueTuple 자료구조
        for (int i = 0; i < N; i++)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int startDay = int.Parse(inputs[0]); // 연구 시작일
            int duration = int.Parse(inputs[1]); // 연구 기간
            int endDay = startDay + duration - 1; // 연구 종료일

            periodLists.Add((startDay, endDay)); // 연구기간 리스트에 저장
        }
        //과제 종료일이 가장 빠른 것부터 처리하기 위해 정렬함
        periodLists = periodLists.OrderBy(x => x.endDay).ToList();
        foreach (var period in periodLists)
        {
            Console.Error.WriteLine(period);
        }
        int maxCount = 0;
        int currentEndDay = -1; // 마지막으로 선택한 연구 종료일
        foreach (var period in periodLists)
        {
            // 기간이 겹치지 않는 경우
            if (period.startDay > currentEndDay)
            {
                maxCount++;
                currentEndDay = period.endDay;
            }
        }
        Console.WriteLine(maxCount);
    }
}

 

[아쉬웠던 점]

제가 실은 처음에 짠 코드는 이게 아닙니다. 처음은 아래 코드를 만들었습니다.

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

//풀이 방법: 종료일이 가장 빠른걸 선택하고 기간이 중복되는건 제거한다
class Solution2
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        var periodLists = new List<(int startDay, int endDay)>(); // ValueTuple 자료구조
        for (int i = 0; i < N; i++)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int startDay = int.Parse(inputs[0]); // 연구 시작일
            int duration = int.Parse(inputs[1]); // 연구 기간
            int endDay = startDay + duration - 1; // 연구 종료일

            periodLists.Add((startDay, endDay)); // 연구기간 리스트에 저장
        }
        //과제 종료일이 가장 빠른 것부터 처리하기 위해 정렬함
        periodLists = periodLists.OrderBy(x => x.endDay).ToList();
        foreach (var period in periodLists)
        {
            Console.Error.WriteLine(period);
        }
        //리스트 요소가 남아있는 동안
        for (int i = 0; i < periodLists.Count; i++)
        {
            var currentPeriod = periodLists[i];
            //period는 리스트의 각 요소를 나타내는 변수. 그러므로 첫번째 요소와 기간이 겹치는 모든 요소를 제거한다. 현재 요소는 제거하지 않는다.
            periodLists.RemoveAll(period => period.startDay <= currentPeriod.endDay && period.endDay >= currentPeriod.startDay && period != currentPeriod);
        }
        Console.WriteLine(periodLists.Count);
    }
}

위 코드에서는 리스트의 각 요소를 제거할 때 RemoveAll 메서드를 사용하고 있습니다. 이 메서드는 리스트 내에서 조건을 만족하는 모든 요소를 제거합니다. 따라서, 조건에 맞는 모든 요소를 찾기 위해서는 모든 요소를 확인해야 하므로, 시간 복잡도가 O(N^2)이 됩니다. 그렇기에 많은 데이터를 다루기에 적합하지 못해 테스트 케이스를 통과하지 못했습니다.

 

모든 요소를 확인할 필요 없이 정렬되어 있으므로 현재 요소의 +1의 시작일을 가진 요소를 선택하는 과정만 반복했어도 충분했을 텐데 모든 요소를 현재 요소와 일일이 확인 후 제거하는 방법을 써서 오히려 더 복잡해진 거 같아서 아쉽습니다.

 

 

[새롭게 알게 된 점]

1. ValueTuple 자료구조에 대해 새롭게 알게 되고 공부가 되었다. 더 이상 인자가 두 개 이상의 제네릭 함수를 만들기 위해 클래스나 구조체를 안 만들고 빠르게 할 수 있을 거 같다.

2. 좀 더 성능을 개선하는 방법에 대해 생각하게 되었다

3. 문제를 푸는 조건을 따져서 탐욕 알고리즘에 대해 좀 더 공부가 되었다.

 

2023.05.09 - [알고리즘 공부/codingame 사이트 문제] - [Condingame] THE GIFT(돈을 나누는 가장 공평한 방식-탐욕 알고리즘)

[Condingame] THE GIFT(돈을 나누는 가장 공평한 방식-탐욕 알고리즘)

이 글도 보는거 추천