그리디 파이썬
-
탐욕 알고리즘 ( Greedy Algorithm )Algorithm/Source Code 2022. 3. 27. 10:42
Greedy Algorithm 그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘이라고도 한다 이름에서 알 수 있듯이 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다 정렬이나 최단경로 등의 알고리즘 유형은 알고리즘의 사용 방법을 정확히 알아야 하지만 그리디는 단순하면서 강력한 해결법이기 때문에 딱히 그렇지 않다 ! 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로' '가장 작은 순서대로' 같은 힌트를 잘 캐치하면 된다 ! 그리디 알고리즘 문제는 주로 정렬 알고리즘과 함께 출제된다 대표적인 거스름돈 ! 거스름돈으로 500원, 100원, 50원, 10원짜리 동전이 무수히 존재한다고 가정한다 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 ..
-
[백준 11501] 주식Algorithm/Source Code 2021. 12. 29. 18:28
문제 홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다. 주식 하나를 산다. 원하는 만큼 가지고 있는 주식을 판다. 아무것도 안한다. 홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다. 예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다...