실습_4. 탐욕적 기법
Updated:
실습
거스름돈
엘리스씨는 1원, 5원, 10원, 50원, 100원 짜리 동전이 무한개(!) 존재하는 가게에 근무한다. 손님이 계산을 하고 난 후, 거스름돈을 돌려주어야 하는데 가능한 적은 수의 동전을 돌려주고 싶다.
예를 들어, 7원을 돌려줘야 한다면 1원을 7개 돌려줄 수도 있지만, 그것보다는 5원 1개와 1원 2개를 돌려주는 것이 적은 수의 동전을 돌려주는 것이므로, 이것이 더 좋은 경우이다.
거스름돈 nn원을 돌려주어야 할 때, 돌려주어야 하는 동전 개수의 최솟값을 출력하는 프로그램을 작성하세요.
- 입력 예시 1
7
- 출력 예시 1
3
- 입력 예시 2
103
- 출력 예시 2
4
-
문제 조건
- 돌려주어야 하는 거스름돈은 최대 100,000,000입니다.
import sys
def coinChange(n) :
'''
n원을 돌려주기 위해 필요한 동전 개수의 최솟값을 반환하는 함수를 작성하세요.
'''
coins = (1,5,10,50,100)
cnts = [0 for i in range(n+1)]
for i in range(1,n+1):
Min = 987654321
for j in coins:
if i-j >= 0:
Min = min(Min,cnts[i-j]+1)
cnts[i] = Min
print(cnts)
return cnts[n]
def main():
'''
이 부분은 수정하지 마세요.
'''
n = int(input())
print(coinChange(n))
if __name__ == "__main__":
main()
기울기가 가장 큰 두 점 찾기 (Big)
2차원 평면에 nn개의 점이 있다. 이 점들 중에서 두 점을 선택했을 때, 그 기울기의 절댓값의 최댓값을 출력하는 프로그램을 작성하시오. 단, 모든 점의 x좌표는 다르다고 가정한다. 또한, 두 점 (x1, y1), (x2, y2)의 기울기는 (y2 - y1) / (x2 - x1) 으로 정의된다.
예를 들어, 4개의 점이 각각 (0, 3), (1, 1), (2, 2), (4, 1) 에 위치해 있다고 하면, 기울기의 절댓값의 최댓값은 2가 된다.
이 경우 기울기 절댓값의 최댓값인 2를 출력합니다.
입력으로는 첫줄에 점의 개수가, 그 다음줄부터는 점의 xx좌표와 yy좌표가 입력됩니다.
- 입력 예시
4
0 3
1 1
2 2
4 1
- 출력 예시
2.000
-
문제 조건
- 점의 개수는 최대 100,000개를 넘지 않습니다.
- 점의 좌표는 모두 정수입니다.
- 출력은 소숫점 넷째자리에서 반올림하여 출력합니다.
import sys
def maxSlope(points) :
'''
n개의 점들 중에서 2개의 점을 선택했을 때, 얻을 수 있는 기울기의 절댓값 중에서 가장 큰 값을 반환하는 함수를 작성하세요.
**주의** : 소숫점 넷째자리에서 반올림하는 것은 고려할 필요가 없습니다. 이는 main()에서 출력을 할 때에 처리가 되므로, 기울기의 최댓값을 구하는 것에 집중해 주시길 바랍니다.
'''
Max = 0
print(points)
points = sorted(points, key=lambda x: x[0])
for i in range(len(points)-1):
Max = max(Max, abs((points[i][1]-points[i+1][1])/(points[i][0]-points[i+1][0])))
return Max
def main():
'''
이 부분은 수정하지 마세요.
'''
n = int(input())
points = []
for i in range(n) :
line = [int(x) for x in input().split()]
points.append( (line[0], line[1]) )
print("%.3lf" % maxSlope(points))
if __name__ == "__main__":
main()
Fractional knapsack
nn개의 물건이 있고, 각 물건은 무게 w_iw i 와 가치 c_ic i 를 갖는다. 이제 이 물건들을 배낭에 넣으려 한다. 이 배낭은 무게 mm까지를 버틸 수 있다.
한 가지 재미있는 사실은, 물건을 쪼갤 수 있다는 것이다. 물론, 물건을 쪼개게 되면 무게가 줄지만, 가치도 줄게 된다. 예를 들어, 무게를 절반으로 줄이면 가치 역시도 절반으로 줄어들게 된다.
배낭이 버틸 수 있는 무게 mm과 nn개의 물건의 정보가 주어질 때, 배낭이 담을 수 있는 가치의 최댓값을 소숫점 넷째자리에서 반올림하여 출력하는 프로그램을 작성하세요.
입력에 첫줄에는 물건의 개수nn과 베낭의 버틸수 있는 무게 mm이 입력됩니다.
이후 nn개의 줄에 대하여 각 물건의 무게 w_iw i , 그리고 가치 c_ic i 가 주어진다.
- 입력 예시 1
4 10
3 10
2 7
4 9
5 13
- 출력 예시 1
30.000
- 입력 예시 2
4 11
3 10
2 7
4 9
5 13
- 출력 예시 2
32.250
-
문제 조건
- 물건의 개수는 최대 100,000개 입니다.
import sys
def fKnapsack(materials, m) :
'''
크기 m까지 버틸 수 있는 베낭이 담을 수 있는 최대 가치를 반환하는 함수를 작성하세요.
주의 : 셋째 자리에서 반올림하는 것을 고려하지 않고 작성하셔도 됩니다.
'''
materials = sorted(materials, key=lambda x: x[1]/x[0], reverse = True)
print(materials)
Sum = 0
for mete in materials:
if mete[0] <= m:
Sum += mete[1]
m -= mete[0]
if m == 0:
break
else:
Sum+=m*(mete[1] / mete[0])
break
print(Sum)
return Sum
def main():
'''
이 부분은 수정하지 마세요.
'''
line = [int(x) for x in input().split()]
n = line[0]
m = line[1]
materials = []
for i in range(n) :
data = [int(x) for x in input().split()]
materials.append( (data[0], data[1]) )
print("%.3lf" % fKnapsack(materials, m))
if __name__ == "__main__":
main()
미션
회의실 준비
엘리스씨는 보다 더 나은 서비스를 제공하기 위하여 정기적인 회의를 하는 것을 선호하는 편이다. 여기서 엘리스씨의 역할은 nn개의 회의가 언제 시작하는지, 그리고 언제 끝나는지를 모두 모으고, 그 이후 각 회의가 어느 장소에서 이루어져야 하는지를 정한다. 각 회의가 시작하는 시간, 그리고 끝나는 시간은 초단위로 주어진다고 하자. 예를 들어, 하나의 회의는 10초에 시작하여 99초에 끝날 수 있다.
당연하게도, 두 개의 회의가 시간이 겹칠 경우에는 같은 회의실을 사용할 수 없다. 또한, 만약 정확히 10초에 끝나는 회의가 있고, 또 다른 회의가 정확히 10초에 시작한다면, 이 두 회의는 같은 회의실을 사용할 수 있다.
회의실을 빌리는 데에는 돈이 들기 때문에, 엘리스씨는 가능한한 적은 수의 회의실을 준비하고자 한다. nn개의 회의에 대한 정보가 주어질 때, 모든 회의가 이루어지기 위하여 빌려야 하는 회의실의 최소 개수를 출력하는 프로그램을 작성하시오.
입력의 첫째 줄에 회의실의 개수 nn이 주어진다.
이후 각 회의에 대하여 회의가 시작하는 시간, 그리고 끝나는 시간이 주어진다.
- 입력 예시 1
4
1 4
3 5
2 7
4 6
- 출력 예시 1
3
- 문제 조건
- 회의실의 개수는 최대 1,000개 입니다.
import sys
def reservation(meetingList) :
'''
회의 일정이 list로 주어질 때, 엘리스씨가 준비해야 하는 회의실의 수의 최솟값을 반환하는 함수를 작성하세요.
각 일정은 tuple로 주어진다. 예를 들어, 주어진 입력의 경우 다음과 같이 저장된다.
meetingList[0] = (1, 4)
meetingList[1] = (3, 5)
meetingList[2] = (2, 7)
meetingList[3] = (4, 6)
'''
meetingList = sorted(meetingList, key=lambda x: x[0])
print(meetingList)
check = True
nums = []
for meet in meetingList:
for i in range(len(nums)):
if nums[i] <= meet[0]:
nums[i] = meet[1]
check = False
break
if check:
nums.append(meet[1])
check = True
nums = sorted(nums, reverse = True)
print(nums)
return len(nums)
def main():
'''
이 부분은 수정하지 마세요.
'''
n = int(input())
meetingList = []
for i in range(n) :
data = [int(x) for x in input().split()]
meetingList.append( (data[0], data[1]) )
print(reservation(meetingList))
if __name__ == "__main__":
main()
회의 참석
nn개의 회의가 언제 시작하는지, 그리고 언제 끝나는지가 주어진다. 엘리스씨는 이제 이 nn개의 미팅 중에서 최대한 많은 미팅에 참석하고자 한다. 물론, 동시에 진행되는 두 개의 회의에는 동시에 참석할 수 없다. 또한, 10초에 끝나는 회의와 10초에 시작하는 회의가 있다면, 이 두 회의에는 모두 참석할 수 있다고 하자.
nn개의 회의에 대한 정보가 주어질 때, 엘리스씨가 참석할 수 있는 회의의 최대 개수를 출력하는 프로그램을 작성하시오.
입력의 첫째 줄에 회의실의 개수 nn이 주어진다.
이후 각 회의에 대하여 회의가 시작하는 시간, 그리고 끝나는 시간이 주어진다.
- 입력 예시 1
5
1 4
3 5
2 7
4 6
7 8
8 출력 예시 1
3
-
문제 조건
- 회의실의 개수는 최대 100,000개 입니다.
- 회의의 시작시간과 종료시간은 모두 정수입니다.
-
출력
엘리스씨가 참석할 수 있는 회의의 최대 수를 출력한다.
import sys
def attending(meetingList) :
'''
회의 일정이 list로 주어질 때, 엘리스씨가 참석할 수 있는 최대 회의 수를 반환하는 함수를 작성하세요.
'''
meetingList = sorted(meetingList, key = lambda x:x[1])
print(meetingList)
end = meetingList[0][1]
cnt = 1
for i in range(1, len(meetingList)):
if end <= meetingList[i][0]:
end = meetingList[i][1]
cnt +=1
return cnt
def main():
'''
이 부분은 수정하지 마세요.
'''
n = int(input())
meetingList = []
for i in range(n) :
data = [int(x) for x in input().split()]
meetingList.append( (data[0], data[1]) )
print(attending(meetingList))
if __name__ == "__main__":
main()
Leave a comment