목록백준 (13)
while (1): study();
출처: 1715번: 카드 정렬하기 (acmicpc.net) 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 전형적인 그리디 유형의 문제입니다. 대략적인 점화식을 써보자면 sum_n = a_n + sum_n-1과 같습니다. 즉 이전까지의 카드 뭉치의 합은 계속 더해지므로 가장 작은 카드 뭉치들을 먼저 합쳐나가는 방식으로 풀어나가면 됩니다. 다만 주의할 점은 단순한 정렬과 반복으로는 풀 수 없다는 점입니다. 다음 코드를 살펴봅시다. n = int(input()) array = [] for _ in ..
출처: https://www.acmicpc.net/problem/18310\ 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 처음에 이진탐색을 이용해 접근하려 했으나 아이디어만 떠올릴 수 있다면 쉬운 문제이다. 역시 문제를 풀기 전에 손보다는 머리를 움직이는 것이 중요하다는 것을 다시금 느끼게 된다. 결과적으로 최적의 안테나 설치 장소는 중앙값이다. 중앙에서 멀어지면 멀어질수록 거리가 멀어진다는 것을 휴리스틱하게 확인할 수 있으며, 생각을 조금만 해봐도 그렇다. 소스코드는 다음과 같이 간단하게 작성할 수 있다. n = int(inpu..
출처: 10825번: 국영수 (acmicpc.net) 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net sort함수에 대한 이해도가 있다면 쉽게 해결할 수 있는 문제입니다. N이 1 이상 100,000 이하이기 때문에 O(NlogN)의 시간복잡도를 보장하는 기본 정렬 기능을 사용할 수 있습니다. 소스코드는 다음과 같습니다. n = int(input()) array = [] for _ in range(n): array.append(input()) array = [row.split() for r..