[그리디(Greedy)] 큰 수의 법칙

참고

클릭하시면 위 이미지에 보이는 링크로 이동합니다.

---

1.목적

• 알고리즘 서적인 '이것이 코딩 테스트다'의 그리디(탐욕법) 중 '큰 수의 법칙' 문제에 대한 이해를 하기 위해 해당 글을 작성하였다.

---

2.개요

'큰 수의 법칙' 이란 대수의 법칙, 라플라스의 정리 라고도 하며 엄청 큰 모집단에서 무작위로 뽑은 표본의 평균이 전체 모집단의 평균과 가까울 가능성이 높다는 통계와 확률 분야의 개념

해당 이론에 대해 통계학에 대한 전체적인 기반이 있어야 이해할 수 있는 영역이지만 그리디 문제 중 큰 수의 법칙은 한 구간에서 반복되는 수열의 규칙을 찾아내는게 핵심이다. 이 법칙에 대해 깊게 파고들지 않아도 되며, 그리디 중 큰 수의 법칙 문제는 한 구간에서 반복되는 수열의 규칙을 찾아내는게 핵심이다.

---

3.문제

'큰 수의 법칙'은 일반적으로 통계 분야에서 다루는 개념이지만 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 m번 더해서 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 k번 초과해서 더해질 수 없는 것이 해당 법칙의 특징이다.

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 m이 8이고, k가 3이라고 가정하자. 이 경우에 특정한 인덱스 수가 연속해서 3(k = 3)번 더해질 수 있다. 그리고 결국 8(m = 8)번 더한 결과로 가장 큰 수를 만들어야 되기 때문에 가장 큰 수를 추출해야되는 큰 수를 추출해야 한다. 따라서 큰 수의 법칙에 따른 결과 다음과 같은 수가 나온다.

6 + 6 + 6 + 5 + 6 + 6 + 5 = 46

만약 서로 다른 인덱스에 해당하는 수가 같은 경우 서로 다른 것으로 간주한다. 배열 3, 4, 3, 4, 3이 있고, m이 7, k가 2라면 다음과 같이 추출된다.

(4 + 4) + 4 + (4 + 4) + 4 + (4) = 28

• 입력 조건
  • 첫째 줄에 n, m, k의 자연수가 주어지며 각 자연수는 공백으로 구분한다.
  • 둘째 줄에 n개의 자연수가 주어진다. 각 자연수는 공백으로 구분합니다. 단, 각각의 자연수는 1 이상 10,000 이하의 수로 떨어진다.
  • 입력으로 주어지는 k(특정 인덱스 반복 가능 횟수)는 m(총 더하는 횟수)보다 작거나 같다 (k <= m)

---

4.답안

4-1.단순 답안

n, m, k = map(int, input().split()) # 첫째 줄에 n, m, k 자연수를 공백을 통해 입력
array_lst = list(map(int, input().split())) # 둘째 줄에 n만큼의 원소를 가진 리스트 공백으로 생성
array_lst.sort(reverse=False) # 리스트의 원소를 오름차순 리스트의 sort() 와 reverse 파라미터
biggest_number = array_lst[n - 1] # 제일 큰 수 초기화 및 값 대입
second_big_number = array_lst[n - 2] # 두번째로 큰 수 초기화 및 값 대입 

result = 0

''' 해당 문제에서의 핵심 구문. nested loop와 break를 이용하여 가장 큰 수를 k번 더하고, 두번 째로 큰 수를 한번 더하게 만듭니다. '''
while True : # 무한 루프 
    for i in range(k) : # 가장 큰 수를 k만큼 더하기 위해 for 루프 반복 
        if m == 0 : # 만약 총 더해지는 수가 
            break
        result += biggest_number # 큰 수를 for 루프만큼 더함 
        m -= 1 # 총 더해지는 수를 차감하여 0이 되면 루프를 나오게 하기 위해 m - 1을 함
    if m == 0 : # m이 0이라면 반복문 탈출
        break 
    result += second_big_number # 두 번째로 큰 수를 더한다. 
    m -= 1 # 총 더해지는 수를 차감하여 0이 되면 루프를 나오게 하기 위해 m - 1을 함

print(result) 

위와 같이 시간 복잡도를 생각하지 않고, 단순하게 생각한다면 무한루프를 돌리고 해당 구문 안에 for 문을 돌려 가장 큰 수를 k 번 더하도록 만든다.

