문제 https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 Inversion Counting 문제를 세그먼트 트리를 이용해 해결하는 문제. 해결법은 다음과 같다. 한 기계의 쌍의 A라인의 위치를 a_idx, B라인에서의 위치를 b_idx라고하자. 이 기계의 케이블과 교차되기 위해서는 해당 기계의 A라인에서의 위치(a_new)가 a_idx보다 앞에 있고 B라인에서의 위치(b_new)가 b_idx보다..

문제 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 세그먼트 트리(구간 트리)를 이용해야 제한시간 안에 풀 수 있는 문제. 세그먼트 트리를 모른다면 간단한 풀이로는 이해하기 힘드므로 백준님의 깔끔한 설명을 보고 오자. 세그먼트 트리 (Segment Tree) - Baekjoon Online Judge 세그먼트 트리는 이름처럼 노드마다 자..

문제 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 입력을 정렬한 후 우선순위 큐를 이용하여 처음부터 끝까지 스위핑하여 해결할 수 있는 문제. 일단 입력의 집과 사무실의 위치를 pair arr[100000] 에 저장한다. 어느 쪽이 집이고 사무실 인지는 철로에 영향이 없기 때문에 pair의 first에 더 작은 위치(선의 시작점)를 저장하자. 이제..

문제 https://www.acmicpc.net/problem/17612 17612번: 쇼핑몰 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 각 계산대에 줄을 세우는 우선순위 큐와 계산을 끝내고 빠져나오는 순서를 저장하는 우선순위 큐의 정렬 순서가 중요한 문제이다. 각 계산대에 줄을 세우는 우선순위 큐를 생각해보자. 고객들은 계산대의 대기 시간이 가장 작은 곳에 줄을 서고, 만약 대기 시간이 같은 계산대가 여러 개라면 번호가 작은 계산대에 줄을 선다. 따..

문제 https://www.acmicpc.net/problem/2014 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 풀이 solved.ac 난이도: Gold 2 K개의 소수가 주어질 때 소수들의 곱으로 만들 수 있는 수들 중에서 N번째 수를 구하는 문제. 소수로 새로운 수를 만들 때마다 오름 차순 정렬하여 N번째 수를 찾아내기는 힘들다. 따라서 간단한 시간 복잡도를 가지는, 우선순위 큐를 활용하자. 최소 힙으로 구성된 우선 순위 큐는 루트(top)에 항상 가장 작은 수가 존재한다..

문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 종만북에 등장하는 변화하는 중간 값 문제와 동일한 문제. 해당 책에서의 트립 알고리즘을 사용하여 트리 내의 몇 번째 원소를 반환하는 코드를 짤 수도 있지만 우선순위 큐만으로 해결가능하다. 우선순위 큐는 부모 노드가 자식 노드보다 큰 값만 가지게 정렬(최대 힙의 경우)되어 있다. 반대로 최소 힙으로 구현된 우선순위 큐는 부모 노드가 ..

문제 www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 일단 문제에서 주어지는 의사 코드(pseudo code)로 구현해보았다. 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 int counter =0; class Node{ public: int num; Node* parent; Node* left = nullptr; Nod..

문제 https://www.acmicpc.net/problem/1693 1693번: 트리 색칠하기 n개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점을 색칠하려고 한다. 색칠을 할 때에는 1, 2, 3, …, n번 색깔 중에 하나로 색칠하여야 한다. 각 색깔을 사용하여 한 개의 정점을 색칠할 때 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 상당히 해결하기 어려웠던 트리에서의 다이나믹 프로그래밍 문제. 해당 문제의 풀이는 koosaga님과 BaaaaaaaarkingDog님의 풀이를 참고하였습니다. T(N): 반드시 N개의 색을 사용해야 트리를 최소 비용으로 칠할 수 있는 트리들 중에서 최소 노드 개수 라고하자. 반드시 N개의 색을 써야 한다면 루트 노드의 자식 노드..

문제 https://www.acmicpc.net/problem/1289 1289번: 트리의 가중치 첫째 줄에 트리의 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N-1개의 줄에 대해 각 줄에는 세 개의 정수 A, B, W(1 ≤ A, B ≤ N, 0 ≤ W ≤ 1,000)가 입력되는데 이는 A점과 B점이 연결되어 있고 이 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 트리에서의 다이나믹 프로그래밍으로 분류되었지만 풀어보니 본인의 풀이에는 다이나믹이 사용될 부분은 없었다. 트리의 모든 경로를 하나 하나 계산하기에는 특정 노드에서 모든 노드 하나하나의 경로 수를 계산해보면 N(특정 노드)*(N-1)(선택한 노드 이외의 모든 노드)의 경로 수가 존재한다. 이..

문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2