[알고리즘 공부] 그리디(Greedy)

Greedy 알고리즘 풀이

 

 2024년 상반기 공고가 시작되었습니다. 그간 작년 12월부터 2월 말까지 대외 활동을 하느니라, 미뤄왔던 코딩 테스트 준비를 위한 알고리즘 공부를 부랴 부랴 다시 시작합니다. 이전과 다른 점은 이제 하고자 하는 의지(?)가 있는 친구들과 함께 준비하기 때문에 이제 자의 반, 타의 반으로 코딩 테스트 공부를 함께 준비할 수 있게 되었습니다. 그래서 이전에 Greedy 알고리즘에 이어서 다시 블로그 글을 작성해봅니다. 

 

• 참고 : 이코테 (이것이 취업을 위한 코딩 테스트다. with 파이썬)
• 사용 프로그래밍 언어 : Python

 

---

문제 유형 : Greedy

 

 시간이 많이 지나갔기 때문에 복습도 할 겸, 그리디 유형에 대해서 살펴보도록하겠습니다. 그리디 알고리즘은 해석하면 "탐욕스러운" 방법으로 문제를 해결하는 방식이라고 말할 수 있는 데, 이를 간단히 말하면 매 순간 가장 좋아보이는 선택을 바로 하여 문제를 해결해 나가는 방법이라고 말할 수 있습니다. 

 

 이를 예를 들면 "사탕을 최대한 많이 가져가고 싶을 때, 매번 가장 큰 사탕을 선택하는 것"이 그리디 알고리즘의 접근 방식입니다. 매 순간 최선의 결정을 내려서 최종적으로 많은 사탕을 가져가게 되는 것입니다. 

 

 또 하나의 예시를 들면 "가장 가까운 이웃" 규칙을 사용하는 것입니다. 예를 들어, 세일즈맨은 현재 도시에 가장 가까운 도시로 이동하고, 이 과정을 모든 도시를 방문할 때까지 반복합니다. 이 과정에서 세일즈맨은 다음으로 이동할 최단 거리의 도시를 선택하는 것입니다. 

 

---

문제 풀이 : 큰 수의 법칙

 

 <이코테> 과정에 따라서 오늘은 "큰 수의 법칙"에 대해서 설명하도록 하겠습니다. "큰 수의 법칙"은 일반적으로 통계 분야에서 다루어지는 내용이지만, 책에서는 저자만의 방식으로 사용하는 것을 확인할 수 있습니다. 문제를 제가 정확하게 밝힐 수 는 없기 때문에 간단히 설명드리면, 다양한 수로 이루어진 배열이 잇을 떄 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙입니다. 

 

그럼, <이코테> 문제를 보고 풀어낸 코드를 통해서 확인하도록 하겠습니다. 

입력 예시 

5 8 3
2 4 5 4 6

답 :46

# 사용자로부터 세 개의 정수 N, M, K를 입력받습니다. 
# 여기서 N은 배열의 크기, M은 더하는 횟수, K는 최대 연속해서 더할 수 있는 횟수를 의미
n, m, k = map(int, input().split())

# 사용자로부터 N개의 정수를 배열로 입력받는 LIST
data = list(map(int, input().split()))

# print(data)

data.sort() # 리스트 정렬
first = data[n-1] # 가장 큰수
second = data[n-2] # 두 번째로 큰수


result = 0
while True :
	# k번 만큼 연속적으로 더하기
    for i in range(k):
        if m == 0:
            break
        result += first
        m -= 1
    if m ==0:
        break
    result += second
    m -=1

print(result)

 

 위 방식대로 하면 m의 크기가 엄청 커지면 시간 초과 판정을 받을 수 있기 때문에 반복되는 수열의 규칙을 찾아 그것을 활용하는 것을 추천드립니다. 다음 코드에서는 특정 수열 규칙를 활용한 코드를 보여드리도록 하겠습니다.

 

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[n - 1]  # 가장 큰 수
second = data[n - 2]  # 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = (m // (k + 1)) * k
count += m % (k + 1)

result = 0
result += count * first  # 가장 큰 수 더하기
result += (m - count) * second  # 두 번째로 큰 수 더하기

print(result)

 

 위 코드를 이해하기 위한 예시로 첫 번째 코드에서는 {6, 6, 6 ,5}가 반복된다는 사실을 알 수 있습니다. 여기서 count = (m // (k + 1)) * k + m % (k + 1)은 가장 큰수가 더해지는 총 횟수를 계산합니다. 전체 더하는 횟수 m을 k+1로 나눈 몫에 k를 곱하고 여기에 m을 k+1로 나눈 나머지를 더해줍니다. 이는 가장 큰 수와 두 번째로 큰 수가 이루는 패턴이 k+1 길이를 가지기 때문입니다. 

 

 

 

마무리

 오랜만에 코딩 TEST를 공부하려고 하니깐, 파이썬도 많이 잊고 그리디 과정도 기억이 가물가물했습니다. 하지만 포기하지 않고 조금씩 계속 수행하다보면 저도 언젠간 코테 마스터가 되는 날이 오겠지요? 다가오는 그 날과 코딩 테스트에서 무너지지 않는 날들을 기대하면서 오늘 코테 공부는 여기서 마치도록 하겠습니다.

 

 

참 고

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

[코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