yeongminb의 PS 블로그

BOJ 2517. 달리기segment tree, coordinate compression 보자마자 세그먼트 트리가 떠올라야하는 문제이다. 어떤 선수의 최소 등수는 $($그 선수 앞에 있는 선수들 중 그 선수보다 실력이 좋은 선수들 명수$) + 1$ 등이 된다. 그래서 앞에서 부터 segment tree에 업데이트 해주며 계산해주면 된다. 또한 선수들 실력의 절대적인 값은 중요하지 않으므로 좌표 압축을 해주어야한다. 시간복잡도는 $O(N\log{}{N})$이다.더보기#include #define fastio cin.tie(0)->ios::sync_with_stdio(0);using namespace std;const int NMAX = 5e5;int N;vector skill_level, cmp;struc..

CodeForces Raif Round 1. Carrots for Rabbitspriority queue, math, greedy priority queue를 사용하는 문제 치고는 좀 까다로운 문제였다. 처음 이 문제를 접근할 때에는 당근을 잘랐을 때 자른 당근의 길이채로 배열에 저장하려고 했었는데 그냥 2개로만 나눠지는 게 아니라 $n$ 개로 나눠질 수도 있기 때문에 나중 상황을 고려하지 못하게 된다. 그래서 그냥 당근은 그 길이대로 저장해되 그 당근을 현재까지 몇 개로 나눴는지를 저장하기로 하였다. 그래서 총 나눈 개수가 K개가 될 때 종료해주면 된다. 그럼 어떤 당근을 잘라야할지를 정해야한다. 그 기준을 '현재 상태에서 1번 더 나누었을 떄 시간이 얼마나 더 줄어드는가'로 하였다. 나눠지는 횟수가 ..

KOI 2024. 이진트리dp, math 문제는 상당히 어렵고 복잡할 것 같이 만들어놓고 풀어보면 진짜 별거없는 사기 문제이다. 그냥 $S(T)$ 들 간에 관계식을 잘 세워주면 풀린다.  $T$의 왼쪽 자식의 서브트리를 $T_l$, 오른쪽 자식의 서브트리를 $T_r$이라고 하자. 또 T에 대해 T의 리프노드 개수가 $n$ 개일 때 $R(T) := \sum_{i=1}^{n}f(i,n)$, 그리고 $L(T) := \sum_{i=1}^{n}f(1,i)$로 정의하자. 일단 $S(T) = S(T_l) + S(T_r) + leafNum(T_l)\times L(T_r) + leafNum(T_r)\times R(T_l) - 1$ 임을 알 수 있다. $($설명하기에는 조금 복잡한데 대충 왼쪽만 쓸 때, 오른쪽만 쓸 때,..

학원에서 수업시간에 딴짓$($?$)$을 하다 학원 벽에 '주어진 삼각형을 유한개의 오목사각형으로 채울 수 있을까?'라는 문장이 무려 '낙서'로 써져있는 것을 봤다. 못 채울 것이라는 생각을 가지고 몇 번 그림을 그려보니 정말 채워지지 않았다. '오 이거 증명해봐야겠다!'라는 충동을 느끼고 학원에서 증명해보았다. 생각보다 잘 증명한 것 같아서 여기에 남겨보았다.   주요 아이디어는 삼각형에만 국한하지 않고 일반적인 볼록다각형에 대해서 채울 수 있는지를 확인하는 것이었다. 삼각형은 항상 볼록하므로 일반적인 볼록다각형에 대해서 불가능하다는 것을 증명하는 것으로 충분하다. 그래서 오목사각형으로 이루어진 도형이 오목할 수 밖에 없다는 것을 증명하였다.  Proposition 1) 임의의 오목다각형에 오목사각형을 ..

