그리디(탐욕) 알고리즘에 대한 정리 - 세기무민

 

안녕하세요

세기무민입니다.

이번 포스팅에서는 그리디 알고리즘에 대해 다뤄보도록 하겠습니다.

---

Greedy? 탐욕?

우선 그리디 알고리즘은 탐욕 알고리즘이라고도 말합니다. 

그리디 알고리즘에서 가장 중요하게 생각하는 포인트는 

"현재 선택지 중 가장 좋은(최적)의 방법을 선택하는 것"

그리디 알고리즘에 대한 가장 좋은 예시는 최단거리를 구하는 것이다.

아래의 그림으로 설명해보면

시작 지점으로부터 끝지점까지 최단거리를 구해보도록 하자. 

시작 지점에서 4로 시작하는 경우 2가지의 경우의 수가 만들어지며 20, 23의 거리를 가진다.

시작 지점에서 4보다 큰 6으로 시작했을 경우 19의 거리를 가지게 되고 

최종적으로 가장 짧은 거리를 가지게 된다. 

즉 그리디 알고리즘은 여러개 중 한개를 선택해야 할 경우

그 순간에 가장 최선이라고 생각되는 것을 선택하여 결과를 도출하는 알고리즘이다. 

백준 알고리즘 예시(AMT 문제)

위의 내용처럼 시간의 합의 최소값을 구하는 방법에 대해 구하는 문제인데 

위의 문제도 그리디 문제 중 하나이다. 

결국 이 문제를 푸는 방법은 가장 최소의 값부터 나열하게 된다면 

가장 최소의 값을 구할 수 있게 된다. 

[코드]

n = int(input())
count = 0
time = 0

arr = list(map(int, input().split()))

arr.sort()

for i in arr:
  count += i + time
  time += i

print(count)

코드는 위와 같이 가장 정렬을 통해 최소값부터 나열한 뒤 시간을 더해주면 되는 문제이다. 

 

마치며

그리디 알고리즘의 경우 순간마다 최적의 값을 구하는 것이 중요하지만 

최종적인 선택에서는 최적의 해가 아닐수도 있다는 생각이 들었습니다.

다음 포스팅에서는 다른 알고리즘 이론으로 찾아오도록 하겠습니다.