본문 바로가기

전체 글

(81)
. 보호되어 있는 글입니다.
선택 정렬의 개선 데추주를 위해 선택 정렬을 짜는데 무언가 익숙함이 느껴졌다. 어 이거... RMQ? RMQ는 세그먼트 트리를 이용하면 각 쿼리를 $O(logN)$에 구할 수 있음이 잘 알려져 있고, 선택 정렬을 시행할 때 필요한 쿼리의 수는 $N$번이다. 세그먼트 트리를 전처리하는 데에도 $O(NlogN)$이 필요하므로, 최종 시간복잡도 $O(NlogN)$에 배열을 정렬할 수 있다. BOJ 2751에 제출해보니 메모리와 시간 면에서 그다지 효율적이지는 않아도 나름 선전하는 모습을 보여줬다. #include using namespace std; #define nm (nl+nr>>1) typedef pair pii; const int N = 1e6+1; int n,a[N]; pii tree[4*N]; void init(in..
First Solve 3개 퍼솔을 처음 시도해보았다. 쫄려서 쉬워보이는 것들만 찍먹함. ㅎㅎ
Educational Codeforces Round 116 (Div. 2) Dashboard - Educational Codeforces Round 116 (Rated for Div. 2) - Codeforces codeforces.com 3주 만의 코포 복귀 & 3달 만의 퍼플 복귀 & 10달 만의 +100 시간이 맞지 않아 3주 동안이나 코포를 못하고 있었고 이날도 분명 힘들거라 생각했었다. 그런데 버스 기사님이 무리를 하셨는지, 도착 예정 시간이 아슬아슬하게 들어와서 지하철 안에서 노트북 세팅을 끝내 놓고 집으로 뛰어들어왔다. 이때가 대충 33분. 손만 대충 씻고 코포에 빠르게 접속하니 대회가 바로 시작... 그래서 외출 상태 그대로 코포를 쳤고, 결과는 성공적이었다. Prob. A ab, ba의 개수는 a, b 묶음이 몇 번 변하는지에 영향을 받는데, 대충 3번째 예제를..
[BOJ 1167] 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 널리(?) 알려진 것과 달리 dfs 한 번으로 해결할 수 있다. 사실 그 방법을 몰라서 이렇게 풀었다. 풀이 임의의 루트를 하나 잡고 트리를 구축했다고 생각하자. 트리의 지름을 만드는 두 노드의 공통 조상은 트리 위의 노드 중 하나이기 때문에, 모든 노드에 대하여 그 노드를 공통 조상으로 하는 두 노드의 최대 거리를 시도해보면 된다. 이를 위해 필요한 정보는 각 서브 트리의 최대 깊이와 여러 서브 트리 중 첫 번째와 두 번째로 깊은 깊이이고, 이..