목록매트로이드 (1)

미새문지

크래프톤 정글 week03, day18 - 그리디 알고리즘, 분할 정복

그리디 알고리즘(Greedy algorithm) - 탐욕법 가장 직관적인 형태의 알고리즘이며, 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘이다. 항상 최적의 결과를 뽑지는 못하지만, 확률 상 최적의 결과에 근사한 값을 빠르게 구할 수 있다. 즉, 특정한 상황에서 최적의 해를 보장하는 극한의 효율충 알고리즘 효율충인만큼 자원에 접근할 때 무조건 큰 경우, 긴 경우 등의 조건으로 문제를 극단적으로 접근하기 때문에 정렬 기법이 함께 사용되는 경우가 많다. 예시는 크루스칼 알고리즘으로 '모든 간선을 정렬한 이후에 짧은 간선으로 연결하는' 최소 신장 트리 알고리즘이 있다. 예시 문제로 일정 금액을 동전을 사용하여 낼 때 최소한의 개수로 낼 수 있는지 확인하는 문제 import sys # 금액을 입력받고 n = ..
크래프톤 정글/TIL 2024. 2. 20. 00:43
이전 Prev 1 Next 다음