CodeForces Round 364 $($Div. 1$)$. Connecting Universitiesdfs, dp 구현은 아주 간단하나 아이디어가 좀 필요했던 문제이다. $N\leq 2\times 10^5$ 이라서 적어도 $O(N\log{}{N})$이하의 풀이가 필요하다.  두 점 사이에 거리를 구하는데만 해도 dfs로 $O(N)$이나 걸리는데 최대 $\frac{N}{2}$ 쌍에 대해서 거리를 구하려고 하면 $O(N^2)$이기에 다른 방법이 필요했다. 그래서 더블카운팅 형식으로 세주려고 했다. 모든 간선들에 대해서 그 간선이 쓰일 수 있는 최대 횟수를 더해주면 그게 정답이 된다. 그 어떤 간선 $E = \left\{V,U\right\}$ 쓰일 수 있는 최대 횟수는 $V$방향 서브트리에 존재하는 대학의..

USACO 2024 December. 2D Conveyor Beltdfs, bfs, offline query $N \leq 10^3, Q\leq 10^5$일 때 $N\times N$ 격자에서 처리해야하므로 처음에 $O(N^2)$이하로 unusable한 conveyor belt들을 모두 계산해두고 $Q$개의 쿼리동안 $O(1)$안에 답을 계산해 출력하는 $O(N^2 + Q)$를 목표로 생각했다. 그래서 먼저 dfs를 잘 이용해 최종상태에서 unusable여부를 미리 계산을 해두었다. 계산을 해두고 보니 처음 상태에서 추가를 하는 것보다 최종상태에서 하나씩 빼는 것이 더 쉬울 것이라고 생각했다. 하나를 뺄 때 그 칸이 unusable->usable로 바뀐다면 그와 인접한 칸들만 탐색해주면 되고 수정한 칸들은..

문제 링크 문제 풀이 어떤 정점 $n\leq 21$개, 간선 $m$개의 그래프 위에 원숭이가 살고 있고, 매 턴마다 인접한 정점으로 항상 움직인다. 이때 매턴마다 그래프 위에 정점 하나를 골랐을 때 최악의 경우에도 언젠가는 원숭이를 잡을 수 있는지를 묻는 문제이다. 또 잡을 때까지의 최소 몇 번의 턴이 필요한지와 가능한 실례도 제시해야한다.   일단 문제를 보자마자 생각할 수 있는 것은 가능하기 위해서는 당연하게 이 그래프가 사이클이 없는 트리여야한다는 것이다. 만약 사이클이 있다면 그 사이클 위에 있는 원숭이는 매턴마다 두 가지의 선택지가 반드시 존재하므로 원숭이를 유인할 수 없다. 이는 직관적으로도 자명하다. 따라서 $m$이 $n-1$이 아닐 경우에는 볼 필요가 없어진다.  처음에는 트리인 경우는 모..

CSES. Stick Divisionspriority queue, greedy 입력으로 최종 상태의 분할 방법이 주어져있어서 분할하는 것보다 합치는 것으로 생각하는게 훨씬 편함. 길이 $l_1,l_2$인 두 막대를 합친다고 생각할 때 비용은 $l_1+l_2$이며 결과적으로 모든 막대를 합쳐야함. 이때 $N\leq 2\times 10^5$라서 $O(N\log_{}{N})$ 풀이가 필요함. 조금만 생각해보면 매순간마다 가장 작은 길이의 두 막대를 합치는 것이 비용적으로 최소임. 합치는 턴마다 막대가 1개씩 줄어드므로 $N$번 반복하면 되고 이때 최소인 두개를 찾는 것은 priority queue를 이용하면 $O(\log{}{N})$만에 할 수 있음. 더보기#include #define fastio cin.t..

CSES. Bit Inversions  set by hasing, data structure  $x_1$부터 $x_n$까지 중에 $x_i \neq x_{i-1}$인 $i$들을 저장해서 $i_{0}, ... , i_{k}$라고 하자 $($단, $i$중에는 0과 $n$은 반드시 포함해서 $i_{0} = 0, i_{k} = n$임$)$. 그럼 우리가 구하고자 하는 정답은 아래처럼 표현됨. $$\max_{1\leq j \leq k}{(i_j -i_{j-1})}$$ 이걸 $log$시간 안에 처리할 수 있기만 하면 $O(m\log{n})$에 가능. 이를 위해 set을 이용할 수 있음. 각 쿼리마다 업데이트 할 때 자신의 인덱스나 자신 - 1의 인덱스가 이미 set 안에 들어 있다면 제거 후 인덱스 끼리의 차를 업데..

