[코딩테스트 합격자 되기 스터디] 10주차 - 그리디 (9.8 ~ 9.14)
코딩테스트 합격자 되기 스터디 10주차
강의 보기 -> 해당되는 부분 책 다시 읽기 -> 블로그 정리
강의는 C++로 되어 있지만 개념적인 내용이라 언어 상관 없이 보고 코드는 각 언어에 맞게 바꾸면 된다.
참고 강의 및 책
인프런 : 코딩테스트 합격자 되기 파이썬, C+_+ 저자님 인프런 강의 링크
Youtube : 코딩테스트 합격자 되기 파이썬, C+_+ 저자님 Youtube 링크
종이책 : 코딩테스트 합격자 되기 파이썬 편
종이책 : 코딩테스트 합격자 되기 C++ 편
종이책 : 코딩테스트 합격자 되기 자바스크립트 편
종이책 : 코딩테스트 합격자 되기 자바 편
그리디
- 매 순간 가장 좋아 보이는 선택을 한다.
- 특정 조건이 만족하는 경우 최적해를 보장한다.
- 최적해를 보장하기 위한 특성
- 탐욕적 선택 속성 : 각 단계에서 가장 좋은 것을 선택한다는 것이 전체 문제 최적해가 된다.
- 최적 부분 구조 : 부분 문제의 최적해로 전체 문제의 최적해를 구성할 수 있다.
예시 1 - 거스름돈 문제
- 13원을 거슬러줘야 할 때, 가장 적은 동전 개수로 거슬러 주는 방법은?
- 화폐 단위는 4원, 2원, 1원
- 그리디로 풀리는 경우
- 화폐가 큰 동전부터 최대한 활용한다.
- 4원, 4원, 4원, 1원
- 8원을 거슬러줘야 할 때, 가장 적은 동전 개수로 거슬러주는 방법은?
- 화폐 단위가 5원, 4원, 1원
- 그리디로 풀리지 않는 경우
- 화폐가 큰 동전부터 활용했을 때는 5원, 1원, 1원, 1원
- 다른 동전을 활용했을 때는 4원, 4원
- 큰 동전을 활용했을 때 보다 작은 동전을 활용했을 때 개수가 더 적다.
- 각 화폐간 단위가 배수 관계
- 1원, 2원, 4원
- 4원은 2원의 조합, 2원은 1원의 조합으로 만들 수 있다.
- 앞의 동전을 최대한 사용해도 뒤의 동전 사용에 영향을 미치지 않는다.
- 그리디로 최적해를 보장한다.
- 각 화폐간 단위가 배수 관계가 아닐 때
- 5원, 4원, 1원
- 5원을 최대한 사용해서 거슬러준 경우 4원을 사용하지 못한다.
- 이후 동전 선택에 영향을 미친다.
- 배수 관계가 아니더라도 그리디로 풀 수 있지만 최적해를 보장하지 않는다.
예시 2 - 최소 신장 트리(MST)
- 신장 트리
- 모든 정점이 간선으로 연결되어 있다.
- 간선 개수가 정점 개수보다 하나 적은 그래프
- 최소 신장 트리
- 신장 트리 중, 가중치의 합이 최소인 것
- 최소 신장 트리 구하기 (프림 알고리즘)
- 임의 정점 하나 최소 신장 트리에 추가한다.
- 최소 신장 트리로 연결된 정점 중 가장 가중치가 적은 정점을 최소 신장 트리에 추가한다.
- 위 경우, 순환을 형성하지 않아야 한다.
- 2, 3과정을 신장 트리 조건에 만족할 때까지 반복한다.
코딩 테스트에서 그리디
- 매순간 가장 좋은 선택을 하면서 해결되는 경우
- 최소 신장 트리
- 최단 경로 문제(다익스트라에서 사용, 밸만포드는 아님)
- 특정 조건을 만족하면서 가장 최대 / 최소값을 찾는 경우
- 부분 배낭 문제(0/1 배낭은 그리디 아님)
- 스케쥴링 문제