![]()
18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net 처음에는 그리디 알고리즘 인줄알았다. 우선순위를 3번 -> 2번 -> 1번 순으로 처리하면 될 줄 알았지만,,,, 2322 인 경우를 생각해보자 그리디 알고리즘으로 풀 경우 2322 ->(14) 0102-> (3) 0002 -> (6) 0000 총 23의 값이 나온다. best값은 무엇일까? 2322 ->(10) 0122 ->(7) 0011 -> (5) 0000 총 22의값 2322 -> (5) 1222 ->(7) 0112 -> (7) 0001 ..
![]()
Greedy는 '탐욕스러운, 욕심 많은' 이란 뜻이다. 탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법이다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 즉, 탐욕 알고리즘을 적용할 수 있는 문제들은 그 순간에 최적값들을 계속 수집하여 최종적인 답을 만들어도 최적인 문제들이다. 탐욕 알고리즘 문제를 해결하는 방법 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사(Solution Check): 원..
