괴물 클럽

문제 설명 주厨 Marin은 n개의 고추를 가지고 요리를 만들 예정이다. 그는 나이가 x일 이하인 모든 고추로 요리 A를 만들고, 나머지 모든 고추로 요리 B를 만든다. 각 고추는 자신의 꿈을 가지고 있으며, 자신이 요리 A가 되고 싶은지 요리 B가 되고 싶은지 알고 있다. 하지만 고추들은 x의 값을 모른다. 꿈을 실현하는 고추의 수를 최대화하기 위해 다음과 같은 교환 ...

연결 리스트 전체를 역순으로 변환하기 문제 설명 단일 연결 리스트의 머리 노드 head가 주어졌을 때, 이를 역순으로 변환하고 변환된 연결 리스트를 반환하세요. 예시1: 생략 예시2: 생략 해결 방법 방법 1: 순차 처리 연결 리스트가 1→2→3→∅라고 가정해보겠습니다. 우리가 원하는 결과는 ∅←1←2←3입니다. 각 노드를 순회하면서 해당 노드의 다음(next) 포인터를 이전(prev ...

트리 체인 분할 개요 트리 체인 분할(Heavy Path Decomposition)은 트리 구조에서 효율적인 쿼리 처리를 위한 고급 자료구조 기법이다. 이 기법은 다음 네 가지 핵심 연산을 지원한다: 두 노드 x에서 y까지의 최단 경로상의 모든 노드에 값을 더한다 두 노드 x에서 y까지의 최단 경로상의 모든 노드 값의 합을 구한다 노드 x를 루트로 하는 서브트리의 모든 노드에 값을 ...

문제 접근 이 문제는 구간 내에서의 최대公约수(GCD) 값을 구하는 문제이다. 핵심 아이디어는 차분(difference) 배열을 활용하는 것이다. 원래 배열에서 인접한 요소들의 차이를 구하면, 해당 구간의 GCD는 차분 배열의 특정 구간 GCD와 동일해진다. 따라서 우리는 구간 GCD를 효율적으로 구할 수 있는 자료구조를 사용하면 된다. 두 가지 대표적인 방법을 소개한다. 방 ...

바이너리 인덱스 트리 1. 점 업데이트와 구간 합 查询 lowbit 함수 바이너리 인덱스 트리의 핵심은 lowbit 연산입니다: lowbit(x) = x & (-x) 이 연산은 x의 이진 표현에서 가장 오른쪽에 있는 1의 위치 값을 반환합니다. 예를 들어, x = (0010010011000)₂ 라면: -x = ~x + 1 = (1101101101000)₂ x & (-x) = (0000000001000)₂ 동작 원리 배열 a[1...n]이 ...

분할 정복 알고리즘 개요 배열 정렬을 위해 널리 사용되는 합병 정렬은 분할 정복(Divide and Conquer) 패러다임을 기반으로 합니다. 이 방식은 주어진 데이터를 작은 단위로 재귀적으로 쪼갠 후, 각 단위를 정렬된 상태로 다시 결합하여 전체 순서를 맞춥니다. 단계 1: 데이터 분할 로직 먼저 배열을 두 개의 하위 부분으로 나누는 과정을 정의합니다. 이때 중간 지점을 ...

문제 1: 일별 최대 작업 시간 최소화 (LCP 12) 특정 프로젝트 진행 시 전체 작업량을 $N$개의 과제들로 나누어 $M$일 동안 처리해야 하는 상황을 가정합니다. 각 과제에는 고유한 수행 시간이 존재하며, 반드시 순서대로 실행되어야 합니다. 다만, 매일 한 번씩 전문가의 도움을 받아 특정 과제의 소요 시간을 제로로 할 수 있는 기회가 주어집니다. 이 조건 하에서 $M$일 ...

대회 경향성 분석 및 난이도 평가 2022 년부터 2024 년까지 이어진 전국 본선 모의 훈련 문제들을 종합적으로 분석한 결과, 전반적인 난이도 흐름은 2022 > 2024 > 2023 순으로 예상된다. 출제 패턴을 살펴보면 대부분 초기 문제에 문자열 처리나 시뮬레이션 유형이 등장하며, 이후 완전 탐색, 자료구조 활용, 그래프 이론과 동적 계획법(DP) 결합 형태가 차례로 배치된다 ...

문제 설명 앨리스, 밥, 찰리가 카드 게임을 하고 있습니다. 각 플레이어는 각각 카드 더미를 가지고 있으며, 각 카드에는 문자 a, b, c 중 하나가 적혀 있습니다. 각 더미에 있는 카드의 순서는 변경할 수 없습니다. 플레이어들은 번갈아가며 턴을 진행합니다. 앨리스가 먼저 시작합니다. 현재 턴인 플레이어의 더미에 카드가 하나 이상 있으면, 가장 위에 있는 카드를 버 ...

체인 포워드 스타 클래스 (캡슐화 버전) struct ChainForwardStar { vector<int> head, to, next, weight; int edgeCount = 0; ChainForwardStar(int capacity) { head.assign(capacity + 1, -1); to.resize(capacity + 1); next.resize(capacity + 1); weight.resize(capacity + 1); } void connect ...