개발일지

문제설명 입출력 예제 개념 각 로프는 고유한 중량 한계를 가지고 있으며 이를 초과할 수 없다. 이때 로프 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 ..

문제설명 입출력 예제 개념 주어진 문자열을 빈도수 → 길이순 → 알파벳 순으로 정렬하는 문제다. 자료구조 맵을 이용해 특정 길이 이상의 문자열을 빈도수와 함께 컨테이너에 저장한 후, 주어진 조건에 맞게 정렬하면 문제를 해결할 수 있다. 풀이 #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; string str; map m; cin >> N >> M; 영단어의 개수 N, 외울 단어의 길이 기준 M, 영단어 문자열 str, 단어를 저장할 컨테이너 m을 초기화한다. while (N--) { cin >> str; if (str.size(..

문제설명 입출력 예제 개념 문자열 S에 대해 서로 다른 부분 문자열의 개수를 구하는 문제다. 여기서 연속된 일부분이라는 것에 주목해야 한다. 즉, S의 길이가 1인 부분 문자열은 a, b, a, b, c가 되고, 여기서 서로 다른 부분 문자열은 a, b, c S의 길이가 2인 부분 문자열은 ab, ba, ab, bc가 되고, 여기서 서로 다른 부분 문자열은 ab, ba, bc S의 길이가 3인 부분 문자열은 aba, bab, abc가 되고, 여기서 서로 다른 부분 문자열은 aba, bab, abc S의 길이가 4인 부분 문자열은 abab, babc가 되고, 여기서 서로 다른 부분 문자열은 abab, babc S의 길이가 5인 부분 문자열은 ababc가 되고, 여기서 서로 다른 부분 문자열은 ababc 따..

문제설명 입출력 예제 개념 집합 A와 B가 주어졌을 때 (A - B) ∪ (B - A)의 값을 구하는 문제다. 자료구조 map을 이용해서 푸는 방법도 있지만, 필자는 조금 다르게 풀었다. 두 집합의 원소를 벡터에 삽입 교집합을 이진 탐색을 이용하여 정수형 변수에 삽입 벡터의 크기에서 교집합의 원소의 차를 출력 풀이 #include #include #include int main() { int N, M, n, count = 0; std::cin >> N >> M; std::vector v(N + M); 집합 A, B의 원소의 개수 N, M, 입력받을 숫자 n, 교집합의 수 count를 초기화해준다. 그리고 N + M의 크기를 가지는 벡터 v를 초기화해 준다. for (int i = 0; i < N; i++..

문제설명 입출력 예제 개념 M개의 카드 중에 N개의 숫자 카드와 같은 것이 몇 개 있는지 출력하는 문제다. map 자료 구조에 저장하여 개수를 출력하면 시간 초과 문제에 걸리게 되는데, 이는 map 자료구조는 연산이 O(logN)의 시간 복잡도를 가지기 때문이다. 즉, M개의 숫자를 하나씩 확인할 때마다 시간 복잡도가 O((N+M) logN)이 되므로 다른 방법을 찾아야 한다. 따라서 시간 복잡도를 줄이는 과정이 필요한데, 이진 탐색을 이용한 std::upper_bound() 함수와 std::lower_bound() 함수를 사용하거나 map의 멤버 함수인 find() 함수와 반복자를 적절하게 이용하면 해결할 수 있다. 풀이 (1) map #include #include #include int main()..