본문 바로가기

Problem Solving

 (59)
[BOJ] 14591 KUBC League, 17165 Gosu 14591 KUBC League 문제 요약 토너먼트 그래프가 있다. 1번 정점에서 시작해서 모든 정점을 순회하는 단순 경로를 찾으면 된다. 문제 풀이 DFS 스패닝 트리에 의거하여, 그냥 DFS를 1번 정점에서부터 수행 후 마지막부터 출력해주면 된다! 코드 #include #include #include #define all(x) (x).begin(), (x).end() #define endl "\n" #define ends " " #define pb(x) push_back(x) #define fio() ios_base::sync_with_stdio(0); cin.tie(0) using namespace std; typedef long long ll; typedef pair pii; typedef pai..
Small to Large Trick Intro Small to Large Trick은 집합을 서로 합치는 연산을 최적화 할 때 사용하는 트릭입니다. (한국에서는 작은거 큰거 라고도 불리는 모양입니다.) 예를 들어 $n$개의 disjoint한, 크기가 1인 집합을 서로 합쳐야 한다고 합시다. 당연하게도 크기가 $a$인 집합에 크기가 $b$인 집합을 추가하는 데는 $O(b)$의 시간이 걸립니다. 이걸 Naive하게 구현한다면 얼마의 시간이 걸릴까요? 만약 두 집합을 합칠 때 아무 집합을 다른 집합에 합치는 것을 계속 반복한다면, 최악의 경우에는 크기가 가장 큰 집합을 크기가 가장 작은 집합에 계속해서 넣으면서 총 $O(N^2)$의 시간이 걸릴 것입니다. 하지만 어지간히 멍청한 알고리즘이 아니고서야, 크기가 큰 집합을 작은 집합에 합칠리가 없습..
Google Hash Code 2020 후기 부추전 고양이 boots jeon cats는 이런 사람들이 모여 만든 팀입니다. ryute, 고려대 아기호랑이, 랜덤과 휴리스틱을 사랑함 Lawali, 고려대 석유호랑이, 랜덤과 휴리스틱을 혐오함 cloneofsimo, 고려대 어른호랑이, 아무튼 알고리즘 시작한지 한달 반 지남 junie, 서울대, 왜 설대인데 고대 사이에 끼어 계십니까? :blobaww: 개인적으로 junie님하고 꽤 많이 친하기에, 구글 해시코드에 나가자는 뜻이 맞아 2인 팀이 결성되었습니다. 그 후 연습을 빙자한 맥주 마시기 행사를 가진 다음 사람이 많을수록 무조건 이득이라는 것을 확인하고, 대충 버스를 태워줄 수 있을 것으로 보이면서 할 것도 딱히 없어 보이는 라왈리를 섭외했습니다. 마지막으로 인원수를 대충 때워야 할 것 같다는 ..
[BOJ] 13329 Meteor Shower 문제 요약 y>0인 반평면에 다각형들이 있다. 원점에서부터 빛을 쏴서 다각형들을 관측할 때, 어떻게 빛을 쏴도 관측할 수 없는 다각형의 개수를 세서 출력한다. 문제 풀이 이런 류의 문제에서 항상 쓰는 테크닉인 스위핑을 갖고 옵시다. 다만 평소에 쓰는 라인 스위핑이 아닌, 각도 기준으로 스위핑을 진행해야 합니다. 다각형끼리 서로 교차하지 않으므로, 각 다각형을 각도가 가장 작은 점과 각도가 가장 큰 점을 이어주는 선분으로 바꿔줘도 답에는 영향이 없습니다. 그렇다면 문제는 n개의 선분이 주어졌을 때 완전히 가려지는 선분을 구하는 문제로 환원됩니다. 모든 선분의 끝 점을 각도 순으로 정렬합니다. (https://koosaga.com/97) 선분의 시작 지점이 들어올 때 집합에 선분을 추가하고, 종료 지점이 들..
[ICPC] ICL 2016 (GP of Tatarstan) 후기 & 잡설들 Intro 고려대학교 2020 ICPC 팀이 한 팀 결성되었습니다! ryute, 20학번, 퍼플 seyun, 19학번, 오렌지 cheetose, 군인, 오렌지 cheetose님이 저에게 팀 하자는 제안을 주셨고, seyun님도 cheetose님한테 팀 하자는 제안을 드린 것 같아서 영문도 모른 채 3인 팀이 구성되게 되었습니다. 저는 오렌지 둘의 버스를 탈 수 있으니 대만족이고, 현재 음료수와 간식을 배달하고 분배하는 업무에 숙달되기 위해 오늘도 열심히 노력하고 있습니다. 입학하기도 전에 버스팀이 생기는 사람이 있다? 서로 얼굴을 본 적이 없다는 이유로 만나서 밥을 먹기로 했습니다. cheetose님이 밥 먹기 전에 셋을 하나 돌자고 하셔서 솔직히 불안했습니다. 오렌지 2명 사이에 끼어서 노솔브 하면 어..
[BOJ] 10264 Particle Swapping 문제 링크: https://www.acmicpc.net/problem/10264 문제 요약 평면 그래프에서 다음과 같은 쿼리를 처리해야 한다. 어떤 두 정점이 주어질 때, 각 정점에서 반대 정점으로 이동하는 개체 2개가 있다. 이동 중 개체 사이 거리의 최솟값이 가장 최대가 되도록 배치했을 때 거리의 최솟값을 구한다. 단, 경로에서는 간선은 따지지 않고 오직 정점만을 따진다. 문제 풀이 그래프를 적절히 바꿔서 모델링해보자. 정점 A에서부터 출발하는 개체와 정점 B에서 출발하는 개체의 위치를 순서쌍으로 표현해볼 수 있다. 만약 그렇다면 이동 중 개체 사이 거리의 최솟값은, 순서쌍을 정점으로 두고 순서쌍 사이의 상태 전이가 가능한 경우를 적당히 간선으로 이어줬을 때 (A,B)에서 (B,A)로 이동하면서 찾아..
[BOJ] 1396 크루스칼의 공 문제 링크: https://www.acmicpc.net/problem/1396 문제 요약 간선에 가중치가 존재하는 그래프가 존재하는데, 다음과 같은 쿼리를 빠르게 처리해야 한다. 정점 x에서 시작해서 y까지 이동하려고 할 때, 이용해야 하는 간선의 최소 가중치는 얼마인가? 그리고 x에서부터 그 가중치로 방문할 수 있는 정점의 개수는 몇 개인가? 문제 풀이 두 가지 풀이가 존재한다. (1) 병렬 이분 탐색 한 쿼리에 대해서 다음과 같은 문제를 해결한다고 생각해보자. 정점 x에서 시작해서 k 이하의 가중치를 갖는 간선만을 사용할 수 있을 때, 정점 y에 방문할 수 있는가? 또한 이 때 정점 x로부터 방문할 수 있는 정점의 개수는 얼마인가? 이 문제를 해결하는 방법은 쉽다. 말 그대로 k 이하의 가중치를 가지..
USACO 2020 January (Gold) 풀이 Intro 원래 USACO 참여할 생각이 없었는데 브론즈만 밀어야지 실버만 밀어야지 하다가 결국 골드를 키게 되었다. 중간에 뇌절파티를 많이 해서 예상보다 시간이 매우매우 많이 걸렸다. 개인적인 난이도는 2->1->3이라고 생각하나, 증명 없이 뇌를 비우고 푼다면 1번이 2번보다 더 쉬울수도 있다는 생각을 해본다. 세 문제 모두 플5에서 플3 정도의 수준이라고 생각한다. 1. Time is Mooney (time) 문제 요약 정점 1000개, 간선 2000개인 그래프가 있다. 각 정점은 1000 이하의 가중치를 가지고 있는데, 정점을 방문할 때 마다 그만큼의 점수를 얻는다(여러 번 방문해서 점수를 얻을 수 있다). 단, 사용한 간선 개수를 $t$라고 하면 주어지는 1000 이하의 정수 $c$에 대해 $c..

티스토리툴바