꾸준함

문제 링크입니다: https://algospot.com/judge/problem/read/STRJOIN 허프만 코드와 비슷한 개념으로 문제를 풀면 됩니다.(https://ko.wikipedia.org/wiki/%ED%97%88%ED%94%84%EB%A7%8C_%EB%B6%80%ED%98%B8%ED%99%94) 허프만 코드는 출현빈도가 높은 문자를 트리 상단에 배치하는데 이 문제에서는 출현빈도 대신 문자열의 길이가 길수록 트리 상단에 배치하면 됩니다.예를 들어 두 번째 테스트 케이스를 그림으로 표현해봤습니다.원 안에 있는 숫자들이 초기에 입력된 문자열의 길이이고, 네모가 합쳤을 때 드는 비용입니다.즉, 네모를 모두 합치면(2+5+7+12) 문자열을 합치는데 드는 최소 비용(26)이 나옵니다. /* n개의 ..

문제 링크입니다: https://algospot.com/judge/problem/read/LUNCHBOX데우는 시간은 상관이 없고 먹는 시간이 식사시간을 좌지우지한다는 것이 핵심이였습니다. /* 유명한 도시락 업체에서 n개의 도시락을 주문했다. 주문량이 많아서 한가지 도시락만 주문할 수는 없었기 때문에 여러가지 종류의 도시락을 주문했다. 하지만 전자레인지는 하나뿐이고 출력량도 적어 한번에 한 도시락만 데울 수 있다. 이 때, 식사시간을 최소화 하려면 어떻게 해야할까? */ #include #include #include using namespace std; const int MAX = 10000; //boxNum> test_case; if (test_case 300) exi..

문제 링크입니다: https://www.acmicpc.net/problem/4587codewars의 Some Egyptian fractions(http://jaimemin.tistory.com/395?category=987931) 문제를 푼 다음 비슷한 문제가 있어서 풀어봤습니다.직접 테스트 케이스를 입력하고 컴파일을 하면 맞게 나오는데 어디가 틀린건지 도무지 모르겠습니다.혹시 틀린 부분이 있다면 댓글을 통해 알려주시면 정말 감사하겠습니다! #include #include #include using namespace std; const int MAX = 1000000; vector v; //최대공약수long long int gcd(long long int N, long long int D) //great..

문제 링크입니다: https://www.codewars.com/kata/54f8693ea58bce689100065f/train/cpp이집트 분수는 일반 분수를 분자가 1인 분수들의 합으로 표현합니다.예를 들어 4/5=1/2+1/4+1/20으로 표현됩니다.상당히 흥미로운 주제인데도 불구하고 처음 접했기 때문에 개념이 상당히 어렵게 느껴졌는데 다행히 이에 대해 잘 설명된 포스팅이 있었기 때문에 프로그램을 쉽게 작성할 수 있었습니다.https://en.wikipedia.org/wiki/Egyptian_fraction denominator) //분자가 분모보다 큰 경우(대분수로 만듬) { result += to_string(numerator / denominator); numerator %= denominato..

문제 링크입니다: http://www.codewars.com/kata/5277c8a221e209d3f6000b56/train/cpp왼쪽 괄호들을 스택에 넣고 오른쪽과 스택의 탑을 비교하는 것이 핵심이였습니다. /* 괄호, 중괄호, 대괄호를 문자열로 받고 맞는 순서로 입력받았는지 판별하시오 */ #include #include #include using namespace std; bool ifLeft(char ch) //왼쪽 괄호 여부 { if (ch == '(' || ch == '{' || ch == '[') return true; return false; } bool match(char left, char right) //왼쪽 괄호와 오른쪽 괄호 동일한지 비교 { if (left == '('&&righ..

http://jaimemin.tistory.com/391?category=988050과 비슷한 문제입니다.두가지 다른 점은 다음과 같습니다.1. 백준 1931번 문제와 달리 한 회의의 소요시간은 1 이상이고2. 한 회의의 끝과 그 다음 회의의 시작은 동일할 수 없다는 점입니다.(이런 경우 겹친다고 여긴다.) 물론 탐욕법(greedy method)를 사용하면 쉽게 풀리지만 동적계획법을 연습 중이기 때문에 동적계획법으로도 풀어봤습니다. /* 회사에 회의실이 하나밖에 없는데, n(0; i--) for(int j=i-1; j>0; j--) if (meeting[i].start > meeting[j].end) { before[i] = j; break; } } int schedule(int idx) { if (id..

문제 링크입니다: https://algospot.com/judge/problem/read/MATCHORDERN의 범위가 1~100이기 때문에 완전탐색법과 동적계획법을 사용하면 시간초과가 발생하는 문제였습니다.따라서 탐욕 알고리즘을 사용하여 프로그램을 작성했습니다. #include #include #include #include using namespace std; int order(const vector &russian, const vector &korean) { int length = russian.size(), wins = 0; //아직 남아 있는 선수들의 레이팅 multiset ratings(korean.begin(), korean.end()); //성적 순 정렬 for (int rus = 0; r..

문제 링크입니다: https://www.acmicpc.net/problem/1931탐욕법(greedy method)을 이용하여 푸는 문제였습니다. /* 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. */ #include #include #include using namespace std; int N..

문제 링크입니다: https://www.acmicpc.net/problem/11052'(i-j)개 세트 팔았을 때 최대값 + j개 세트 가격' 이 부분이 핵심이였습니다. /* 강남역에서 붕어빵 장사를 하고 있는 해빈이는 지금 붕어빵이 N개 남았다. 해빈이는 적절히 붕어빵 세트 메뉴를 구성해서 붕어빵을 팔아서 얻을 수 있는 수익을 최대로 만드려고 한다. 붕어빵 세트 메뉴는 붕어빵을 묶어서 파는 것을 의미하고, 세트 메뉴의 가격은 이미 정해져 있다. 붕어빵 i개로 이루어진 세트 메뉴의 가격은 Pi 원이다. 붕어빵이 4개 남아 있고, 1개 팔 때의 가격이 1, 2개는 5, 3개는 6, 4개는 7인 경우에 해빈이가 얻을 수 있는 최대 수익은 10원이다. 2개, 2개로 붕어빵을 팔면 되기 때문이다. 1개 팔 때의..

문제 링크입니다: https://www.acmicpc.net/problem/1010이 문제의 핵심은 서쪽의 첫번째 사이트가 연결한 다리를 고정으로 놓고 부분문제로 나누는 것이였습니다.테스트 케이스를 입력 받고 그만큼 반복해서 답을 도출해야하기 때문에 미리 모든 경우의 수를 계산해놓고 결과를 출력하는 형식으로 코드를 작성했습니다. /* 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 ..