백준 30976 - 사랑의 큐피드 (C++)
문제 문제 링크 BOJ 30976 - 사랑의 큐피드 문제 요약 $N$명의 여학생과 $M$명의 남학생에 대한 키 정보가 주어진다. 각 학생에 대한 선호 기준이 주어질 때, 성립될 수 있는 커플의 최대 수를 구해보자. 제한 TL : $1$ sec, ML : $512$ MB $1 ≤ N, M ≤ 400$ $1 ≤ G_i, B_i, L_i, U_i ≤ 300$ 한 학생이 둘 이상의 커플에 속할 수 없다. 알고리즘 분류 이분 매칭 (bipartite_matching) 풀이 여학생 집합과 남학생 집합은 서로 독립적이며, 간선은 서로 다른 집합에 대해서만 향할 수 있다. 즉, 문제의 조건대로 두 집합을 그래프로 모델링할 시 이 그래프는 반드시 이분 그래프의 형태를 띈다. 또한, $N, M ≤ 400$ 이고 최대 매칭..
백준 30943 - Zatopljenje (C++)
문제 문제 링크 BOJ 30943 - Zatopljenje 문제 요약 $N$개의 지점에 대해 $h_1, h_2, ... , h_N$이 주어진다. 아래 쿼리를 수행하는 프로그램을 작성해보자. $l$ $r$ $x$ : 해수면이 $x$까지 차올랐을 때, $[l, r]$에서 볼 수 있는 섬의 개수를 출력한다. 만약 인접한 섬이 모두 보인다면, 이는 하나로 쳐야 한다. 제한 TL : $2$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 200,000$ $0 ≤ h_i, x ≤ 10^9$ 알고리즘 분류 자료 구조(data_structures) 세그먼트 트리(segtree) 오프라인 쿼리(offline_queries) 풀이 온라인으로 풀기엔 좀 난감해 보인다. 쿼리를 순차적으로 처리할 때, $x$가 단조성..
백준 30512 - 조용히 완전히 영원히 (C++)
문제 문제 링크 BOJ 30512 - 조용히 완전히 영원히 문제 요약 길이 $N$의 수열 $A_1, A_2, ... , A_N$이 주어진다. 아래 쿼리가 $Q$개 주어질 때, $Q$개의 쿼리를 순서대로 처리한 후의 수열과 각 쿼리마다 잊힌 원소의 개수를 구해보자. $L$ $R$ $x$ : 모든 $L ≤ i ≤ R$에 대해 $A_i = min(A_i, x)$를 적용한다. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 100,000$ $0 ≤ A_i, x ≤ 1,000,000$ 알고리즘 분류 자료 구조 (data_structures) 세그먼트 트리 (segtree) 느리게 갱신되는 세그먼트 트리 (lazy_propagation) 풀이 구간 업데이트답게 무지성 $lazy$_$p..
백준 30515 - 방형구 탐색 (Hard) (C++)
문제 문제 링크 BOJ 30515 - 방형구 탐색 (Hard) 문제 요약 $1*N$ 크기의 격자에서, 각 칸에 피어있는 꽃의 종류 $A_1, A_2, ... , A_N$가 주어진다. 아래 두 쿼리를 수행하는 프로그램을 작성하자. $1$ $l$ $r$ $k$ : $[l, r]$에서 꽃의 종류가 $k$인 꽃의 개수를 출력한다. $2$ $l$ $r$ : $[l, r]$에 속한 모든 꽃들을 제거한다. 제한 TL : $1.5$ sec, ML : $1024$ MB $1 ≤ N, Q ≤ 200,000$ $1 ≤ A_i$$, k ≤ 10^9$ $1$번 쿼리는 하나 이상 주어진다. 알고리즘 분류 자료 구조 (data_structures) 트리를 사용한 집합과 맵 (tree_set) 풀이 $EASY$버전을 나이브하게 짜고..