그리디

[python] 백준 - 1931. 회의실 배정

🤔문제 해결 S2 | 정렬, 그리디 회의 시간이 긴 것과 상관 없이 회의가 끝나는 시각이 빠른것을 선택 회의가 끝나는 시각이 빠른 순으로 정렬 이전 회의가 끝난 시각과 비교하여 회의를 시작할 수 있으면 카운트 +1 없으면 통과 💨 끝나는 시각 뿐만 아니라 시작 시간도 두번 째로 정렬 해줘야 한다. 반례 [2,2], [1,2] 💨 sys.stdin.readline 과 input의 차이 (아래가 input()으로 받은 것) 💻소스 코드 import sys input = sys.stdin.readline N = int(input()) meetings = [list(map(int, input().split())) for _ in range(N)] meetings.sort(key=lambda x: (x[1], x..

[python] 백준 - 11497. 통나무

🤔문제 해결 S1 | 정렬, 그리디 알고리즘 왼쪽과 오른쪽 끝을 최솟값으로 점점 채우는 방식으로 문제를 해결했음 리스트에서 최솟값을 꺼내는 방법은 힙큐를 사용 예시 [1, 2, 3, 4, 5, 6, 7] 위의 그림을 보면 가장 앞의 1과 가장 뒤의 2의 차이도 최소로 할 수 있음 다음 리스트 앞뒤로 값의 차이의 최댓값을 답으로 저장 💨 💻소스 코드 import heapq def solution(N, logs): heapq.heapify(logs) my_logs = [0] * N left = 0 right = -1 for _ in range(N // 2): my_logs[left] = heapq.heappop(logs) my_logs[right] = heapq.heappop(logs) left += 1 r..

[python] 백준 - 11399. ATM

문제 해결 1. 그리디 알고리즘. S3 2. 단순하게 정렬을 이용해서 문제를 해결했다. 3. 각각의 사람들이 기다리는 시간은 수학적으로 계산을 했다. ⛅ 생각보다 단순하고 쉬운 문제였다. 소스 코드 n = int(input()) people = list(map(int, input().split())) # 오름차순으로 정렬 people.sort() result = 0 # i번 째 사람이 인출 할 경우 i번 부터 i+n까지의 사람들은 *n시간 기다려야 한다. # 그러므로 n을 곱해서 더해준다. for i in range(len(people)): result += people[i] * (len(people) - i) print(result) 출처: BACKJOON ONLINE JUDGE 문제: https://..

[python] 백준 - 11047. 동전 0

문제 해결 1. 그리디 알고리즘. S1 2. 큰 동전부터 순차적으로 for문을 돌리며 (1) 목표값 k 보다 작은 동전이 나왔을 때 그 동전의 값을 뺄 수 있는 만큼 빼준다. ex) 45원이 남았을 때 10원짜리 동전이 나왔다면 계산을 통해 10원을 4번 빼주고 카운트를 4 올려준다. (2) 빼준 값만큼 k값을 줄여가며 동전을 0원으로 만든다. (3) 누적된 cnt 값을 출력해주면 끝 🌞 탐색알고리즘을 해결할 땐 시간을 최적화 하는게 중요한 것 같다. ❓처음 해결방법: 동전값을 찾았을 때 while문으로 동전을 하나씩 빼줬는데 시간 초과가 났다. ❓두번째 해결방법: k값이 0이 됐음에도 불구하고 나머지 for문을 돈다고 생각하여 break문을 추가했다. 이것도 시간 초과. 사실 별로 도움이 안된거 같다...