Codeforces Round 179 Div. 1.  Greg And Array  prefix sum 아무 생각없이 각 쿼리마다 게속 업데이트 해주려고 하면 $O(mk + mn)$이 걸려서 $m,n,k \leq 10^5$인 범위에서 시간초과가 남. 따라서 연산이 사용되는 개수를 구하는 것과 연산을 통해 숫자를 변화시키는 것  각각 $O(m+k), O(m+n)$과 같이 바꿔줘야함. 이때 먼저 구간의 시작과 $($끝+1$)$에 각각 원하는 값을 미리 더해주고 나중에 누적 합을 해주어 처리하면 가능해짐.더보기#include using namespace std;typedef long long ll;typedef pair pii;const int nmax = 1e5, mmax = 1e5; struct operat..

비트마스크 알고리즘 $(Bit Mask)$은 0,1로만 이루어진 이진수를 사용하여 집합과 같은 자료구조를 표현하는 알고리즘이다.  AND연산이나 OR, XOR과 같이 기본연산만 사용하기 때문에 대부분 $O(1)$ 으로 구현되어 시간적으로도 효율적이고, 배열을 사용하지 않기 때문에 메모리 측면에서도 효율적이다.  1. 기본 연산 비트마스크에 사용되는 대표적인 기본 연산자는 AND$(\space \& \space)$, OR$(\space | \space)$, XOR$(\space \sim \space)$ , NOT$(\space \wedge \space)$, Shift$(\space  1) AND -> 모두 1일 때만 1AND10110000 2) OR -> 1이 존재하면 1OR10111010 3) XOR -..

문제 링크 문제 풀이 이 문제는 어떤 양의 실수$\leq 10^9$들의 합에 대한 정보와 곱에 대한 정보가 주어질 때 이 수들의 개수로 가능한 최솟값을 출력하는 문제이다. 합과 곱이 주어졌으므로 산술기하 평균 부등식 AM-GM inequality 을 떠올릴 수 있다. 이 실수들의 합, 곱, 개수를 각각 $S, P, N$이라 할 때 다음이 성립한다.$$S \leq N\sqrt[N]{P}$$$$\Rightarrow P \leq (\frac{S}{N})^N$$  따라서 이를 만족하는 $N$의 최솟값을 찾으면 된다. 이때 불가능한 경우를 따지기 위해 $f(N) = (\frac{S}{N})^N$로 두고 미분하여 최댓값을 찾아야한다.$$(\ln_{}{f(N)})^{\prime}=\frac{f^{\prime}(N)}..

kaggle 사이트에서 competitions 카테고리를 보다가 "House Prices - Advanced Regression Techniques" 이라는 제목을 봤는데 뭔가 재미있어 보여서 연습도 할겸 시도해보았다. 문제는 train set로 여러 집들의 세부사항과  그 판매 가격이 주어질 때 적절한 모델을 통해 이를 학습 시켜 test set에 있는 집들의 세부사항으로 그 가격들을 모두 예측하는 것이다. 이때 집들의 세부사항은 무려 80개나 주어진다. 주어지는 세부 사항들의 예시는 아래와 같다.○ MSSubClass: The building class○ MSZoning: The general zoning classification○ LotFrontage: Linear feet of street co..

