링크 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 소요시간: 5분 21초 설계하기(접근방법) 이전 문제와 완전히 동일하여 생략하겠습니다 1. 입력받기 2. 구현하기 3. 출력하기 코드(출력) import sys , heapq n = int(input()) h = [] for i in range(n): card = int(input()) heapq.heappush(h,card ) count = 0 while len(h)..
링크 : https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 문제 소요시간: 11분 30초 설계하기(접근방법) 1. 입력받기 이 문제는 그냥 풀면 시간초과가 날 것이다 2. 구현하기 가장 작은 파일 2개를 계속 합산해 나가다 보면 최적의 해를 구할 수 있을 것이다 작은 파일을 항상 앞에 나오도록 하려면 heap 자료구조를 사용해야 한다 즉 입력받은 list를 heapify 한 후 heap의 앞 두 원소 최소1, 최소2를 pop한 후 둘을 더해준..
링크 : https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 문제 소요시간: 35분 설계하기(접근방법) 1. 입력받기 입력이 많기 때문에 sys로 입력받는다 2. 구현하기 이 문제를 가로로 살펴보면 알 수 있는 포인트가 있다 1층을 기준으로 설명하면 건물이 끝나는 지점까지는 1층은 얼마나 확장하든 한 건물로 취급할 수 있다. 즉 한번 올라간 n층은 n-1층으로 스카이라인이 하강하지 않는다면 유지..
링크 : https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 문제 소요시간: 설계하기(접근방법) 1. 입력받기 입력받을 마을의 개수가 많으므로 sys를 통해 입력받는다 2. 구현하기 약 30분 동안 아이디어를 고민했지만 떠오르지 않았다 이 문제의 답은 인구수의 중앙값이 넘어가는 지점이다 처음에는 해설을 보고 이해를 못해서 GPT4에게 물어봤다 이 처럼 좌우의 개수가 ..
링크 : https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제 소요시간: 30분 초과(실패) 설계하기(접근방법) 1. 입력받기 크레인 수 크레인 리스트 박스 수 박스 리스트를 입력받는다 2. 구현하기 이 문제의 핵심은 가벼운 박스의 경우 무게를 많이 들 수 있는 크레인과 적게 들 수 있는 크레인 모두 들 수 있으므로 이를 어떻게 분배해서 최소의 시간만에 박스를 옮기느냐 이다 처음에는 무게 범위대로 배분을 한 후 각 크레인보다 무..
링크 : https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 소요시간: 12분 7초(구현 9분 10초) 설계하기(접근방법) 1. 입력받기 센서 집중국 센서의 좌표를 입력받는다 2. 구현하기 이전의 행복 유치원과 매우 유사하 문제이니 구현 부분은 생략하겠다 다만 집중국의 개수가 센서의 개수보다 많은 경우 집중국의 개수가 센서의 개수와 동일한 사례와 같으므로 조건문으로 처리해준다 3. 출력하기 최소 범위의 합을 출력한다 ..
링크 : https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 문제 소요시간: 22분 27초 설계하기(접근방법) 1. 입력받기 유치원생 수, 조의 개수와 유치원생 키 리스트를 입력받는다 2. 구현하기 모든 숫자의 차이를 검사해서 가장 큰 차이부터 (조의 개수 - 1)만큼 제거한다 모든 숫자의 차이는 첫번째 인덱스와 마지막 인덱스의 차이이다 heapq의 자료구조를 이용해서 모든 리스트를 순회하면서 차이를 max_heap의 형태로..
링크 : https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 문제 소요시간: 15분(우선순위큐 개념 익히기) 설계하기(접근방법) 1. 입력받기 입력받을 배열이 많으니 sys를 사용하자 2. 구현하기 이 문제의 배열 크기가 100,000이다. 즉 일반적인 정렬이나 완전 탐색으로는 시간이 초과된다 일단 문제를 해석하자면 이전 실버 1 문제의 회의실 배정과 비슷하다. 그 문제는 끝나는시간을 기준으로 정렬하고, 시작 시간을 비교하여 그리디로 풀었다 이..
