[자료구조] 그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘

탐욕스러운
-> 가장 처음의 경우로 만족하면 끝내는 (뒤의 것 신경 쓰지 않는 )

* 동전 금액 맞추기가 쉬운 에제


✅ Greedy 알고리즘 사용하기 위한 조건 
- 탐욕적 선택 속성(Greedy Choice Property) : 현재 선택이 미래 선택에 영향을 미치지 않을 때
- 최적 부분 구조(Optimal Substructure) : 부분의 최적 해가 모이면 전체의 최적해 
-> 큰 문제를 작은 부분으로 나눌 수 있고 그 작은 문제들에 대한 최적의 해가 더해진 것이 곧 전체 문제의 최적해가 되는 것(최적 부분 구조 조건)


✅ 정렬
그리디 전략
그리디 전략을 쓰는 이유
- 속도()
- 다이나밍 프로그래밍 = 100%최적해를 보장하기 위해 사용
- 100% 최적해를 보장하지 않는 경우에 대해 그리디 전략을 사용
- 성능 개선을 위해(ex 길 안내 )


✅ 완전탐색 (Brute Force)과 시뮬레이션 (Simulation)
완전탐색 ->모든 경우의 수 확인하여 문제 푸는 것
for나 loof 또는 재귀함수로 모든 구성을 다 구현해보는 것
ex) 프로그래머스 모의고사, 소수찾기 추천

시뮬레이션 -> 문제에서 요구하는 구현을 코드로 옮겨 시뮬레이션 하는 것 처럼 


1. 선택절차 : 현재 상태에서 최적의 해답 선택
ex) 동전 가장 큰 거 부터 선택
2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
ex) 선택된 동전이 구하고자 하는 금액 초과하는지 검사, 아니면 작은 동전 선택 반복
3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고 해결되지 않으면 선택 절차로 돌아가기
ex) 합을 더해 일치하는지 검사, 부족하면 반복

 

---

 

어제는 진짜 역대 역대 역대급으로 어려웠는데 그래프 순환 알고리즘인 BFS, DFS를 보다 오니 한 결 나았다. 숨통이 트이는 기분.. BFS, DFS를 알고 있어야 한다고 되어있어 아침에 일어나 어제 설명에 있던 예제 문제를 다시 다시 봤다. 오늘은 그리디 에 대해 배웠는데 재미있었다. 

수도 코드를 쓰는 것도 수월했고 너무 재미있는 시간이었던 것 같다. 어제 너무 힘들어서 그런가?ㅋㅋㅋ 코플릿 문제도 생각보다 술술 풀려서 너무 좋았다. : )

오늘 남은 시간은 컬렉션을 다시 복습하고 공부하고자 한다. 이렇게 블로그를 쓰지 않는 부분들은 진짜 확실히 기억이 안난다.... 블로깅은 보여주기 위해서 하는 것 보다 나를 위해 하는 것임을 다시 깨닫는 매일매일이다.