전체 글
-
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 = ..
-
[python 3] 행렬 데이터 시각화아무거나적어~ 2021. 10. 3. 14:24
data_visualization.py 1 2 3 4 5 6 7 8 9 10 11 12 13 import sys import matplotlib.pyplot as plt f = open("data_visualization", 'r') data = f.read().split("\n\n") f.close() for fig_num, d in enumerate(data): d = list(map(lambda row: list(map(int, list(row))), d.split())) plt.figure(figsize=(5, 5)) plt.imshow(d) plt.show() plt.savefig(f"{fig_num}")cs data_visualization.txt 1 2 3 4 5 6 7 8 9 10 11 1..
-
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})$ 구간을 근무한다 누굴 해고해야 전체 근로시간이 가장 길까? 이때 근로시간은?..
-
2170, Gold 5백준 2021. 10. 3. 00:29
2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 문제 $n(1\leq n \leq 10^{6})$번 수직선 위의 구간 $[x, y], -10^{9}\leq x < y \leq 10^{9}$에 선분을 긋는다 그려진 선들의 길이의 합? $O(nlog\ n)$ 선분들을 정렬한 후 $O(nlog\ n)$ 선분들이 하나의 연속된 그룹(두 선분 사이에 빈틈이 없으면 연속이라 하자)인지 아닌지를 판단한다 $O(n)$ i) $s \leq r$이면 연속 ii) $r < s$이면 불연속 c++ 1 ..
-
16768, Gold 4백준 2021. 9. 21. 16:44
16768번: Mooyo Mooyo In the example above, if $K = 3$, then there is a connected region of size at least $K$ with color 1 and also one with color 2. Once these are simultaneously removed, the board temporarily looks like this: 0000000000 0000000300 0054000300 1054500030 220000 www.acmicpc.net 문제 같은 숫자가 $k$개 이상 인접하면 사라지고 아래로 내려온다. 최종 모습은? 풀이 ※ 마킹한 1은 미리 0으로 바꾸지 않는다(변화는 항상 마지막에) 화살표를 따라가다가 0을 만나면 열..
-
1283-C, *1500코드포스 2021. 9. 17. 00:35
Problem - C - Codeforces codeforces.com 문제 $n(2\leq n \leq 2\cdot 10^{5})$명의 사람을 차례대로 1, 2, 3, ... , n 이라고 하자 각각의 사람이 누구에게 선물을 주어졌는지 주어진다. 이때 0 은 아직 선물을 주지 않은 사람이다 선물을 아직 주지 않은 사람은 다음 조건을 만족하도록 선물을 주어야한다 1. 자기 자신에게는 주지 않는다 2. 모든 사람은 선물을 적어도 하나 받는다 위 조건을 만족하도록 선물을 주는 경우를 아무거나 출력하라 $O(n)$ 각각의 사람을 node, 선물을 주는 것을 edge 로 표현하여 위 문제를 graph 로 이해하자 그러면, 위 문제는 다음 조건을 만족시켜야 한다 1. 각각의 노드에서 뻗어나가는 edge 는 유일하..