olrlobt

https://www.acmicpc.net/problem/2293 🔒 골드5 - #2293 동전 1 📌 테스트케이스 추가 힌트 4 10 1 2 5 3 = 20 ✍️ 풀이법 대표적인 DP 문제이다. DP 문제를 풀 때, 가장 먼저 고려해야 할 것은 캐싱을 통한 점화식 도출이다. 캐싱을 위해 DP 테이블을 그려보면, 가로축에 K원이 되기 위한 가치를 나열할 수 있다. 그리고 세로축에 동전을 하나씩 추가하며 문제를 해결해 보자. 먼저 1원짜리 동전을 추가한다. 1원짜리 동전으로 1원을 만들던, 2원을 만들던, 3원을 만들던... 값은 모두 1이 되므로 1로 채워지게 된다. 또한, 0원을 만드는 경우도 { x } 동전을 선택하지 않는 경우 1가지로 생각할 수 있다. 다음으로 2원짜리 동전을 추가한다. 2원짜리 ..

🔒 골드5 - #12865 평범한 배낭 📌 테스트케이스 추가 힌트 5 7 6 13 4 8 3 6 5 12 2 7 = 19 ✍️ 풀이법 대표적인 DP (다이나믹 프로그래밍) 문제이다. DP 문제를 해결해야할때, 가장 먼저 고려해야 하는 것은 캐싱을 통한 점화식 생성이다. 먼저 값을 저장할 DP 테이블 만든다. 가로축은 들 수 있는 무게를 의미하며, 세로축에는 차례대로 물건의 무게와 가치를 입력한다. 먼저 첫번째 물건인, 무게 6에 가치 13의 물건이 들어가게 되면, 무게 6까지는 들 수 없으므로 DP (캐시)에 6부터 채워지게 된다. 이후, 두번째 물건인 무게 4에 가치 8의 물건이 들어가게 되면, 마찬가지로 무게 4까지는 들 수 없으므로 이 전 값인 0을 가져오게 된다. 이후, 4부터는 두 번째 물건을 ..

동적계획법 : 다이나믹 프로그래밍 DP (Dynamic programming) DP는 하나의 큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 알고리즘 기법이다. DP에서 동적계획법, 동적프로그래밍이라는 단어는, DP 창시자가 그냥 멋있는 단어를 붙인 것이라고 한다. 따라서 크게 의미를 부여하거나 찾아볼 필요는 없다. 하나의 문제를 작은 문제로 나누어 해결하는 방식은 분할정복 알고리즘과 비슷하다고 생각할 수 있다. 분할정복 알고리즘의 경우는 단순히 큰 문제를 작게 나누어 해결하는 방식에 불과하지만, DP의 경우는 작은 문제를 풀고 값을 저장하여, 중복된 계산 자체를 없애버린다. 예를 들어 피보나치 수열을 보자. 피보나치 수열은 재귀함수로, f(n) = f(n-1) + f(n-2) 의 형태를 띈다. 이때 계..

탐욕법 : 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘 (Greedy Algorithm)이란 여러 가지 선택지 중에서 지금 이 순간 최적이라고 생각되는 것을 선택하는 알고리즘이다. 지금 당장 최선의 선택을 하므로, 정답을 항상 구할 수는 없다. 하지만, 그리디 알고리즘 자체가 최적의 해를 구하는 것이 아니라, 상대적으로 최적의 해에 가까울 수 있는 해를 구하는 알고리즘이다. 예를 들어, 아래 그림과 같이 Start에서 층을 내려가면서 숫자의 최댓값을 구하는 문제가 있다고 하자. Start에서 시작을 했을 때, 5와 10중에 최댓값에 더 최적화된 선택지는 10이 된다. 그리고 그다음 선택지인, 1과 2중에 최댓값에 더 최적화된 선택지는 2가 되므로, 위 문제를 그리디 알고리즘으로 해결..

