[유형]그리디 [문제링크]https://www.acmicpc.net/problem/1339 [요약]예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. [문제풀이]예를 들어, GCF + ACDEB를 계산한다고 할 때,words[G] = 10^2, words[C] = 10^1 + 10^3, ... , words[B] = 10^0을 저장한다.{'G': 100, 'C': 1010, 'F': 1, 'A': 10000, 'D': 100, 'E': 10, 'B': 1}딕셔너리 word..

[유형]그리디  [문제링크]https://school.programmers.co.kr/learn/courses/30/lessons/42884 [요약]고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. [문제풀이]도착지점을 기준으로 정렬을 한다.첫번째 도착지점에 단속카메라를 설치(prev_end)하고, 다음 차량의 출발지점(start)이 도착지점(prev_end)보다 크면 새로운 단속카메라를 설치한다.def solution(routes): answer = 1 routes.sort(key= lambda x: x[1]) prev..

[유형]heap [문제링크]https://www.acmicpc.net/problem/11000 [요약]김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.  [문제풀이]시작 시간이 빠른 순으로 정렬을 한다.최소힙을 사용해서, 강의 끝나는 시간이 새로운 강의 시작 시간보다 느리면, 새로운 강의실을 사용한다.(heappush)import sysimport heapqdef input(): return sys.stdin.readline().rstrip()times= []N = int(input())for N in range(N): start,end = map(int,input().split()) times.appe..

[유형]그리디 [문제링크]https://www.acmicpc.net/problem/1449 [요약]물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오.  [문제풀이]import sysfrom collections import Counterdef input(): return sys.stdin.readline().rstrip()N, L = map(int,input().split())locations = list(map(int, input().split()))locations.sort()start = locations[0] - 0.5end = start + Lcount = 1for location in loca..

[유형]그리디 [문제링크]https://www.acmicpc.net/problem/11399 [요약]줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오. [문제풀이]돈을 인출하는데 필요한 시간이 적은 사람 순으로 정렬을 한다.import sysdef input(): return sys.stdin.readline().rstrip()N = int(input())waitings = list(map(int, input().split()))waitings.sort()answer = [0] * (N)answer[0] = waitings[0]for i in range(1,N): ans..

[유형]DP [문제링크]https://www.acmicpc.net/problem/2294 [요약]n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. [문제풀이]동전의 구성이 1,5,10일때 가치의 합이 15가 되는 동전 최소 개수동전 1을 통해 1~15원까지 만들 수 있는 동전의 최소 개수는 각각 1,2,3,...,10이다. 따라서, dp[i]=i로 갱신된다.동전 5가 추가되었을 때, dp[4]까지의 값은 더 이상 갱신되지 않는다.dp[5]는 min(dp[5],dp[5-5]+1)이라고 할 수 있다. 5 1개만으로 5원을 만들 수 있다.import sysfrom ..