[그리디 알고리즘] 큰 수의 법칙

그리디 알고리즘에 대한 소개

문제 풀이에 앞서 그리디 알고리즘을 간단하게 짚고 넘어가보자.
그리디 알고리즘은 비교적 간단하고 자주 사용되는 알고리즘이다.
이 알고리즘은 특정한 조건 내에서 가능한 가장 좋은 해를 찾기 위해 매번 다른 값을 시도해 보는 방식으로 접근한다.
일반적으로 시간 및 공간 복잡도가 낮아 효율적인 솔루션을 제공한다.

그리디 알고리즘의 종류

일반적으로는 최적 분할 문제, 최대 값 문제 및 최소 값 문제에 적용할 수 있다. 이 외에도 다양한 다른 문제에 대해 그리디 알고리즘을 사용할 수 있다.

예시 문제

예를 들어 다음과 같은 숫자 배열이 있다고 가정해보자 [2, 3, 7, 8, 10]
여기에서 주어진 숫자들을 사용하여 최대 합을 가지는 부분 집합을 찾는 문제를 해결하고자 한다.
이 때 그리디 알고리즘이 적용되는데, 숫자가 적어도 하나 이상 포함되는 부분 집합을 구하기 위해 다음과 같은 과정을 따른다.

1. 첫 번째 원소를 선택한다.
2. 다음 원소를 선택하고 지금까지 선택한 원소의 합과 비교한다.
3. 두 숫자 중 더 큰 값을 선택한다.

결론

그리디 알고리즘은 비교적 간단하고 자주 사용되는 알고리즘이다.
가장 큰 장점은 시간 및 공간 복잡도가 낮아 효율적인 해를 찾는 것!

즉 모든 문제는 완전탐색으로 풀 수 있지만,
이 알고리즘을 채택한다면 더 빠르게 풀 수 있다!

하지만 이 알고리즘을 사용하기 전에 이 방법이 정말 맞는지 판별하기가 어렵기 때문에
꽤 어려운 알고리즘이다.

[문제] 큰 수의 법칙

입력받은 배열을 사용하여 가장 큰 수를 만드는 문제이다.

1. N개의 자연수를 가진 배열은 정렬되어있지 않고
2. 총 M번 더할 수 있으며
3. 하나의 인덱스 당 K번 초과하여 더할 수 없다.

입력 조건

• 첫째 줄에 N(2 <= N <= 1,000), M(2 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며,각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

• 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

풀이

1. 입력받은 배열을 정렬한다.
2. 맨 마지막에 있는 수(가장 큰 수)를 K번 더한다.
3. K를 초과할 때 두번째로 큰 수를 한번 더하고 count를 초기화 한다.
4. 2,3번을 M번 반복한다.

코드

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
var (N, M, K) = (input[0], input[1], input[2])
var array = readLine()!.split(separator: " ").map{ Int(String($0))! }

array.sort()
let first = array[N - 1] // 가장 큰 수
let second  = array[N - 2] // 두번째로 큰 수

var result = 0
var count = 1

for _ in 0 ..< M {
    if count <= K {
        result += first
        count += 1
    } else {
        result += second
        count = 1
    }
}

print(result)