문제 링크 문제 풀이  이 문제는 $m\leq 500$ 개의 $10^8$ 이하의 숫자와 $k\leq m$ 이 주어질 때 $m$개의 숫자를 $k$개의 집합을 나누어 그 집합들의 합의 최대가 최소가 되도록 하는 문제이다. 이때 같은 집합에 포함되려면 그 수들이 모두 연속해야하며 원소에 개수가 1개 이상이어야한다. 예를 들어 9개의 수 100, 200, 300, 400, 500, 600, 700, 800, 900을 3개의 집합으로 나눈다고 할 때 100,200,300,400,500 / 600,700 / 800,900 으로 나눠야 최대합이 1700으로 최소가 된다. 참고로 나누는 방법이 여러개인 경우는 앞쪽의 집합의 원소의 개수가 가장 작을 때를 출력해야한다.  일단 $m,k$의 범위가 작아서 백트랙킹을 해야하..

문제 링크 문제 풀이 이 문제는 $4\times 4$ 크기의 그리드에 글자들이 적혀져 있을 때 이 글자들을 이어 만들 수 있는 단어들을 찾는 문제이다. 이때 찾은 단어의 길이에 따라 점수가 주어져 점수가 최대로 되도록 하게 찾기도 해야한다. 주어지는 단어의 개수는 $w \leq 3\times 10^5$이고 단어의 길이는 최대 8이다.  일단 칸의 개수가 16개로 매우 작은 편이기 때문에 DFS로 완전탐색 할 생각을 할 수 있다. 모든 칸에서 최대 $4^8$번 탐색을 하므로 연산 횟수는 $2^{20}$을 넘지 않는다. 그래서 그냥 완전탐색을 하며 중복만 잘 처리해주면 되는 아주 쉬운 문제이다. 참고로 실행시간 절약을 위해 주어진 단어들을 해시 맵 형태로 저장하였다.  코드#include #include #..

문제 링크 문제 풀이 이 문제는 정점의 개수 $N \leq 200$ 이고 간선의 개수 $M \leq 20000$ 인 그래프에서 특정한 정점에 불을 붙여 모든 정점과 모든 간선이 불에 탈 때까지 걸리는 최소시간을 출력하는 문제이다. 어떤 정점에 불이 붙으면  그와 연결된 모든 간선으로 불이 퍼져나간다. 이때 이 간선이 모두 불타는데 걸리는 시간은 그 간선의 길이와 같다. 또한 간선의 양쪽 정점에 모두 불이 붙은 경우는 두 불이 퍼져나가다 만나면 그 간선이 모두 불탄 것이다. 참고로 간선 중에는 양 끝 점이 모두 동일하게 한 정점인 간선도 있다.  처음 한 생각은 일단 모든 정점으로부터 모든 정점까지 최소 거리를 저장하는 것이다. 그렇게 되면 어떤 정점으로부터 불이 시작될 때 어떤 간선이 불에 타서 없어질 ..

문제 링크 문제 풀이 이 문제는 어떤 0과 1로만 구성된 문자열이 주어질 때 그 문자열의 서로 다를 필요는 없는 부분 문자열끼리 XOR연산을 한 값의 최댓값을 출력하는 문제이다. 여러개의 테스트 케이스로 주어지고, 이때 주어지는 모든 문자열의 길이의 합은 $10^7$을 넘지않아서 $O(N)$풀이가 필요하다.   문제를 처음봤을 때 아이디어가 바로 떠올라서 플레4보단 쉽다고 느꼈는데, 구현을 해볼 수록 고려해야할 게 많다는 것을 깨달았다. 생각한 아이디어는 앞의 나오는 자릿수 중에 1이 많으면 좋으므로, 처음에 나오는 연속한 1들과 그 다음 나오는 0들을 XOR하는 것이었다. 예를 들어 11100010이라는 문자열이 주어지면 11100010과 11100을 XOR하여 앞의 0들을 모두 1로 만들어주어 숫자를..

