https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 우선 세그먼트 트리를 이용해야 되는데, 구간의 업데이트가 있으므로 이를 효과적으로 수행하기 위해 느리게 갱신되는 세그먼트 트리 사용한다는 것을 알 수 있다. 주의해야 될 점이, 세그먼트 트리를 사용할 때, 쉽게 생각할 수 있는 방법처럼 위치마다 별의 개수를 저장하는 배열의 세그먼트 트리는, 별들이 공차가 1일 등차수열 형식으로 별들이 증가하므로, 효과적인 구..

https://www.acmicpc.net/problem/18780 18780번: Timeline Session two occurred at least five days after session one, so it cannot have occurred before day $1+5=6.$ Session four occurred at least two days after session two, so it cannot have occurred before day $6+2=8$. www.acmicpc.net 세션 사이의 관계를 그래프로 만들고, 그래프를 위상정렬 하며 배열 s에 s[세션 번호] = 해당 세션이 최소 며칠 이후에 일어나는지를 저장해 나아가는 방법으로 문제를 해결했다. 코드 #include #inc..

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 사건 사이의 관계 그래프를 2차원 배열로 표시하여, 플로이드 와샬을 통해 각 지점에서 도달할 수 있는 지점을 체크해 문제를 해결했다. 코드 #include #include #include using namespace std; int n, k; int adj[405][405]; int s; vector result; void pre() { for (int i = 0; i < 405; i++)..

https://www.acmicpc.net/problem/1396 1396번: 크루스칼의 공 첫째 줄에는 그래프의 정점의 개수 n과 간선의 개수 m이 주어진다. 그리고 두 번째 줄에서 m+1번째 줄까지는 a b c의 형태로 a와 b를 연결하는 간선의 고유값이 c라는 의미이다. m+2번째 줄에는 알고 www.acmicpc.net 문제에 대한 접근은, 간선을 가중치 순으로 정렬하고 각 쿼리에 대해 어떠한 간선까지 합쳤을 때, 쿼리의 출발지에서 목적지까지 가는지 이분 탐색을 통해 구할 수 있다. 출발지에서 목적지까지 갈 수 있는지 여부는, 유니온 파인드에서 출발지와 목적지가 같은 그룹이 되는지 확인하는 방법을 이용했다. 하지만 쿼리가 많아, 각 쿼리마다 하나씩 진행하지 않고 병렬 이분 탐색을 이용해서 문제를 ..

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 꽃의 날짜 순으로 정렬한 뒤, 해당 순서로 확인하며, 3월 1일부터 11월 30일까지 범위를 앞에서부터 채워 나가며 꽃을 고르는데, 앞에서부터 채우는 꽃을 고를 때, 가능한 꽃이 지는 날짜가 긴 것을 고르도록 그리디 하게 접근하여 문제를 해결했다. 코드 #include #include #include using namespace std; int n; int month_day_s..

https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 구간의 왼쪽 끝점에 +1, 구간의 오른쪽 끝점에 -1을 표시하여 이를 누적합을 수행하여, 구간을 나타내었고, 이를 기반으로 투 포인터를 이용해, 투 포인터의 범위의 합이 k가 되는 경우를 확인하는 방법으로 문제를 해결했다. 코드 #include #include #include using namespace std; int n, k; int chec..