그리디 알고리즘1 [C 언어] 탐욕 알고리즘 (Greedy algorithm) Coin change problem 탐욕 알고리즘은 눈 앞에 놓인 선택지 중에 현재 상황에서 가장 최선의 것을 선택하도록 디자인 된 알고리즘이다. 알고리즘은 일상에서 coin change problem, 즉 상점에서 잔돈 돌려주는 상황에 써먹을 수 있는데, 돌려줘야 될 잔돈의 수에 따라서 quarters 25, dimes 10, nickels 5, pennies 1 중 최선을 선택해야 한다. 여기서 최선의 선택이란 가장 높은 가치의 돈 (만약 >=25 이라면 25)을 우선으로 선택하고 남는 돈은 그 다음 (10->5->1)로 넘어가는 것이다. 이렇게 잔돈을 돌려주도록 코딩을 하기 위해서는 알고리즘처럼 직관적으로 생각하면 된다. 25 부터 1까지 순서대로 정렬한 후, 반복문을 돌면서 조건이 끝나는 때 남는.. 2022. 2. 27. 이전 1 다음