경기과학고등학교 수학 브릿지 프로그램으로 수리창의문제해결 프로젝트라는 것을 하길래 문제를 풀어보았다. 1차 문제로 2개가 있었는데 하나는 사고력$(?)$을 요하는 증명 문제였고 나머지 하나는 경우의 수를 세는 기하문제였다. 이 기간동안 몸이 좀 아파서 집에만 있었는데 친구들 풀이 읽고 문제 풀고 하는게 재미있어서 이것만 했었다 ㅎㅎ  P1.  이 문제에는 어떤 한 열쇠 구멍을 돌릴 때, 그 열쇠 구명과 같은 열, 같은 행에 있는 모든 열쇠 구멍도 똑같이 돌아가지는 이상한 금고가 나온다. 이 금고에서 모든 구멍이 바닥과 수평인 방향의 모양으로 바꾸어 금고를 열 수 있는지 증명하는 문제이다.    처음에 친구들이 불가능하다고 증명을 해놨었는데 친구들의 풀이를 다 읽어보니까 공통적인 오류가 보였다. 그래서 열..

문제 링크 문제 풀이 이 문제는 $K \leq 50$개의 자연수 중에서 $N\space\space(K \leq N \leq 50)$개의 자연수를 중복을 허용하고 뽑아 이어붙였을 때 만들어질 수 있는 가장 큰 수를 출력하는 문제이다. 이 때 주어진 K개의 자연수 모두 적어도 한 번씩은 사용되어야한다.   이 문제를 접근할 때 두 가지를 고려하였다. 첫 번째는 주어지는 각 숫자의 사용 개수이고, 두 번째는 숫자들의 사용 순서이다. 먼저 각 숫자의 사용 개수는 당연히 자릿수가 가장 많은 숫자를 많이 사용하는 것이 유리하다. 왜냐하면 자릿수가 많을수록 숫자가 커지기 때문이다. 그래서 자릿수가 가장 큰 숫자를 $N-K$번 사용하고 나머지를 1번씩만 사용할 생각을 하였다. 만약 자릿수가 가장 큰 숫자가 2개 이상이..

문제 링크  문제 풀이 이 문제는 Hilbert Curve 모양의 미로에서 시작점까지의 거리가 주어질 때 그 위치의 좌표를 구하는 문제이다. 입력은 $n \leq 2^{15}$ 와 $m \leq n^2$ 이 주어지는데 $n$은 미로의 크기, $m$은 구하고자 하는 점의 시작점으로부터의 거리이다.   Hilbert Curve가 재귀적으로 정의되는 모양이다보니까 이 문제도 재귀적으로 풀어야겠다는 생각을 했다. 이 때 미로를 $\frac{n}{2}$ 크기의 네 구역으로 나누어서 분할정복 알고리즘으로 플 수 있다고 생각했다. 그래서 먼저 좌표를 반환해주는 함수를 다음과 같이 정의해보자.//pair : 크기 k인 미로에서 거리 d인 점의 좌표pair calcCoord(int k, int d)먼저 구하고자 하는 점..

SCC는 모든 정점에서부터 모든 정점까지로의 경로가 존재하는 그래프를 의미한다. 주어진 그래프에서 SCC들을 찾아내는 알고리즘은 타잔 알고리즘과 코사라주 알고리즘이 있다. 아직 정확히는 모르지만 타잔 알고리즘이 더 활용도가 높다고 하므로 타잔 알고리즘을 공부했다.  1) 타잔 알고리즘의 동작기본 원리는 dfs와 같다. 어떤 정점에서 시작해 dfs를 하는데 방문하는 정점마다 서로 다른 idx를 부여한다.  dfs 결과 자기 자신의 idx가 나온다면 cycle(SCC)가 존재한다는 것을 알 수 있다. 2) 타잔 알고리즘의 구현구현은 dfs와 stack을 이용하여 한다.1> dfsint v, e, id;int d[MAX];int sccNum; int sn[MAX]; vector a[MAX];bool finis..

