[CS] 알고리즘 - 그리디

1. 그리디 알고리즘 이란?

• 현재 상황에서 지금 당장좋은 것만 고르는 방법
• 단순히 가장 좋아 보이는 것만 반복적으로 선택해도 최적의 해를 구할 수있는지 검토
• 예: 루트 노드부터 시작해 거쳐가는 노드의 값을 최대로 하고 싶은경우

→ 단순히 매 상황에서 가장 큰 값만 고르는 방식

• 일반적인 상황에서 최적의해를 보장할 수 없을 때가 많다

<예시: 거스름돈 문제>

- 500 100 50 10 → N

• 가장 큰 화폐부터 돈을 거슬러준다
• ⇒ 최적의 해를 보장하는 이유는?
• ⇒ 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가나올 수 없기 때문!
• 500, 400, 100원인 경우 500원이 400원의 배수가 아니므로 다른 해법이 나올 수 이다.
• 화폐의 종류가 K라고 할때, 소스코드의 시간 복잡도는 O(K)
• 이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다

2. 연습문제

 

(1) 큰 수의 법칙

1. input()은 한 번에한줄만 읽어들인다.
condition, array = input().split("\n")는 잘못된 풀이!
2. map(int, input().split()) 으로 int로 바꿔주지 않으면 문자열이라서, 정렬 시 의도하지 않은대로 정렬 될 수 있음
3. 공백을 기준으로 분리할 때는 split(" ")을 명시하지 않고 split()으로 사용 가능
4. 해당 배열을 더 이상 사용할 일이 없다면 sorted를 쓸 경우 메모리가 불필요하게 사용 될 수 있어 sort를 사용!
5. 각 단계에서 최선의 선택이 누적(가장 큰 수 또는 두번재로 큰 수를 선택)되어 전체 합을 최대로 만드는 해를 구하는 문제이므로 그리디 문제이다!

 

(2) 숫자 카드 게임
1. 모든 행의 최솟값을 저장했다가 한 번에 최댓값을 계산하고 있는데, 행이 많아질수록 메모리 사용량이 증가한다.
2. 최소값만 저장하면 메모리사용량을 아낄수 있다
 중간 결과를 저장할필요 없이 바로 처리할 수 있다.
3. min 함수도 내부적으로 모든 원소를 한 번씩 순회하며 비교하기 때문에 for문이랑 같은 수의 비교 연산을 수행한다.
4. iterator는 데이터를 한 번에 하나씩만 일고, 읽은 데이터를 처리하고 나면 메모리에서 지운다.
(리스트는 모든숫자가 동시에 메모리에 저장됨)

 

(3) 1이 될 때 까지
1. N의 범위가 100억 이상의 큰 수 가 되는 경우, 한번에 하나씩 1을 빼는 것 보다는 한번에 빼고 카운트하는것이 효율적이다.