알고리즘/백준 BOJ17 2217. 로프 그리디 문제이다. 1. 문제 풀이 2. Solution 1. 문제 풀이 필자는 로프 문제를 그리디로 해결했다. 필자가 생각해 낸 로프 문제의 탐욕법은 "정렬을 통해 k를 계산 + 각 로프당 들 수 있는 최소 중량을 이용하자" 이다. 예제 문제를 보면, 2개의 로프에 대해 각각 20, 25의 중량을 들 수 있다. -1개의 로프를 포함하는 경우: 최대 25 중량 가능 -2개의 로프를 포함하는 경우: 최대 40 중량 가능 단, 각 로프당 들 수 있는 최소 중량 = w/k (40중량/2개 = 20중량)을 만족해야 한다. 그렇기 때문에, 필자는 로프 문제를 해결하기 위해 1) 우선 로프가 들 수 있는 무게를 정렬 (오름차순 정렬) * 이때, 정렬을 안 하면, rope[i] MAX) ? w : MAX; } retu.. 2023. 1. 29. 11399. ATM 그리디 문제이다. 1. 문제 풀이 2. Solution 3. 알아야 할 개념 1. 문제 풀이 필자는 ATM 문제를 그리디 문제로 해결했다. ATM 문제에서 탐욕법은 "시간이 적게 걸리는 사람부터 ATM 사용하기" 이다. ATM 문제에서는 1번으로 ATM을 사용하는 사람이 N번 사용시간이 더해지고, 2번 사람은 N-1번 사용시간이 더해지고,,,, N번 사람은 1번 더해지기 때문이다. 2. Solution // 백준 11399 ATM #include #include #include using namespace std; int minTime(int N, vector& person) { // 시간이 적게 걸리는 사람이 앞으로 오도록 정렬 sort(person.begin(), person.end()); // 총 .. 2023. 1. 29. 2839. 설탕 배달 1. 올바른 풀이 2. 깔끔한 Solution 3. 나의 Solution 그리디 문제이다. (선택의 순간마다 당장의 눈 앞에 보이는 최적의 선택을 함) 1. 올바른 풀이 최소의 설탕봉지를 선택해야 한다. 필자는 이 문제를 해결하기 위해 "모든 경우의 수를 탐색해야 한다"에만 초점을 맞추어 잘못된 문제 풀이를 했다. 필자가 생각하는 올바른 문제 풀이는 "탐욕적으로 선택하기"이다. 그렇다면, 설탕봉지 문제에서 탐욕적인 선택은 "5kg 설탕봉지부터 가지기"이다. 예시로 30Kg 설탕봉지는 5kg 만으로 가져가면 6개의 설탕봉지를 배달하고, 3kg 만으로 가져가면 10개의 설탕봉지를 배달한다. 2. 깔끔한 Solution 알고리즘 문제를 풀 때, 깔끔한 코드를 보며 배우는 것은 중요하다고 생각한다. 아래의 코드.. 2023. 1. 29. 13398. 연속합2 1. 해결방법 Dynamic Programming DP[n] : n번째 수를 포함했을 때 연속합의 최대합을 의미. DP_left[n] : n번째 수를 포함했을 때 n 기준 왼쪽에 있는 연속합의 최대합을 의미. DP_right[n] : n번째 수를 포함했을 때 n 기준 오른쪽에 있는 연속합의 최대합을 의미. 문제의 조건에는 "수열에서 수를 하나 제거할 수 있다 (제거하지 않아도 된다)" 라고 하였기 때문에, n을 기준으로 왼쪽과 오른쪽에 있는 연속합을 더할 수 있다. DP_left[n - 1] + DP_right[n + 1] 수를 제거하지 않았을 때의 연속합의 최대합과, 수를 하나 제거했을 때의 연속합의 최대합을 비교하면 된다. 2. Solution #include #define MAX_ 100000 +.. 2022. 8. 20. 이전 1 2 3 4 5 다음
