푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 기본적인 위상 정렬 문제이고 문제에서 주어진 "가능하면 쉬운 문제부터 풀어야 한다"의 조건을 주의해야 합니다. 문제의 숫자가 높아질수록 난이도가 올라가므로 우선순위 큐를 오름차순으로 정렬해서 큐를 돌려주면 됩니다. ✏️ 문제 코드 #include #include #include using namespace std; ve..

✏️ 문제 링크 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 위상 정렬로 접근해서 푸는 문제 일반적인 위상정렬로 구현하고 큐를 탐색하는 과정에서 살짝만 추가하면 문제를 해결할 수 있습니다 작업 시간 배열, 선행 관계 배열, 그리고 정답 출력 배열을 만든 후 큐를 돌리면서 ans[next] = max(ans[next], ans[node] + workTime[node])로 갱신해주시면 됩니다. 정답은 m..

머지 소트 트리(Merge Sort Tree)는 트리의 일종으로 merge sort과정을 그대로 트리 모양으로 접합시킨 트리트리의 높이는 log N 정도이고, 하나의 층에 총 N개의 원소가 있으므로 공간복잡도 역시 O(N log N)수준구현이 문제인데, 이것은 merge 함수를 이용하여 생각보다 간단하게 구현이 가능  백준 13537번 수열과 쿼리 1https://www.acmicpc.net/problem/13537 13537번: 수열과 쿼리 1길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.www.acmicpc.net     각 배열들..

✏️ 문제 링크 https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 코드 #include #include #include using namespace std; #define INF 1000000001 vectortree,arr; int initTree(int start, int end, int node); int updateTree(int s..