그리디 (3) 썸네일형 리스트형 [알고리즘] 그리디(Greedy) 알고리즘 (Swift) 그리디 알고리즘에 대해 알아보고 대표문제를 Swift로 한 번 풀어보겠습니다. 그리디 알고리즘이란? 그리디 알고리즘을 번역하면 탐욕 알고리즘 이라고 한다. 말 그대로 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 즉, 매 순간마다 최선의 경우를 고르고 다른 경우는 고려하지 않는다. 그리디 알고리즘의 어려운 점은 이 문제가 그리디가 맞는지 판별하는 것이 가장 어려운 것 같다. 계속해서 반례가 있는지 확인해야하고 고민해야 한다. 그리디 알고리즘은 정렬 알고리즘과 주로 짝을 이루기도 한다. 대표 문제 백준 5585 거스름돈 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 .. [BOJ] 백준 2036 수열의 점수 (Swift) 문제 https://www.acmicpc.net/problem/2036 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net 풀이 1보다 큰 양수는 큰 양수끼리 곱하는 것이 가장 큰 값이 나올 것이다. 1은 더하는게 가장 큰 값이다. 1과 다른 수를 뽑아서 곱해봤자, (1 * x) = x 이기 때문 음수는 가장 작은 음수끼리 곱하는 것이 가장 큰 값이 나올 것임 0은 음수가 남았을 때, 음수랑 곱해주면 0으로 가장 큰 값이 나오게 될 것이다. 그 외에는 있으나 마나..? 그러므로 배열을 입력받고, 1보다큰 양수, .. [BOJ] 백준 5545 최고의 피자 (Swift) 문제 https://www.acmicpc.net/problem/5545 5545번: 최고의 피자 상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 www.acmicpc.net 풀이 1원 당 열량이 가장 큰 피자가 최고의 피자이고 최고의 피자의 1원 당 열량을 구하는 문제 입력받은 토핑을 가장 큰 열량별로 정렬을 해주고, 1원 당 열량을 계산하는 방식으로 풀이할 수 있겠다고 생각이 듬 1원 당 열량을 계산하고, 다음 토핑을 추가했을 때, 1원 당 열량이 현재보다 크다면 토핑을 추가하고 아니라면 더 이상 토핑을 추가하지 않으면 될 것이다 라고 생각함 소스코드 후기 소스코드.. 이전 1 다음
