[CS] 알고리즘 - 그리디

1. 그리디 알고리즘 이란?현재 상황에서 지금 당장좋은 것만 고르는 방법단순히 가장 좋아 보이는 것만 반복적으로 선택해도 최적의 해를 구할 수있는지 검토예: 루트 노드부터 시작해 거쳐가는 노드의 값을 최대로 하고 싶은경우→ 단순히 매 상황에서 가장 큰 값만 고르는 방식일반적인 상황에서 최적의해를 보장할 수 없을 때가 많다- 500 100 50 10 → N가장 큰 화폐부터 돈을 거슬러준다⇒ 최적의 해를 보장하는 이유는?⇒ 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가나올 수 없기 때문!500, 400, 100원인 경우 500원이 400원의 배수가 아니므로 다른 해법이 나올 수 이다.화폐의 종류가 K라고 할때, 소스코드의 시간 복잡도는 O(K)이 알고리즘의 시간 복잡도는 거..
AI/CS 2025. 3. 5. 22:11
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/03   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
글 보관함