🔒 골드5 - #1461 도서관 📌 테스트케이스 추가 힌트 5 2 1 2 3 4 5 = 13 5 2 -45 -26 -18 -9 -4 = 89 5 3 -45 -26 -18 -9 -4 = 63 ✍️ 풀이법 해당 문제는, 문제를 이해하기와 테스트케이스가 풀어지는 과정을 구하는 것이 다소 어려웠다. 당연히 2개씩 책을 들고 간다면, 끝부터 차례로 2개씩 놓으면 된다고 생각을 했는데 답이 도출되지 않았고, 중간에 책을 놓고 가는 경우를 생각 해보니 답이 도출되었지만, 식을 세우기 어려웠다. 따라서 다시 답이 도출되는 과정을 생각해 보고 문제를 해결하였다. 내가 생각한 답이 도출되는 과정은 한 칸씩 전진하는 방법이다. 한칸씩 움직이면서, 해당 방향에 있는 모든 책들을 옮기는 방식으로 진행하면된다. 위의 테스트케이스..

https://www.acmicpc.net/problem/13164 🔒 골드5 - #13164 행복 유치원 📌 테스트케이스 추가 힌트 4 2 1 4 5 6 = 2 ✍️ 풀이법 한 조에서, 가장 큰 사람과 가장 작은 사람의 차이는 각 조원의 키의 차이의 합과 같다. 예로, 위의 예시를 보면 조는 1 / 4, 5, 6 두 개로 나누어지고 두번째 조에서 비용은 (4와 5의 차이) + (5와 6의 차이) 와 같다. 따라서 조를 나눌때는, 키 차이가 가장 큰 순으로 조를 나누어야 한다. 위 예시에서는 조를 2개로 나누었으므로, 조원 사이의 거리중 가장 큰 값을 한 개만큼 (= K-1) 지운다. 풀이방법: 1. 다음 사람과의 키 차이를 구한다. 2. 키 차이에서 큰 값부터 K-1 번째까지를 모두 제외하고 모두 더한..

🔒 골드3 - #13904 과제 📌 테스트케이스 추가 힌트 4 1 10 3 30 3 30 3 40 = 100 ✍️ 풀이법 문제는 정말 간단했다고 생각한다. 마감일부터 거꾸로 진행을 하고, 최대값부터 하나씩 빼 주는 방식으로 해결하였다. 위 테스트 케이스로 설명을 하자면, 3일에 수행 가능한 과제 = ( 30 , 30 , 40) / 40 수행 2일에 수행 가능한 과제 = ( 30, 30) / 30 수행 1일에 수행 가능한 과제 = ( 30 , 10) / 30 수행 = 100 풀이 방법: 1. 마감일 수의 최대값부터 해당 날에만 수행 가능한 과제를 수행 가능 리스트에 추가한다. 2. 수행 가능 리스트에서 최대값을 제거하고, 최종 점수에 더한다. 3. 최대값에서 1을 뺀 후, 위 과정을 반복한다. 🗝️ 풀이 ..

🔒 골드4 - #1715 카드 정렬하기 📌 테스트케이스 추가 힌트 5 10 20 10 10 40 = 190 4 10 10 10 30 = 110 ✍️ 풀이법 해당 문제는 이해했다고 생각해도 헷갈리는 경우가 많았던 것 같다. 테스트 케이스를 세우고 문제를 풀 때, 더한 값들을 한 번씩 쓰면서 다 합친 이후. 쓴 값들을 다 더해주어야 답이 나오게 된다는 점을 알고 진행하면, 이해하기 편할 것 같다. 첫 번째 케이스를 예로 들자면, 90이 나오는 과정에서 모든 카드가 합쳐지게 된다. 이 후, 파란 값 ( 더한 과정에서 나온 값) 들을 다 합치면 원하는 정답 190 이 나오게 된다. 이 문제는 토너먼트 방식을 사용하려하거나, 리그 방식을 사용하려고 하면 안 된다. 왜냐하면, 가장 작은 카드 뭉치부터 뭉쳐주어야, ..