문제 링크 문제 풀이 이 문제는 $1$부터 $N \leq 10^9$까지의 수에서 등장하는 0 ~ 9의 개수를 출력하는 문제이다. 문제 자체는 쉽지만 TLE가 나지 않게 구현을 하려고 하면 조금 까다로운 문제이다.  기본적인 아이디어는 $N$을 각 자리수에 따라 나누어 더블카운팅의 형식으로 세는 것이다. 예를 들어서 $N = 223$이라고 하면 $N$을 200, 20, 3으로 나누어서 0~199까지의 각 자리수의 개수, 0~19까지의 각 자리수의 개수, 0~3까지의 각 자리수의 개수를 따로 세주어 더하는 형식이다. 여기서 0~199까지의 각 자리수의 개수와 같은 경우는 또 0~99, 100~199로 나누어서 생각해볼 수 있다. 10의 거듭제곱 단위로 나뉘기 때문에 이에 대한 정보만 미리 저장해둔다면 빠른 ..

문제 링크  문제 풀이 이 문제는 $N \leq 1.5\times 10^6$일 동안 상담을 하는데 각 상담마다의 걸리는 시간과 얻을 수 있는 금액이 주어질 때 얻을 수 있는 최대 금액을 출력하는 문제이다. 상담을 하는 기간이 서로 겹치면 동시에 할 수 없기 때문에 적절한 상담들만 선택해주어야 한다.   문제를 보자마자 DP가 떠올랐다. 그런데 시작 날짜를 기준으로 DP를 하면 망할 것이 뻔히 보이기 때문에 상담 종료 날짜를 기준으로 DP를 할 생각을 쉽게 할 수 있다. 그러기 위해서 종료 날짜를 기준으로  각 상담들을 정렬해주고 상담의 시작날짜와 종료날짜를 이용해 선분처럼 표현하면 라인 스위핑을 하면서 DP를 해주면 풀릴 것이다.  점화식을 다음과 같이 정의하자. $dp[i] := (i$일 까지 상담을 ..

문제 링크  문제 풀이 이 문제는 $N \leq 10^{5}$개의 행성의 좌표 $x,y,z$가 주어지고 두 행성 $A(x_{A},y_{A},z_{A})$와 $B(x_{B},y_{B},z_{B})$ 의 거리가 $min(|x_{A}-x_{B}|,\space |y_{A}-y_{B}|,\space |z_{A}-z_{B}|)$로 정의될 때 모든 행성들을 연결하는 경로의 최소 길이를 구하는 문제이다.  처음 보자마자 당연하게 MST를 구해야겠다는 생각이 떠오른다. 그런데 MST를 구하는 Kruskal Algorithm을 쓰려고 하면 모든 간선의 개수가 ${N \choose 2}$개이므로 MLE랑 TLE가 날 수밖에 없다. 그래서 간선을 되도록 조금만 저장하는 방향으로 생각해볼 수 있다.  어짜피 MST에 포함되는 ..

Segment Tree는 어떤 배열에서 구간에 관한 정보를 저장해 놓는 자료구조이다. 누적합 배열을 사용할 때에는 $O(N)$으로 비교적 빠르긴 하지만 배열의 원소를 교체할 때에도 $O(N)$이므로 원소를 교체하는 쿼리가 많이 주어지는 경우에는 시간초과가 나기 쉽다.  반면에 Segment Tree는 이진트리의 형태의 자료구조이므로, 원소 교체나 구간합을 구할 때의 시간복잡도가 $O(logN)$으로 매우 빠르다. 1. Segment Tree의 구조  위 그림은 {1,9,3,8,4,5,5,9,10,3,4,5}라는 배열에 대한 구간합을 저장한 'Segment Tree'를 나타낸 것이다. 이진트리 형식으로 구성되어있으며 어떤 노드에 적혀 있는 숫자는 자식 노드들의 적혀 있는 숫자들의 합이라는 것을 알 수 있다..

문제 링크 문제 풀이 이 문제는 $N\leq 3\times 10^5$개의 보석과 $K\leq 3\times 10^5$개의 가방이 주어지고, 각 보석의 무게 $M_{i}$, 가격 $V_{i}$와 가방에 담을 수 있는 최대 무게 $C_{i}$가 주어질 때 담을 수 있는 보석의 최대 가격을 출력하는 문제이다.   일단 당연히 최대 가격을 얻기 위해선 보석들 중 가격이 높은 순서대로 가방에 넣는 것을 시도해야 한다. 그래서 그리디 알고리즘으로 생각해보면 가격이 높은 보석들부터 가방에 넣는데, 그 가방의 무게는 보석의 무게를 넘는 최소의 무게(lower bound)일 수록 좋을 것이다. 만약 만족하는 가방이 없거나 이미 보석을 넣은 상태라면 넣지 못할 것이다. 이렇게 생각하면 일단 보석에 대해 iteration을..

KMO 2차에 수열 관련해서 수학적 귀납법으로 증명하는 문제가 많이 보이는 것 같아서 가장 대표적인 수열인 피보나치 수열에 대해 정리해보려고 한다. PS에서도 자주 나오니까 도움이 될 것 같다.   2023 중캠 2차 3번 (AOPS링크) Math Message Boards FAQ & Community Help | AoPSSomething appears to not have loaded correctly.artofproblemsolving.com  피보나치 수열 관련된 문제로 이런 문제가 있는데, $a_{n} = 4{F_{2n-1}}^2 + {F_{2n}}^2$임을 증명하는 (더러운)문제이다. (솔직히 사람이 이걸 어떻게 생각하는지 모르겠다)  정의피보나치 수열은 자연수 $n$에 대해 아래와 같이 정의된..

$FTC$는 Fundamental Theorem of Calculus(미적분학의 기본 정리)로 미적분을 배운다면 알 수밖에 없는 가장 기본적인 정리이다. 나중에 증명과정이 필요할 수도 있기 때문에 증명과정을 정리해보겠다. $F.T.C.\space1)$ 구간 $[a,b]$에서 연속인 $f(x)$와 $F(x) = \int_{a}^{x} f(t)dt$ 에 대해 다음이 성립한다. $$F^{\prime}(x) = f(x)\space\space (x\in [a,b]) $$ p.f) $$F^{\prime}(x)=\lim_{h→0}\frac{F(x+h)−F(x)}{h}$$$$=\lim_{h→0}\frac{\int_{a}^{x+h}f(t)dt-\int_{a}^{x}f(t)dt}{h}$$$$=\lim_{h→0}\frac{..

문제 링크  문제 풀이  이 문제는 수직선 위에서 가로등의 위치들이 주어질 때 각 수직선 상의 위치마다 밝기를 작은 것부터 $K \leqslant 3\times 10^5$개 출력하는 문제이다.   일단 $ L \leqslant 10^{18} $ 이므로 배열에 각 위치들을 배열에 저장하거나, 완전탐색을 할 경우 MLE나 TLE가 날 수밖에 없다. 그래서 필요한 위치들의 밝기만 저장하거나 다른 방법이 필요하다.  가장 처음에 생각했던 것은 인접한 가로등 사이의 구간 길이를 저장하는 것이다. 구간의 길이의 개수는 항상 $N+1$개이고, $N \leqslant 3\times 10^{5} $ 이기 때문에 완전탐색을 해도 별 문제가 없고, 구간의 길이가 각 위치들의 밝기를 특정해주기 때문이다. 예를 들어서 구간의 ..

Topolgy Sort(위상 정렬)는 유향그래프에서 정점들의 순서를 정할 때 사용하는 알고리즘이다. 유향그래프에서 진입차수를 기준으로 쉽게 구현할 수 있다. 1) 위상 정렬의 동작위상정렬은 다음과 같이 동작한다.1) 진입차수가 0인 노드 선택한다.2) 1)의 노드와 연결된 모든 노드들의 진입차수를 1씩 뺀다.3) 1)의 과정을 반복한다. 2) 위상 정렬의 구현 진입 차수가 0인 노드들을 queue에 넣음으로써 구현한다. void topology(){ queue q; for(int i=1;i 여기서 $inDegree$ 배열은 각 노드들의 진입차수를 저장하는 배열이고, result는 위상정렬 결과 노드들의 순서를 저장하는 벡터이다.