목록전체 글 (601)
sm 기술 블로그
import sys input = sys.stdin.readline N = int(input()) timeList = [list(map(int, input().split())) for _ in range(N)] # 시작시간, 끝시간 timeList2 = [] timeList.sort(key=lambda x: (x[1], x[0])) for val in timeList: timeList2.append(val) endMin = timeList[0][1] cnt = 1 del timeList[0] del timeList2[0] #처음에 시작과 종료시간이 같은 회의가 들어갈 수 있음 for val in timeList: if val[0] < endMin: timeList2.remove(val) else: end..
import java.util.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); Integer[] coinList = new Integer[N]; int cnt = 0; for (int i = 0; i K) { continue; } else { if (K == 0) { break; ..
import sys input = sys.stdin.readline N,K = map(int,input().split()) coinList = sorted([int(input()) for _ in range(N)], reverse = True) cnt = 0 for val in coinList: if K == 0: break cnt += K//val K %= val print(cnt) 문제요약 주어진 동전 리스트를 최소로 사용하여 가치에 맞게 만드시오 설명 그리디 알고리즘의 대표 문제이다. 그리디 알고리즘에 대해서는 아래를 참고하자 https://smhope.tistory.com/384 [알고리즘 | 자료구조] 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘(Greedy Algorithm..
그리디 알고리즘(Greedy Algorithm) 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법 예시) 다음 중 가장 큰수를 고르라고 한다면 그리디 알고리즘은 12 -> 6 을 선택한다. 결과를 봤을 때 최적의 수는 아니지만 모든 노드를 거치지 않아 계산속도가 빠르다는 점을 지녔다. 문제 해결 방법 선택절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택절차로 돌아가 위의 과정을 반복 사용하는 문제 활동 선택 문제 거스름돈 문제 최소 ..