개발일지

문제설명 입출력 예제 개념 각 로프는 고유한 중량 한계를 가지고 있으며 이를 초과할 수 없다. 이때 로프 2개가 각각 10kg, 15kg을 버틸 수 있다고 하면, 10kg 한 개를 쓸 땐 10kg, 15kg 한 개를 쓸 땐 15kg, 10kg과 15kg을 함께 쓰면 각 로프가 10kg씩 버틸 수 있으므로 20kg를 버틸 수 있다. 이러한 특징에 착안하여 로프들을 강도에 따라 정렬하여 가장 강한 로프부터 시작하여 점점 약한 로프를 추가하며, 각 단계에서의 최대 중량을 계산할 수 있다. 이때 로프들 중 일부만을 선택해야 할 경우도 고려해야 한다. 예를 들어, 10, 20, 30, 40, 50kg을 버틸 수 있는 로프 5개가 있다고 가정해 보자. 1. 50kg: 50kg 2. 50kg, 40kg: 40 + 4..

sort vs stable_sort 개요 데이터를 정렬할 때 동일한 값들이 존재하는 경우가 발생할 수 있다. 이때, 우리가 사용하는 일반적인 정렬 알고리즘은 동일한 값들의 순서를 보장하지 않아서, 정렬 후의 순서가 원래의 순서와 다를 수 있다. 예를 들어, 이름으로 사람들을 정렬한 후, 나이로 다시 정렬하면 나이가 같은 사람들의 상대적인 순서가 정렬된 후에 변경될 수 있다. 본문 C++ 표준 라이브러리에는 정렬 함수로서 std::sort()와 std::stable_sort()가 존재한다. 이 두 함수는 기본적으로 배열 또는 벡터의 시작과 끝 위치를 인자로 받으며, 선택적으로 비교 함수를 추가하여 사용할 수 있다. 둘 모두 시간 복잡도는 평균적으로 O(n log n)으로, 대략적으로 n log n 번의 비..

문제설명 입출력 예제 개념 원본 수열에서 정렬을 적용한 후, 각 원소가 원래 있던 위치에서 어떤 위치로 이동하였는지 확인하는 문제다. 즉, 원본 수열의 원소들이 정렬된 후의 위치 값을 찾는 문제다. 유의해야 할 점은, 중복된 원소의 값을 처리하는 것이다. 이는 동일한 원소의 경우 원본 수열에서 사전순으로 앞서는 것을 출력해야 한다는 것을 의미한다. 따라서 각 원소의 값을 그 원소의 원래 위치와 함께 저장하는 pair 자료형을 사용하여 해결할 수 있다. 또한, 오름차순을 정렬할 때 정렬 후에 동일한 값의 원소들 사이의 상대적인 순서를 유지하기 위해 stable_sort를 사용해야 한다. 풀이 #include #include #include using namespace std; bool custom(pair..

문제 설명 제한 사항 및 입출력 예제 개념 주어진 배열에서 k개를 선택하는 방법 중 종류를 가장 적게 고르는 방법을 구하는 문제다. 배열을 내림차순으로 정렬하고, 가장 많은 개수를 가진 귤의 크기부터 선택하여 바구니에 담는 그리디 알고리즘을 채택하여 문제를 효율적으로 해결할 수 있다. 풀이 #include #include #include #include using namespace std; int solution(int k, vector tangerine) { int answer = 0, sum = 0; map m; for (const auto& val : tangerine) m[val]++; 주어진 벡터에 있는 원소들의 개수를 파악하기 위해 map 자료구조를 활용하였다. 이때 맵은 귤의 크기를 키로 하..

문제설명 입출력 예제 개념 올림픽에서 메달 획득 별 등수를 출력하는 문제다. 올림픽 메달 순위에서는 동점의 경우 같은 등수를 가지며, 그다음 등수는 동점인 나라의 수를 고려하여 건너뛰게 된다. 예를 들어, 금메달 수가 1개인 나라가 1등에 2개가 있다면, 그다음 나라는 3등이 된다. 이러한 동점 상황을 고려하여 문제를 풀면 해결할 수 있다. 풀이 #include #include #include using namespace std; struct medal { int _id, _gold, _silver, _bronze; bool operator > (const medal& m) const { if (_gold != m._gold) return _gold > m._gold; else if (_silver !=..

문제 설명 제한 사항 및 입출력 예제 개념 주어진 정수 벡터에서 모든 숫자의 조합 중 가장 큰 수를 찾는 문제다. 다음과 같은 조건을 고려해 보자. 숫자의 순서: 수를 이루는 각 숫자들의 배치 순서를 문자열로 바꾸어 정렬 숫자의 자릿수: 두 숫자가 주어졌을 때, 자릿수가 다르다면 두 숫자의 문자열로 바꾼 후 이어 붙였을 때 큰 방향을 확인 따라서 정렬 기준을 두 문자열을 더했을 때 큰 쪽을 리턴하게 새롭게 정의하면 된다. 풀이 #include #include using namespace std; string solution(vector numbers) { string answer = ""; vector v; 정답을 저장할 문자열 answer와 벡터 v를 초기화한다. for (const auto& val ..

문제 설명 제한 사항 및 입출력 예제 개념 두 수열 A와 B의 각 원소를 한 번씩 곱한 값을 더했을 때, 그 합이 최소가 되도록 만드는 문제다. 즉, 한 수열에서 최솟값을 다른 수열에서의 최댓값과 곱하는 과정을 반복하여 합을 최소화하는 것이 목표다. 이를 구현하는 방법은 여러 가지가 있다. 풀이 (1) multiset 활용 #include #include using namespace std; int solution(vector A, vector B) { int answer = 0; multiset ms1(A.begin(), A.end()), ms2(B.begin(), B.end()); while (!ms1.empty()) { answer += (*ms1.begin() * *ms2.rbegin()); ms..

문제설명 입출력 예제 개념 단어를 길이를 기준으로 정렬하는 문제다. std::sort에 비교 구문을 추가하여 해결하면 쉽게 해결할 수 있다. 풀이 #include #include #include int main() { int N; std::cin >> N; std::vector v; while (N--) { std::string str; std::cin >> str; v.push_back(str); } 단어의 개수 N을 초기화하고, 문자열을 넣을 벡터 v를 초기화해 준다. struct { bool operator() (std::string a, std::string b) const { if (a.size() == b.size()) return a < b; return (a.size() < b.size()..