AT2645 [ARC076D] 최소 의자 추가 문제
해결 방법 1
보조정리: 이분 그래프의 두 부분집합을 각각 X, Y(|X| ≤ |Y|)라고 할 때, 완벽한 매칭이 존재할 필요충분조건은 ∀S ⊆ X, f(S) ≥ |S| (여기서 f(S)는 S와 연결된 점들의 집합)이다. (즉, 홀의 정리)
문제에서 요구하는 것은 기본적으로 완벽한 매칭을 구성하기 위해 최소 몇 개의 의자를 추가해야 하는지를 묻고 있습니다.
따라서 모든 사람이 의자를 선택할 ...
7월 31일 18:34에 게시됨
큐 자료구조의 개념과 다양한 구현 방식
큐의 기본 원리
큐는 선형 데이터 구조 중 하나로, 삽입과 삭제가 양 끝에서 이루어지는 특성을 가집니다. 한쪽 끝(후단)에서 요소를 추가하고, 다른 쪽 끝(전단)에서 요소를 제거하는 방식을 따릅니다. 이는 선입선출(First In First Out, FIFO) 원칙에 기반하며, 가장 먼저 들어온 항목이 가장 먼저 처리되는 구조입니다.
이러한 특성 덕분에 큐는 작업 스케줄링, 메시 ...
7월 25일 09:20에 게시됨
로구 P2672 영업사원 문제 해결 (탐욕 알고리즘, 시뮬레이션)
해결 접근법
첫 번째 방법:
i번 가게를 선택하는 경우, 명백하게 a 값이 가장 큰 i-1개 가게는 반드시 선택해야 합니다. 따라서 마지막 가게 선택 방식만 고려하면 됩니다.
a 값이 i번째로 큰 가게를 선택하는 방법과, 남은 가게 중 s 값이 가장 큰 가게를 선택하는 방법 중에서 선택해야 합니다.
각 가게의 정보(s와 a)를 구조체에 저장한 후, a 값을 기준으로 내림차순으 ...
7월 8일 19:16에 게시됨
RMQ 문제 풀이: 슈퍼 피아노, 빈도 값, 인구 조사 문제
P2048 [NOI2010] 슈퍼 피아노
연속 부분 수열의 합을 전처리하고 RMQ를 사용하여 최대값을 찾습니다.
우선순위 큐를 사용하여 최적의 답을 저장합니다.
힙의 맨 위 요소를 꺼내서 계산한 후, 해당 지점을 제외하고 두 개의 새로운 구간을 다시 큐에 추가합니다. 이 과정을 k번 반복합니다.
#include <iostream>
#include <vector>
#include <queue>
#inc ...
7월 2일 00:21에 게시됨