1주차 (07월 04일)
목표
- 알고리즘 < 그리디 알고리즘 > 문제풀기 (백준 11047번, 백준 1931번, 백준 11399번)
회고
- 알고리즘 < 그리디 알고리즘 > 문제 : 백준 11047번(“동전0”) -> 난이도 : 실버2
해결 방법 : 큰 동전 순서로 정렬 한 후에 큰 동전으로 만들 수 있는 것부터 확인한다.
코드일부
N, K = map(int, sys.stdin.readline().rstrip().split())
coin = list()
result = 0
for i in range(N):
coin.append(int(input()))
coin.sort(reverse=True)
for i in range(N):
result += K // coin[i]
K = K % coin[i]
print(result)
- 알고리즘 < 그리디 알고리즘 > 문제 : 백준 1931번(“회의실 배정”) -> 난이도 : 실버2
해결 방법 : min heap을 사용해서 끝나는 시간이 작은 것부터 결과 list에 저장을 한다. 그리고 다음 시작 시간이 전에 처리한 끝난 시간보다 크다면 list에 저장을 한다.
코드일부
N = int(input())
schedule = list()
result = list()
for i in range(N):
start, end = map(int, sys.stdin.readline().rstrip().split())
heapq.heappush(schedule, (end, start))
finish = 0
while schedule:
end, start = heapq.heappop(schedule)
if start >= finish:
result.append((start, end))
finish = end
print(len(result))
- 알고리즘 < 그리디 알고리즘 > 문제 : 백준 1541번(“잃어버린 괄호”) -> 난이도 : 실버2
해결 방법 : 식을 입력 받으면 -로 split을 한다. 그 후에 split으로 나눠진 수를 맨 앞의 수만 더하고 나머지는 모두 뺀다.
코드일부
cal = list(sys.stdin.readline().rstrip().split('-'))
answer = 0
for i in cal[0].split('+'):
answer += int(i)
for i in cal[1:]:
temp = 0
for j in i.split('+'):
temp += int(j)
answer -= temp
print(answer)