공대생

https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 내 답안 en = [500, 100, 50, 10, 5, 1] cnt = 0 x = 1000 - int(input()) for i in en: cnt += (x // i) x %= i print(cnt) Review 그리디 알고리즘의 매우 간단한 대표적인 문제이다. 코드가 이해 안된다면 아래 글을 참고 하자. https://thingjin.tistory.com/entry/%E..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 내 답안 x = input().rstrip().split('-') result = [sum(map(int, i.split('+'))) for i in x] print(result[0] - sum(result[1:])) REVIEW 문제를 보면서 어떻게 하면 잘 계산을 할 수 있을까 고민을 하였다. 내가 생각한 순서는 이렇다. 1번 "-" 단위로 끊어서 리스트를 만든다. -> ["55", "5..

그리디 알고리즘( Greedy Algorithm ) 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 단어 그대로 번역 하면 탐욕법 이고 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘 이다. 여기서 탐욕적 이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 매 순간 가장 좋아 보이는 것을 선택하며 , 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 코딩 테스트 유형 그리디의 문제 유형은 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높다. 최단 경로를 구하는 다익스트라 알고리즘은 그리디 알고리즘으로 분류 되므로 암기가 필요한 알고리즘 이다. 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에 다익스트라 알고리즘과 같은 특이 케이스를 제외하고는 단순 암기를 통해..