백준 31222 - 수열과 어렵지 않은 쿼리 (C++)
문제 문제 링크 BOJ 31222 - 수열과 어렵지 않은 쿼리 문제 요약 길이 $n$의 수열 $A_1, A_2, ... , A_n$에 대해 임의의 연속 부분 수열 $[a_l, a_{l+1}, ... , a_{r-1}, a_r]$에서 모든 원소가 서로 일치할 때, 이러한 구간 $[l, r]$을 '연속 일치 구간'이라고 한다. 또한 임의의 연속 일치 구간이 수열의 다른 연속 일치 구간에도 완전히 포함되지 않는다면 이를 '중요한 연속 일치 구간'이라고 한다. 이때, 아래 쿼리를 수행하는 프로그램을 작성하자. $1$ $i$ $x$ : $A_i$의 값을 $x$로 변경한다. $(1 ≤ i, x ≤ n)$ $2$ $l$ $r$ : $[l, r]$에서 서로 다른 중..
백준 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$가 단조성..