백준
-
9370, 삐빅-- 메모리 초괍니다(다익스트라로 최단경로 tree)백준 2022. 2. 4. 14:43
9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89..
-
2515, 골드 2백준 2021. 11. 11. 01:16
https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정 www.acmicpc.net 문제 폭이 같은 그림들을 $n$개 포개어놓는다 정면에서 봤을 때 보이는 높이가 $s$이상인 그림들의 값어치의 최대값을 구하라 풀이 그림을 정렬하고 dp 를 이용하여 구한다 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 32 33 34 35 36 37 38 39 40 41 42 43 4..
-
10999, Platinum 4백준 2021. 10. 8. 01:13
10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 빈번하게 변하는 배열의 구간합을 구하시오(변할 때 하나의 값이 아닌 구간으로 변한다) $O((m+k)log\ n)$ lazy propagation in segment tree which constrctive recursive function lazy propagation 의 핵심 아이디어는 갱신을 미리하지 말고 모았다가 (변화량은 lazy 배열에 저장해놓는다) 필요할 때 한꺼번에 하는것이다. ..
-
2042, Gold 1백준 2021. 10. 7. 01:16
2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 빈번하게 변하는 배열의 구간합을 구하시오 $O((m+k)log\ n)$ 세그먼트 트리(Segment tree)를 재귀함수로 구현한다 ※ 아래와 같이 구현할 때, 세그먼트 트리의 값을 담는 배열의 크기는 4*(다루는 숫자의 개수) def init( ) ~ seg_i 의 값을 리턴 1 2 3 4 5 6 7 8 9 ll init(int seg_i = 1, int arr_l = 1, int arr_r = ..
-
16236, Gold 4백준 2021. 10. 3. 14:20
16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 아기상어의 초기크기는 2, |본인| 마리수의 물고기를 먹으면 사이즈+1 먹을 수 있는 것 : |본인| > |물고기| 지나갈 수 있는 칸: |본인| ≥ |물고기| 먹이 우선순위 : 1. 거리가 가깝다 2. 위쪽에 있다 3. 왼쪽에 있다 풀이 가중치가 없는 그래프이므로 bfs 를 사용하면 된다. 이때 다음만 주의해주면 된다 움직이려는 칸이 좌표 유효? 0 ≤ row < n & 0 ≤ column < n 움직이려는 칸이 size 이하? 이때 아기상어 초기좌..
-
11286, Silver 1백준 2021. 10. 3. 01:54
11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 절댓값 힙을 구현하라 풀이 비교함수 연습문제 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 32 33 34 35 36 37 38 #include #define endl "\n" #define ooop(i, n) for(int i = 0; i me; } }; int main() { ios::sync_with_stdio(false); ci..
-
15589, Gold 1백준 2021. 10. 3. 01:40
15589번: Lifeguards (Silver) The first line of input contains $N$ ($1 \leq N \leq 100,000$). Each of the next $N$ lines describes a lifeguard in terms of two integers in the range $0 \ldots 1,000,000,000$, giving the starting and ending point of a lifeguard's shift. All such endpoints www.acmicpc.net 문제 $n(1\leq n \leq 10^{5})$명의 근로자가 각각 $[s_{i}, e_{i})$ 구간을 근무한다 누굴 해고해야 전체 근로시간이 가장 길까? 이때 근로시간은?..