본문 바로가기

분류 전체보기

 (78)
[ICPC] Latin America Regional 2017 일부 문제 풀이 A. Arranging Tiles BOJ 15052번: https://www.acmicpc.net/problem/15052 이 문제의 핵심은, 어떤 2개의 다각형을 얼마나 가까이 붙일 수 있는 지 빠르게 계산하는 것입니다. 다각형을 배열하는 순서를 정하고, 그 다각형들에 대해 한 다각형의 x좌표 최댓값이 바로 다음 다각형의 x좌표 최솟값과 같게 배치했다고 합시다. 그렇다면 이 때의 해는 모든 다각형의 x축 길이 합에서, 모든 인접한 다각형 쌍에 대해서 다각형을 얼마나 가까이 이동시킬 수 있는지의 합을 뺀 것이 됩니다. 따라서 우리는 다각형 쌍이 주어졌을 때 이를 서로 붙일 수 있는 최대 길이를 미리 계산해 둔 뒤 가능한 모든 배열에 대해 해 중 최소를 찾아주면 됩니다. 붙일 수 있는 최대 길이를 모두 전..
[BOJ] 15404 Divide and Conquer 문제 요약 $N$개의 정점이 있고, 이 정점을 잇는 스패닝 트리가 2개 있다. 이 두 스패닝 트리의 합집합으로 구성되는 그래프에 대해(간선은 구별된다), $K$개의 간선을 제거하면 그래프를 연결 그래프가 아니도록 할 수 있다. 이 때 $K$의 최솟값을 구하고, 그 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력하면 된다. 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $K=2$이거나, $K=3$. 증명은 다음과 같다. 임의의 정점에 연결된 모든 간선을 제거하면 그 정점은 다른 정점과 연결되어 있지 않기에, 그래프는 연결 그래프가 아니다. 따라서 $K$는 모든 정점의 degree 중 최솟값보다 클 수 없다. 간선 하나는 정확히 두 개의 정점의 degree를 1만큼 증가시키므로, 모든 정점의 d..
2020 숭고한 Marathon 참가 후기 Intro 원래는 Advanced Division에 참가하려고 했었는데, 팀노트를 만들기 귀찮았고 무엇보다 자신이 작성해둔 코드라도 인터넷 검색에 걸리면 표절이라는 룰이 있었기 때문에 굳이 참가할 이유를 못 찾았습니다. ALPS는 Contest나 Marathon에서 한 문제 이상 해결하면 회비를 면제해주기도 했고, thak00는 이기고 싶었기 때문에 정확히 thak00보다 한문제 더 풀려고 노력했습니다. 여담으로 이번에 domjudge를 처음 써 봤는데 CMS에 비해 매우 별로였습니다. CMS가 최고다! 마지막 두 문제 빼고는 전부 해결했습니다. M은 디버깅 코드를 안 빼고 제출한 관계로 대회 중에는 WA로 기록되어 있습니다. 각 문제를 해결하면서 느낀 점과 셋 구성, 디스크립션에 대해 잡설을 풀어보려고..
개인적인 웹툰 몇줄 감상 * 너무 유명한, PC 기준 순위 5위권 즈음에 들어가는 웹툰들은 과감히 제외하고 선정합니다. * 보는 웹툰 중에서도 이건 한번씩 볼만하다 싶은 작품들을 선정했습니다. * 글쓴이의 취향은 상당히 마이너합니다. 꿈의 기업 드림 코퍼레이션이라는 의문의 회사에 취직한 사람들과, 그들이 살았던 도시, 그리고 한 인공지능의 이야기. 물론 스릴있고 흥미롭지만 무엇보다도 생각을 많이 하게 해 주는 작품. 긴 이야기 호흡에도 지치지 않을 자신이 있다면 시도해볼 가치가 충분하다. 고삼무쌍 이세계가 아닌 현세계에서 고등학생이 깽판치는 웹툰. 빠르고, 호쾌한 B급감성 신세대 무협. 이제는 무협도 따분하게 보지 않을 수 있다. 색다른 판타지 웹툰이 필요했거나, 아니면 요즘 살기가 좀 팍팍해서 큰 웃음이 필요한 사람들에게. 닥..
[BOJ] 16910 mex와 쿼리 [문제 링크](https://www.acmicpc.net/problem/16910) 문제 요약 다음과 같은 세 쿼리를 처리해야 합니다. [l,r]에 속하는 모든 자연수를 배열 A에 추가한다. 이미 있는 수는 무시된다. [l,r]에 속하는 모든 자연수를 배열 A에서 제거한다. 없는 수는 무시된다. [l,r]에 속하는 모든 자연수에 대해 있으면 제거, 없으면 추가한다. 각 쿼리를 수행 한 뒤에 이 배열에 없는 수 중 가장 작은 자연수를 찾으면 됩니다. 문제 풀이 일단 문제에서 요구하는 좌표가 크니 좌표 압축을 시도하고 생각합시다. 그 이후 Lazy Propagation 달려 있는 세그로 연산을 처리해주며 특정 구간에 존재하는 수의 개수를 세 주면 됩니다. Lazy 연산 중에 1번 쿼리와 2번 쿼리는 서로 상..
[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인 팀이 결성되었습니다. 그 후 연습을 빙자한 맥주 마시기 행사를 가진 다음 사람이 많을수록 무조건 이득이라는 것을 확인하고, 대충 버스를 태워줄 수 있을 것으로 보이면서 할 것도 딱히 없어 보이는 라왈리를 섭외했습니다. 마지막으로 인원수를 대충 때워야 할 것 같다는 ..

티스토리툴바