본문 바로가기

백준

 (223)
[ICPC] 백준 2104 - 부분배열 고르기 https://www.acmicpc.net/problem/2104 문제에서 요구하는 사항을 처리하기 위해서는 두 개의 세그먼트 트리가 필요하다. 하나는 구간합을 저장하는 트리, 나머지는 구간의 최솟값의 index를 저장하는 트리이다. 최솟값도 아니고 그 index를 저장하는 이유는 다음 전략을 따르기 때문이다. 1. 특정 구간 x의 연산 결과를 구한다. 2. x의 최소 원소 xval가 없는 구간은 xval보다 큰 수를 곱할 것이 자명하다. 3. 그렇다면 xval이 빠진 구간의 연산 결과는 구간 x의 연산 결과보다 커질 수 있다는 기대를 가질 수 있다.(입력은 전부 1 이상의 정수이므로 더하는 것보다 곱하는게 더 영향이 크다는 사실을 상기하라.) 4. 그러므로 우리는 xval를 pivot으로 하여 구간을 ..
[ICPC] 백준 9345 - 디지털 비디오 디스크 https://www.acmicpc.net/problem/9345 아이디어 고객이 l번부터 r번까지의 DVD를 원할 때 이들의 index 최솟값과 최댓값은 l과 r이다. 그러면 도중에 DVD가 바뀌었다 하더라도 l번부터 r번까지 DVD의 index 최솟값과 최댓값이 l과 r이면 해당 구간에 동일한 내용물이 들어있음을 이해할 수 있다. 왜냐하면 DVD 집합의 크기가 변하는 것이 아니기 때문에 index의 경계를 살펴보면 원하는 원소들이 속해있는지 속하지 않았는지 판단할 수 있기 때문이다. 그러면 세그먼트 트리를 통해 특정 구간에서 index의 최소와 최대를 저장하여 질의를 처리하는 방법을 생각해 볼 수 있다. 구현 문제를 풀기 위해 다음 역할을 하는 배열을 사용한다. ar[선반 번호] = DVD 번호 초기..
백준 13544 - 수열과 쿼리 3 https://www.acmicpc.net/problem/13544 특정 구간에서 어떤 원소를 상대로 질의를 처리하는 것은 머지 소트 트리를 이용하여 할 수 있다. 머지 소트 트리를 구현한 후 문제에서 요구하는 대로 질의를 처리한 결과를 출력하면 AC를 받을 수 있다. 마지막으로 출력한 결과와 XOR 연산을 해줘야 하는 것을 잊지 말자. # XOR를 해주는 이유는 오프라인 쿼리를 사용할 수 없게 하기 위함이라고 한다. 전체 코드 더보기 #include using namespace std; vector tree[400000]; int ar[100001]; int mid(int s, int e) { return s + (e - s) / 2; } void init(int node, int start, int ..
[ICPC] 백준 7469 - K번째 수 https://www.acmicpc.net/problem/7469 수열의 부분 구간에서 연산을 하는 것은 머지 소트 트리로 처리할 수 있다. 머지 소트 트리를 구현한 후 이진 탐색을 이용하여 구간의 k번째 원소를 찾아주면 된다. 전체 코드 - query 함수에서 lower_bound를 사용했으므로 kth - 1을 pivot으로 삼은 것에 유의하라. 더보기 #include using namespace std; int n, m; vector mst[400000]; int ar[100001]; inline int mid(int s, int e) { return s + (e - s) / 2; } void set_mst(int node, int start, int end) { vector &cur = mst[no..
[ICPC] 백준 9463 - 순열 그래프 https://www.acmicpc.net/problem/9463 각 편에서 번호가 같은 정점끼리 연결했을 때 생기는 교차점으로 순열 그래프를 구성한다고 한다. 우리는 교차점의 개수를 구해야 되므로 문제에서 첫번째 그림을 보고 3770번 문제와 같은 흐름으로 inversion counting을 생각할 수 있다. 다만 이 문제는 주어진 입력에서 번호가 같은 정점끼리 연결하는 것이므로 이를 적절히 변환해줄 필요가 있다. 주어지는 첫번째 노드 집합을 index에 매칭하여 각 숫자가 어느 index에 대응하는지 배열로 저장한다.(mp[val] = idx) 두번째 노드집합에서는 index와 첫번재 mp배열에서 해당 노드 숫자의 index를 가져와 pair로 짝지어서 배열이나 선형 자료구조에 저장한다. 그렇게 되면..

티스토리툴바