알고리즘/백준 & swacademy108 BOJ 2532 - 먹이사슬 (LIS) https://www.acmicpc.net/problem/2532 각 요소마다 구간이 주어질 때, 어떤 구간이 한 구간을 완전 감쌀 수 있다면 먹이사슬 상 상하관계가 나뉜다고 한다. 가장 긴 먹이사슬의 크기를 구하라 priority queue를 이용해서 풀고자 했지만 잘 보이지 않는다. 2차원 평면에 그래프를 그려보면 형태가 눈에 보일 것. x값 증가, y값 감소하도록 {x,y}를 정렬한다면 y값들만 봤을 때 가장 긴 최장단조감소부분수열의 길이를 구하면된다. lower_bound대신 upper_bound를 쓰면 된다. (같은 구간은 빼주고 생각해야 함에 주의) int n; vector a; int main() { FAST; cin >> n; for (int i = 0,x,y,z; i < n; i++) {.. 2020. 5. 20. BOJ 14939 - 전구 끄기 (비트마스크, 그리디, 완탐) https://www.acmicpc.net/problem/14939 https://www.acmicpc.net/problem/14927 n*n그리드 위에 꺼진전구와 켜진 전구가 주어진다. 한 전구의 스위치를 누르면 주변4방향과 자기 자신의 상태가 변한다. 모든 전구를 끄기위해 최소 몇번 스위치를 눌러야 하는가? (n 2020. 5. 19. BOJ 2261 - 가장 가까운 두 점 (라인스위핑) https://www.acmicpc.net/problem/2261 https://www.acmicpc.net/blog/view/25 위 링크의 백준님이 설명해주신 방법 리뷰 좌표평면 위에 최대 n개의 좌표 x,y가 주어질 때, 가장 가까운 두 점의 거리의 제곱을 구해라 (n> p[i].first >> p[i].second; sort(p, p + n); ll st = 0, ans = 2e18; set cand; cand.insert(p[0]); for (ll i = 1,x,y; i ans) { cand.erase(p[st]); st++; } else.. 2020. 5. 19. BOJ 2568 - 전깃줄2 ( LIS, segtree ) www.acmicpc.net/problem/2568 pair로 입력받아 정렬후 second값의 LIS를 제외한 나머지의 first값 출력 위 점화식을 구간최대 세그트리를 이용해서 구하면 된다. 세그트리의 인덱스는 second값. const int MAX = 1e5 + 4; const int SMAX = (1 1) { i /= 2; seg[i] = max(seg[i * 2], seg[i * 2 + 1]); } } P val(int s, int e, int node, int ns, int ne) { if (e x >> y; a[i] = { x,y }; } sort(a + 1, a + n +.. 2020. 5. 14. 이전 1 2 3 4 5 6 7 ··· 27 다음
