Algorithm/Greedy

[SW Expert Academy 14178번] 1차원 정원 (C++)

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1치원 정원 문제는 나누기 연산으로 해결할 수 있습니다. 모든 꽃이 한 개 이상의 분무기에서 물을 받을 수 있도록 하기 위해서는 [x - D, x + D] 구간이 겹치지 않도록 물을 주면 됩니다. 1차원 정원이 [1, 2, 3, 4, 5]이고, D가 1인 경우, 첫 번째 분무기는 1번 인덱스에, 두 번째 분무기는 3이나 4번 인덱스에 두면 됩니다. 따라서 필요한 최소한의 분무기 수는 n / (D * 2 + 1)입니다. (D * 2 + 1은 분무기 하나가 물을 줄 수 있는 정원의 길이) 하지만, 만약 n이 (D * 2 + 1)로 나누어 떨어지지 않는 경우, 올..

[백준 1700번] 멀티탭 스케줄링 (C++)

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 멀티탭 스케줄링 문제는 그리디 알고리즘으로 해결할 수 있습니다. 콘센트에 꼽혀 있는 기기 중, 앞으로 사용하지 않거나, 가장 나중에 사용할 기기를 선택하여 현재 사용할 기기와 교체해주면됩니다. 증명은 어렵지만, 믿음으로 푼 문제입니다. 알고리즘의 기본 틀은 아래와 같습니다. 멀티탭의 구멍 개수가 기기의 총 사용횟수보다 작은 경우 0을 출력한다. 플러그를 뽑지 않아도 꽂을 수 있는 최대한의 개수를 ..

[백준 2170번] 선 긋기 (C++)

https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x n; for(int i = 0; i < n; i++) cin ..

[백준 1744번] 수 묶기 (C++)

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 수 묶기 문제에서 큰 값과 큰 값을 곱해주면, 합이 최대가 되도록 해줄 수 있습니다. 하지만, 입력으로 0 이하의 숫자들도 주어질 수 있습니다. 따라서 양수와 0 이하의 숫자를 구분할 필요가 있습니다. 알고리즘의 기본 틀은 아래와 같습니다. 양수와 음수를 구분하여 각각의 배열에 저장한다. 양수 배열(p)과 음수 배열(m)을 정렬한다. 양수 배열 p[i + 1]이 양수이면, p[i], p[i + ..

[백준 11501번] 주식 (C++)

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 주식 문제에서는 매일 3가지 행동 중 한 행동을 할 수 있습니다. 주식 하나를 산다. 원하는 만큼 가지고 있는 주식을 판다. 아무것도 안 한다. 아래와 같은 동작을 생각해볼 수 있습니다. (단, stock[d]는 d일의 주식 가격) stock[d] stock[d+1]이면, 주식을 판다. stock[d] == stock[d+..

[백준 2457번] 공주님의 정원 (C++)

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 공주님의 정원 문제는 회의실 배정과 유사한 문제로, 그리디 알고리즘을 이용하여 해결할 수 있습니다. 현재 피어 있는 꽃이 지기 전에 피고, 그 중 가장 늦게 지는 꽃을 선택하면 꽃을 최소의 개수로 선택할 수 있습니다. ⚠️ 주의할 점 빨리 피는 순으로 꽃을 정렬해야합니다. 현재 피어 있는 꽃이 지기 전에 피는 꽃이 없는 경우 0을 출력해야합니다. 3월 2일 이전에 피는 꽃이 없..

[백준 1026번] 보물 (C++)

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net S의 값을 가장 작게 만들기 위해서는 B의 i번째로 큰 값과 A의 i번째로 작은 값을 곱해주면 됩니다. 아래는 전체 코드입니다. #include using namespace std; int a[51], b[51]; bool cmp(int x, int y){return x > y;} int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >..

[백준 2217번] 로프 (C++)

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 로프 문제는 그리디 알고리즘을 이용하여 해결할 수 있습니다. 먼저, 버틸 수 있는 최대 중량이 가장 높은 로프부터 골라야 높은 중량의 물체를 들 수 있습니다. 따라서, 최대 중량을 기준으로 정렬을 수행해야합니다. n번째부터 i번째까지 로프를 선택했을 때, 들 수 있는 최대 중량은 Si * (n - i)입니다. (단, Si는 i번째 로프의 최대 중량) 왜냐하면 i번째 로프의 최대 중량이 가..