개요
4주차 스터디는 자료구조 관련 6문제였다.
A번
문제 요약
N명의 후보들의 득표수들이 주어지고,
1번 후보가 당선되게 하기 위해서 유권자를 몇명이나 매수해야 하는지를 구하는 문제
설명
Max PQ에 1번을 제외한 후보의 득표수를 넣고,
가장 큰 득표수가 1번의 득표수보다 작아질 때까지, 1표를 옮기고 PQ에 집어넣기를 반복하면 된다.
꼭 1표씩 처리해줘야 한다.
B번
문제 요약
터널을 지나가는 차량 번호의 순서가 주어졌을 때, 터널 내에서 추월한 차를 모두 찾기
설명
추월한 차의 번호를 관리하는 set을 만들고, 차 번호 배열 in과 out을 비교하면서 다르면 set에 넣는다.
이미 set에 들어간 차라면 continue해 준다.
C번
문제 요약
문제 제목이 마음에 든다.
N개의 수 중 다른 두 수의 합으로 나타낼 수 있는 수의 개수를 구하면 된다.
설명
map<int, set<int>> where를 만들어서, 어떤 값이 어떤 인덱스들에 있는지를 저장해 둔다.
2중 for를 돌면서, 모든 A, B에 대해 A+B가 where 안에 있는지 확인한다.
그 후 set에 있는만큼 세 주고, set에서 제거해준다.
‘다른’ 두 수가 맞는지, A와 B가 같은 인덱스인지를 신경써주면 된다.
D번
문제 요약
그래프에서 엣지를 하나씩 제거하는데, 엣지가 집합을 둘로 나누는 경우에는 두 집합의 크기를 곱한 만큼 비용이 발생한다.
비용의 총합을 구하는 문제
설명
아이디어가 꽤 참신한 문제
관찰해보면 UF의 Union를 반대로 진행하고 있다는 것을 확인할 수 있다. (집합을 둘로 분리하기)
그래서 쿼리를 역순으로 처리하면서, Union시마다 둘의 size를 곱한 만큼 ans에 더해주면 된다.
UF에서 size를 잘 관리해주자.
E번
문제 요약
어떤 트리가 있다.
어떤 탐색 순서가 주어졌을 때, 트리 위에서 DFS로 가능한 탐색인지 확인하는 문제
설명
DFS를 잘 시뮬레이션 하면 된다. (스택을 이용해서)
다음 노드는 고정되어 있으므로, 그 다음 노드로 가는 방법이 있는지만 확인하면 된다.
자식을 먼저 확인하고, 자식 중에 없으면 스택의 이전 노드로 되돌아가서 반복하면 된다.
F번
문제 요약
비용이 있는 트리가 주어질 때,
- 어떤 노드 u, v를 잇는 경로의 비용
- 어떤 노드 u, v의 경로 중 u로부터 k번째 노드 찾기
이렇게 두 가지 쿼리를 처리하는 문제
설명
LCA로 접근하고, 경로는 u->LCA + LCA->v라는 점을 이용하면 된다.
1번 쿼리는 u->LCA의 비용, v->LCA의 비용을 더해서 출력하면 되고,
2번 쿼리는 u->LCA가 몇 개인지, LCA->v가 몇 개인지를 생각해보고 어디에 위치하는지 생각해보면 된다.
그래서 LCA의 쿼리를 두 가지로 짜면 된다.