Greedy Algorithm - 11399

백준 온라인 코딩 문제풀이

https://www.acmicpc.net/

Baekjoon Online Judge

---

11399번 - ATM 문제

 

 

우선 알고리즘 방식이 Greedy Algorithm(탐욕 알고리즘)으로 기재가 되어있다.

 

따라서 우선 탐욕 알고리즘이 무엇인지부터 정리해보았다.

 

탐욕 알고리즘

- 현재 상황에서 가장 최적이라고 생각되는 선택을 반복적으로 수행

- 즉, 미래를 고려하지 않고 매 순간 최선의 선택을 하는 방식

 

특징

탐욕 선택 속성 (Greedy Choice Property)
- 현재의 선택이 이후의 결과에 영향을 미치지 않아야 한다.

최적 부분 구조 (Optimal Substructure)
- 문제를 작은 부분 문제로 나눌 수 있으며, 각 부분 문제의 최적해를 결합하여 전체 문제의 최적해를 구할 수 있어야 한다.(DP와 같은 특징)

 

장점
1. 구현이 간단하고 빠르다.
2. 복잡한 문제에서도 근사값을 빠르게 구할 수 있다.
3. 특정 조건을 만족하는 문제에서는 최적해를 보장한다.

 

단점

1. 항상 최적해를 보장하지는 않는다. 일부 문제에서는 오히려 잘못된 해답을 도출할 수 있다.
2. 이전 선택을 되돌릴 수 없기 때문에 동적 프로그래밍(DP)보다 유연성이 낮다.

 

대표적인 활용 사례

1. 동전 거스름돈 문제
2. 최소 신장 트리 (예: 크루스칼 알고리즘)
3. 활동 선택 문제
4. 허프만 코딩 (데이터 압축)

 

여기까지 탐욕 알고리즘이 무엇인지와 특징과 장단점, 활용 사례를 대충 살펴보았다.

 

우선 문제에서 "시간의 합이 제일 작게 만들어라"라는 문구를 보고 생각이 난대로 구현을 해보았다.

 

내가 생각한 것에 대해 적어보도록 하겠다.

1. 시간의 최소 합이 되려면 결국 앞에서 쌓이는 시간이 최소여야한다.(그때그때 선택한 것이 탐욕 알고리즘처럼 최선의 선택이어야 한다)

2. 그런데 굳이 탐욕 알고리즘이 필요한가?(어차피 그때그때 최소값을 찾아서 구현하던지 미리 정렬하던지 시간 복잡도가 비슷할거 같다)

 

따라서 시간 복잡도에 관해서 찾아보았다.

보통의 경우에는 Math.Min의 경우가 시간 복잡도가 상수로 성능이 좋지만 우리의 경우 Array의 메소드인 Min을 사용하기 때문에 이 경우에서 시간 복잡도를 추가로 찾아보았다. 

Array의 Min 메소드를 사용하는 경우 시간 복잡도가 O(n)으로 올라가게 된다.

 

O(nlogn)과 O(n)의 경우 시간 복잡도의 차이가 있다.

하지만 우리는 루프를 통해 최소값을 하나씩 빼면서 계속 추출해내야 한다.

따라서 어느쪽으로 구현하든 시간 복잡도의 차이가 거의 없을 것으로 판단하였다.

 

Array.sort하는 방식으로 구현을 해보겠다.

 

구현

 

using System;
using System.Linq;
//using System.Collections.Generic;
namespace StudyCS
{
    class Program
    {
        public static void Main(string[] args)
        {
            int personNum = int.Parse(Console.ReadLine());
            int[] timeArray = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            Console.WriteLine(TimeCal(timeArray));
        }
        public static int TimeCal(int[] _time)
        {
            Array.Sort(_time);
            int[] waitTime = new int[_time.Length];
            for (int i = 0; i < _time.Length; i++)
            {
                if (i == 0) waitTime[i] = _time[i];
                else waitTime[i] += waitTime[i-1] + _time[i];
            }
            return waitTime.Sum();
        }
    }
}

구현 방식은 위에서 말한것처럼 그냥 입력을 받은 후 Array.Sort 메소드를 이용하여 정렬하고 시간을 앞에서부터 차근차근 쌓아 배열에 저장하게 하였다.

 

시간의 여유가 없다면 다른 방식으로 구현했겠지만 문제 없이 통과되었다.