그 다음 두번째로 큰 수를 한번 더해준다.

만약 m번 만큼의 원소 수행을 끝냈다면 해당 프로그램을 종료한다. 그러기 위해 break 문을 사용한다.

정말 좋은 방법 중 하나지만 반복문이 있다면 시간 복잡도가 커져 효율적이지 못 할 것이다. 그래서 다음과 같은 방법을 사용한다.

4-2.시간 복잡도를 고려한 답안

n, m, k = map(int, input().split()) # 첫째 줄에 n, m, k 자연수를 공백을 통해 입력
array_lst = list(map(int, input().split())) # 둘째 줄에 n만큼의 원소를 가진 리스트 공백으로 생성

array_lst.sort(reverse=False) # 리스트의 원소를 오름차순 리스트의 sort() 와 reverse 파라미터
biggest_number = array_lst[n - 1] # 제일 큰 수 초기화 및 값 대입
second_big_number = array_lst[n - 2] # 두번째로 큰 수 초기화 및 값 대입 

biggest_number_count = 0 # 가장 큰 수가 더해지는 카운트를 세는 변수 초기화 

if m % (k + 1) == 0 : # 만약 수열의 반복되는 횟수가 딱 떨어진다면?!
# 수열의 반복되는 횟수 * 한 수열에서 제일 큰 수가 반복적으로 더해지는 횟수 = 모든 수열 구간에서 가장 큰 수가 더해지는 횟수가 나옴
    biggest_number_count = (m // (k + 1)) * k 
else : # 그렇지 않다면(수열의 반복되는 횟수가 딱 떨어지지 않는다면?!)
    # 모든 수열 구간에서 가장 큰 수가 더해지는 횟수 + 짤려진 수열의 더해지는 큰 수 
    biggest_number_count = ((m // (k + 1)) * k) + (m % (k + 1)) 

# 총 더해지는 횟수를 result로 선언 및 0 할당
result = 0
result += (biggest_number_count * biggest_number)

second_number_count = (m - biggest_number_count)
result = second_number_count * second_big_number

print(result)

반복되는 수열에 대한 파악이 중요하다.
- 한 덩어리의 수열이 어떠한 원소 구조를 가지고 있는가?
- 한 패턴으로 구현된 수열이 총 몇개 있는가?

즉, 한 구간의 수열은 다음과 같은 구조를 가지고 있다.

n개의 리스트 원소 중 가장 큰 피연산자는 k개 만큼 있을 것 이며, 이후 두 번째로 큰 피연산자가 1개 있을 것이다.

반복되는 수열의 길이(len) 공식 = (k + 1)

또한 모든 피연산자는 m개 만큼 있으며, 이것을 (k + 1) 만큼 나눈 몫은 한 패턴으로 구현된 수열의 갯수가 나올 것이다.

수열이 반복되는 횟수 공식 = m // (k + 1)

마지막으로 수열이 반복되는 횟수에 가장 큰 피연산자의 횟수 k를 곱하면 가장 큰 피연산자의 모든 수를 출력 할 것이다.

가장 큰 피연산자가 더해지는 횟수 = m // (k + 1) * k

하지만 이런 경우도 생각해 볼 수 있다. 만약에 수열이 반복되는 횟수(m // (k + 1))가 딱 떨어지지 않는다면 어떡하지? 이럴 경우 m % (k + 1)의 나머지가 있을 것이며, 이 나머지는 마지막에 있는 반복되 수열에서 짤린만큼의 수열 패턴으로 구현 될 것이다.

ex ) n = 4 이며, 배열 = [3, 2, 4, 7], k = 3, m = 6 이라고 한다면??
| 7 | 7 | 7 | 4 |

| 7 | 7 |

이런 형태로 구현 될 수 있을 것이다.

가장 큰 피연산자가 더해지는 횟수(수열이 반복되는 횟수가 딱 떨어지지 않을 경우) = (m // (k + 1)) * k + (m % k + 1)

---

5.해당 문제를 분석 후 의문점

greedy 문제들은 무수히 많은 유형이 있기 때문에 머리를 굴려 아이디어를 도출해야 된다고 알고 있다. 이러한 문제를 분석하고 이에 맞게 패턴화하여 내 머릿속에 집어 넣으며 공부를 하면 정말 실전에서 맞출 수 있을지 의문이다.

일단은 더 열심히 분석하고 문법 공부에 열중하여 잔디 심기와 글들을 꾸준히 올려야 될 것 같다.