4Legs_Archives

문제 링크 : www.acmicpc.net/problem/16225 16225번: 제271회 웰노운컵 첫 줄에 짝수 N(2 ≤ N ≤ 200,000)이 주어진다. 다음 줄에 A[1], ..., A[N], 그 다음 줄에 B[1], ..., B[N]이 (1 ≤ A[i], B[i] ≤ 109) 주어진다. 모든 A[i]는 서로 다르고, 모든 B[i]도 서로 다르다. www.acmicpc.net 문제 유형 Greedy 문제 두 개를 선택했을 때, 항상 상대는 B값이 더 큰 문제를 가져간다 했으므로, 주어진 문제들을 B값의 오름차순으로 정렬해 보자. 정렬 후 알 수 있는 사실은 다음과 같다. 즉, 2k + 1 번까지의 문제 중에서 k + 1 개의 문제를 가져갈 수 있고, 이 때 문제를 어떤 조합으로 고르던 항상 배..

문제 링크 : www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net [문제 유형] Tree DP, Greedy 만약 한 사원에 대해, 그 사원의 직속 부하(즉, 인접 자식 노드)로부터 전파가 완료되는 시간을 모두 알고 있다고 가정해보자. 이 때, 전파 시간이 오래 걸리는 사원에게 먼저 전파하는 것이 총 전파 시간을 줄이는 데 반드시 좋을 것이다. 직속 부하에게는 한 번에 한 명에게만 전파가 가능하기 때문이다. 따라서 각 직속 부하들로부터 완료되는 전파 시간들을 큰 순으..

문제 링크 : www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 주어진 무게추로 측정할 수 없는 최소무게를 구하는 문제이다. 무게추 1, 2, 3을 갖고 있다고 가정할 때, 우리는 1에서 6까지의 모든 무게를 측정할 수 있다. 이 상태에서 새로운 무게추 5가 추가되었을 때, 이미 우리는 1에서 6까지의 무게를 1~3 무게추로 측정할 수 있었기 때문에 각 무게에 대한 무게추 조합에 5 무게추만 추가한 새로운 조합을 만들어 낼 수 있다. 다시 말해 우리가 2, 3 무게추를 ..

문제 링크 : www.acmicpc.net/problem/20117 20117번: 호반우 상인의 이상한 품질 계산법 어떤 묶음에 있는 호반우의 품질이 [1, 2, 3, 4] 라고 하면 중간값인 3으로 모든 호반우의 품질을 계산한다. 따라서 이 묶음의 총 가격은 3 × 4 = 12 가 된다. 품질이 [6, 3, 9] 라고 하면 중간값인 6으로 www.acmicpc.net 그리디 알고리즘으로 해결할 수 있는 문제이다. 판매하는 물건들을 가장 비싸게 팔 수 있는 가장 좋은 방법은 가장 싼 물건과, 가장 비싼 물건을 묶어 파는 것이다. 문제에서 물건의 묶음이 짝수인 경우, 가격의 중앙값은 (묶음 개수/2+1)번째 호반우로 정의했기 때문에 (k1, k2) 묶음에 대해서 반드시 k2의 가격이 중앙값이 된다. 따라서..

문제 링크 : www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 책을 최대한 많이 나눠주기 위해선 어떻게 해야 할까? 우선 책 번호의 범위가 좁은 사람에게 먼저 책을 나눠주는 것이 유리할 것이다. 범위가 넓은 사람에게 더 많은 선택지가 있기 때문이다. 또한, 동일한 크기의 여러 구간들이 겹쳐 있는 경우에는 최대한 겹치는 구간의 수가 적은 책을 먼저 나눠주어야 더 많은 사람에게 책을 나눠줄 수 있을 것이다. 겹치는 구간을 최대한 피하기 위한 방법은 다음과 같은 두 ..

문제 링크 : www.acmicpc.net/problem/20115 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 그리디 알고리즘으로 해결할 수 있는 문제이다. 최종적으로 만든 드링크의 양이 최대가 되기 위해서는, 두 드링크를 섞을 때 버려지는 양이 최소가 되어야 한다. 그러기 위해서는 두 드링크를 섞을 때, 원래 양이 더 적은 드링크를 절반 버리는 것이 이득이다. 따라서, 드링크의 목록 중 가장 양이 많은 드링크가 기준이 되어, 다른 모든 드링크를 절반씩 섞은 양이 최종 드링크의 최대 양이 된다. [코드] ..

문제 링크 : www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 그리디 알고리즘으로 해결이 가능한 활동 선택 문제이다. 핵심은 각 문제들을 어떤 기준으로 정렬할 것인지(즉, 어떤 문제의 우선순위를 높게 잡을 것인지)이다. ① 우선 당연히 받을 수 있는 컵라면의 갯수가 많은 문제를 우선적으로 풀어야 할 것이다. 하지만 위와 같은 상황에서, 보상이 8개인 문제를 먼저 풀게 된다면 데드라인이 1인 문제 하나를 풀 수 없게 된다. 보상이 8인 문제는 데드라인이 3이기 때문에 ..

문제 링크 : www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 평소에 전공지식 공부를 병행한 사람이라면 무언가 번뜩할 것이다. 이 문제는 페이지 교체 알고리즘에 빗대어 설명할 수 있기 때문이다. [OS/운영체제] 페이지 교체 (Page Replacement) - (2) FIFO (First-In, First-Out) Page Replacement FIFO는 가장 단순한 페이지 교체 알고리즘으로, 메모리에 옮겨진 메모리들 중 가장 오래된 페이지를 Victim으..

문제 링크 : www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 이 문제가 그리디 알고리즘으로 해결할 수 있다는 것을 캐치한다면, 일반적으로는 더 자릿수가 큰 수의 앞 자리 알파벳부터 큰 수를 부여하는 식의 접근을 할 것이다. 하지만 이러한 접근의 경우 각종 예외 케이스들을 관통하는 하나의 코드를 구현하기 매우 까다롭다. 예를 들어 ABC와 BB 9개, 총 10개의 단어에 대해 A = 9, B = 8, C = 7 이라면 987 + 88 * 9 = 1,77..

Greedy Algorithm 탐욕 알고리즘(그리디 알고리즘)은 특정 경우들 중 하나를 선택할 때, 그 순간에 가장 최적의 경우를 선택하는 알고리즘이다. 목적지까지 최단 경로로 가야 하는 상황을 예로 들어보자. 목적지를 향해 가던 중, 갈림길을 만났다. 그리디 알고리즘에서는, 다음과 같은 갈림길들 중 현재 상황에서만 최적인 경우를 선택한다. 따라서 위 그림에 그리디 알고리즘을 적용한다면, 직진을 하게 될 것이다. 하지만 만약 직진으로 간 다음 경유지에서 목적지까지의 거리가 100km이고, 다른 두 갈림길의 경유지에서 거리는 10km라면 어떻게 될까? 그리디 알고리즘을 통해 최적의 경우를 선택했지만, 결과적으로는 직진을 선택했기 때문에 목적지까지 최단경로로 갈 수 없게 된다. 이와 같이 그리디 알고리즘은 ..