괴물 클럽

이원 정렬의 개념 알고리즘 문제 풀이 과정에서 두 가지 이상의 데이터를 묶어서 정렬해야 하는 상황을 자주 접하게 됩니다. 예를 들어, 길이가 $n$인 두 수열 $A = \{a_1, a_2, \dots, a_n\}$과 $B = \{b_1, b_2, \dots, b_n\}$이 주어졌을 때, 먼저 $a_i$를 기준으로 오름차순 정렬하고, $a_i$ 값이 같다면 $b_i$를 기준으로 다시 오름차순 정렬하는 방식입니다. 이를 C+ ...

1. 비수정 시퀀스 알고리즘 이러한 알고리즘은 작업 대상 컨테이너의 요소를 변경하지 않습니다. 1.1 find와 find_if find(begin, end, value): value와 동일한 첫 번째 요소를 찾아 반복자 반환 (못 찾으면 end 반환) find_if(begin, end, predicate): 조건자를 만족하는 첫 번째 요소 찾기 find_end(begin, end, sub_begin, sub_end): 하위 시퀀스가 마지막으로 나타나 ...

삽입 정렬은 정렬된 부분과 정렬되지 않은 부분으로 배열을 나누어, 정렬되지 않은 부분의 요소를 정렬된 부분의 적절한 위치에 '삽입'하는 방식의 알고리즘입니다. 1. 동작 원리와 루프 불변성 삽입 정렬의 핵심 아이디어는 루프 불변성(Loop Invariant)으로 설명할 수 있습니다. 길이 n인 배열 data에 대해, 인덱스 [0, i) 범위는 항상 정렬된 상태를 유지하며, 인덱스 ...

부제: 기본적인 수학 논리와 자료구조를 통한 효율적 설계 다음 내용은 특정 알고리즘 대회에서 자주 등장하는 4 가지 핵심 유형에 대한 접근법과 개선된 구현 예시를 다룹니다. 각 문제는 수학적 성질 검증, 그리디(Greedy) 할당, 해싱 기반 카운팅, 그리고 동적 계획법(DP) 과 재귀 탐색을 포함하고 있습니다. 1. 짝수 합분해 가능성 판정 목표: 주어진 양의 정수가 두 ...

부분합 차이 최소화 문제 주어진 배열에서 연속된 부분 수열의 합 차이를 최소화하고, 해당 조건을 만족하는 최대 길이를 찾는 문제입니다. O(n2) 복잡도의 단순 접근법은 모든 부분 수열을 계산하여 해결합니다. 최적화된 접근법은 다음과 같습니다: 배열의 누적 합을 계산 누적 합을 값 기준으로 정렬 (값이 동일할 경우 인덱스 내림차순) 인접한 누적 합 간의 차 ...

BIT(페니크 트리) 개요 BIT(Binary Indexed Tree)는 구간 합을 빠르게 계산하고, 특정 인덱스의 값을 업데이트할 수 있는 자료구조입니다. lowbit 연산을 기반으로 하여 시간 복잡도 O(log N)을 보장합니다. P3374: 기본적인 BIT 연산 단일 값 갱신과 구간 합을 처리하는 가장 기초적인 템플릿 문제입니다. #include <bits/stdc++.h> using namespace std; int n ...

柠檬水找零 문제 입력과 응답 시나리오가 고정된 문제의 경우, 단순하게 구현하면 된다. class Solution { public: bool lemonadeChange(vector<int>& bills) { unordered_map cash; for(int i = 0;i < bills.size();i++){ int change = bills[i] - 5; if(change == 0){ cash[bills[i]]++; ...

좌표 데이터 표준화의 필요성 지리 정보 시스템 (GIS) 및 항해 분야에서는 위치 데이터를 처리할 때 일관된 좌표 체계가 필수적입니다. 역사적으로 경도와 위도는 도 (Degree), 분 (Minute), 초 (Second) 로 구성되는 DMS(度分秒) 형식으로 표기되어 왔습니다. 그러나 컴퓨팅 환경과 수치 연산의 효율성을 고려할 때, 소수점을 포함한 십진법 도 (Decimal Degree, DD) 형식 ...

문제 링크: https://codeforces.com/contest/1118 A 문제: 문제 설명: q 번의 쿼리가 주어지며, 각 쿼리마다 숫자 n 이 주어집니다. 숫자 1 과 2 를 사용하여 n 을 만들되, 1 의 비용은 a이고 2 의 비용은 b입니다. 최소 비용을 구하세요. 해결 방법: 만약 2a <= b라면 모두 1로 구성하는 것이 가장 유리합니다. 반면에 2a > b라면, n이 홀수라면 하나의 1과 나머지 ...

문제 정의 무게 제한이 있는 배낭과 여러 개의 아이템이 주어졌을 때, 각 아이템은 고유한 무게와 가치를 가집니다. 한 번에 하나의 아이템만 선택할 수 있으며, 배낭의 총 무게가 허용 범위를 넘지 않도록 하면서 담을 수 있는 아이템들의 총 가치를 최대화하는 것이 목표입니다. 예시: 아이템 개수: 3개 각 아이템의 무게: [1, 3, 4] 각 아이템의 가치: [15, 20, ...