기록공간

우선, 로프들을 오름차순으로 정렬한 후, 그리디 알고리즘을 이용하여 풀면된다. O(n^2)를 사용하면 시간초과가 나므로 이점을 유의해서 풀어야한다. 정렬 후에 할일은 다음과 같다. 배열 가장 처음에 위치하는 가장 길이가 짧은 로프는 모든 로프의 길이보다 작거나 같으므로 개수는 배열의 크기와 같다. 분기를 타며 길이가 길어질수록 로프의 개수를 하나씩 줄여나가면서 들 수 있는 중량을 구해주면된다. 이전에 저장된 들 수 있는 중량보다 현재 계산한 중량이 더 크다면 그 값으로 덮어쓴다. 코드는 다음과 같다. #include #include using namespace std; bool cmp(int a, int b) { return a > inpu..

그리디 알고리즘은 탐욕 알고리즘이라고도 불린다. 그리디 알고리즘은 커다란 문제를 해결하기 위해 여러 단계를 나누어 해결하는 알고리즘의 하나이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간의 최적이라고 생각되는 것을 선택해 나가는 알고리즘이다. 하지만 그리디 알고리즘을 적용할 수 있는 예는 많지 않다. 코딩이 쉽고, 구현이 쉬운건 사실이지만, 그리디 알고리즘으로 구한게 항상 최적을 보장하는 경우는 거의 없기 때문이다. 만약에 사탕을 당장 받으면 1개만 받지만, 1분을 기다리면 2개를 받을 수 있다고 하자. 이런 경우 그리디 알고리즘을 사용하면 사탕을 1개 받는 것을 선택한다. 그래서 보통 '근사치 추정'을 위해 그리디 알고리즘을 사용한다. 적용 가능한 예 Prim Algorithm, Kruskal ..

회의 시간에 대한 문제는 그리디 알고리즘의 대표적인 문제라고 한다. 회의 시간이 끝나는 시간을 기준으로 정렬 한 후, 현재 기준에서 가능한 회의 가장 회의가 빨리 끝나는 것을 고르면 된다. 끝나는 시간이 같은 경우가 있을 수 있는데 (6, 8) (8, 8) 이러한 경우이다. 이런 경우를 고려하여 정렬을 해줘야 한다. 만약 끝나는 시간이 같다면 시작시간을 기준으로 정렬해주면 된다. 회의 시간 정렬이 끝나면, 맨 처음 시작 시간을 기준으로 차례대로 카운트 해나가면 원하는 값을 구할 수 있다. 코드는 다음과 같다. 벡터를 이용하여 회의 시간을 담아 정렬을 하였다. #include #include #include using namespace std; struct Time { int begin; int end; ..

동전의 가치가 가장 높은 것 부터 순차적으로 내려가면서 K보다 가치가 작았을때 그 가치만큼의 동전의 개수를 구해 (나눠주고) 최종값에 더해주고 나머지 값이 있으면 아직 동전을 충분히 채우지 못했으므로 반복해주면 된다. 4200원 동전의 가치 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000 [1] 50000 -> 10000 -> ... -> 1000(알맞는값) 4200 / 1000 = 4개 4200 - (1000 * 4) = 200원 [2] 1000 -> 500 -> 100(알맞는값) 200 / 100 = 2개 200 - (200 * 2) = 0원(분기 종료) [최종] 4개 + 2개 = 6개 #include using namespace std; int main() {..

정렬을 할 줄 안다면 정말 쉬운 문제이다. 시간의 합이 최소가 되기 위해서는 각 사람이 돈을 인출하는데 필요한 시간을 오름차순으로 정렬하면 된다. 정렬 전 [3 1 4 3 2] 3 3 + 1 = 4 3 + 1 + 4 = 8 3 + 1 + 4 + 3 = 11 3 + 1 + 4 + 3 + 2 = 13 3 + 4 + 8 + 11 + 13 = 39 정렬 후 [1 2 3 3 4] 1 1 + 2 = 3 1 + 2 + 3 = 6 1 + 2 + 3 + 3 = 9 1 + 2 + 3 + 3 + 4 + 13 1 + 3 + 6 + 9 + 13 = 32 #include #include using namespace std; int main() { int personCount = 0; int* personTime = nullptr..

#include using namespace std; class CStar { public: CStar(){ } ~CStar() { if (m_ppArr) { for (int i = 0; i < m_nCount; ++i) { if (m_ppArr[i]) { delete[] m_ppArr[i]; m_ppArr[i] = nullptr; } } delete[] m_ppArr; m_ppArr = nullptr; } } public: int GetCount() { return m_nCount; } public: void Solve(int x, int y, int num) { if (num == 1) { m_ppArr[x][y] = '*'; return; } int divide = num / 3; for (int ..

#include #include using namespace std; class CHanoi { public: int GetCount() { return m_nCount; } public: void InputCount() { cin >> m_nCount; } void Solve(int circleCount, int from, int by, int to) { if (circleCount == 1) { Move(from, to); } else { // 1번째에서 3번째를 거쳐 2번째로 n-1만큼 옮긴다. // 나머지 하나를 1번쨰에서 3번째로 옮긴다. // 2번째에 있는 n-1개를 1번째를 거쳐 3번째로 옮긴다. Solve(circleCount - 1, from, to, by); Move(from, to);..