2601번: 도서실카펫 (acmicpc.net) 2601번: 도서실카펫 모든 사각형의 좌표는 1,000,000 보다 작은 음이 아닌 정수이고 가로 세로의 길이는 1,000,000 보다 작은 양의 정수이다. 얼룩 직사각형은 서로 겹치지 않지만 접할 수는 있다. 얼룩 직사각형과 카펫 www.acmicpc.net 알고리즘 태그 : 레이지 세그먼트 트리, 스위핑 시간 복잡도 : \(O(NlogN+MlogM)\) 각 얼룩 마다 어디에 카펫을 설치할 경우 이 얼룩이 지워진다는 것을 직사각형 모양의 범위로 표현할 수 있다. 이제 이 범위들을 가지고 스위핑을 하며 구간 업뎃을 해서 각 업뎃이 끝났을 때 마다 전체 구간의 최댓값을 구해주면 된다. #include #define x first #define y second..
https://www.acmicpc.net/problem/17493 17493번: 동아리 홍보하기 1, 4, 7번 전봇대에 전단지를 붙이면, 모든 곳에서 전단지를 볼 수 있다. www.acmicpc.net 보통 저런 문제들이 트리 dp형태인데, dp테이블을 직관적으로 세워보자. \(dp[i][0] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드는 자식들 중 한 노드에 전단지가 붙여져있을 때, 최소 전단지 수 \(dp[i][1] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드에 전단지를 붙일때, 최소 전단지 수 \(dp[i][2] : \) \(i\)번 노드가 루트인 서브트리에서 \(i\)번 노드의 부모가 전단지가 붙여져있을 때, 최소 전단지 수 이렇게 \(dp\)식을 세..
https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net \(N\)개의 수를 그리디적으로 적절히 정렬할려고 한다. 어떤 두 수 \(A\), \(B\) 에 대해 \(AB\)랑 \(BA\) 중에 더 크게 되도록 정렬을 해주면 된다. 만약, \(AB\) > \(BA\) 라면 \(A\), \(B\) 순으로 정렬해주면 되고, 반대라면 \(B\), \(A\) 순으로 정렬해주면 된다. 자리수를 구할때 입력받은 수가 0인 경우에 0자..
- Total
- Today
- Yesterday
- 알고리즘 문제 풀이
- 누적 합
- AtCoder
- gunwookim
- DP
- 쿼리
- ABC
- codeforces
- Offline Dynamic Connectivity
- Rabin-Karp
- 앳코더
- 세그먼트 트리
- 비요뜨 존맛
- 비요뜨
- Constructive
- 수열과 쿼리
- 냄새 싫어
- 간단한 풀이
- BOJ
- 1909
- combination
- 오일러 경로
- hyper
- 하이퍼
- 스택
- 정렬
- PS
- 김춘배
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |