시작 전에...
알고리즘 공부를 하면서 제가 보기 위해 정리한 글입니다.
본 글은 아래 링크를 참조하여 작성되었습니다.
[알고리즘] 탐욕 알고리즘(Greedy Algorithm)
그리디 알고리즘이란?
그리디, 즉 Greedy는 탐욕을 의미한다. 그리디 알고리즘은 말 그대로 순간마다 최선의 선택을 함으로써 해답에 도달하는 방식이다.
순간마다 하는 선택은 각 상황에 최선임이 보장되지만 최종 답이 최선이라는 보장은 없다. 하지만 그리디로 풀 수 있는 문제들은 이 최종 답 또한 최선이 되는 문제들이다.
그리디 알고리즘의 조건
01 탐욕적 선택 속성(Greedy Choice Property)
앞의 선택이 이후의 선택에 영향을 주지 않는다.
02 최적 부분 구조(Optimal Substructure)
문제에 대한 최종 해결 방법은 부분적인 문제들에 대한 최적의 문제 해결 방법으로 구성된다.
다만 이러한 조건을 만족하지 않아도 그리디 알고리즘을 근사 알고리즘으로 충분히 활용할 수 있는 경우가 있다.
또한 위 조건을 갖춘 구조를 매트로이드라 하는데, 이 구조를 가진 문제에 대해서는 그리디 알고리즘이 언제나 최적해를 찾아낼 수 있다.
예제. 보물(백준 1026번)
문제
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.
출력
첫째 줄에 S의 최솟값을 출력한다.
예제 입력
5
1 1 1 6 0
2 7 8 3 1
예제 출력
18
풀이
s를 최소로 하려면 가장 작은 수와 가장 큰 수를 곱해서 더해야 한다. 따라서 A 배열을 오름차순으로, B 배열을 내림차순으로 정렬(물론 반대로 해도 된다)해서 각 원소를 곱해서 더해주면 된다. 문제에서 B는 재배열할 수 없다고 했지만, 저렇게 해도 항상 두 원소가 대응될 수 있으므로 상관 없다.
코드
n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
a=sorted(a)
b=sorted(b, reverse=True)
s=0
for i in range(n):
s+=a[i]*b[i]
print(s)마치며...
방학 중 알고리즘 공부를 하겠다던 야심찬 계획은 어디 갔는지 모르겠다. 그래도 정리하면서 문제 풀면 좀 더 오래 가지 않을까 싶어 벨로그를 시작하게 되었다.
질문은 (저도 잘 모르지만) 아래 남겨주시면 최대한 답변 드리겠습니다. 모두 파이팅 :P
