본문 바로가기

전체 글

BOJ)2261 가장 가까운 두 점 문제:icpc.me/2261 가장 가까운 두점을 N^2보다 적은 시간에 구해야하는 문제이다. 우선 점들을 x좌표 기준으로 스위핑해보자. 이후 x좌표가 증가하는 순서대로 점들을 볼건데 이미 본 점들은 y좌표 기준으로 정렬이 되도록 set에 삽입해준 후 지금까지의 최단거리가 d라면 현재 볼 점의 x좌표가 d이상 차이나거나 y좌표가 d이상 차이나는 점들을 제외하고 비교해준다. x좌표가 정렬 된 순서로 보기 때문에 포인트를 잡아서 기록해두면 x좌표가 차이나는 점들은 set에서 제거해줄 수 있고 y좌표는 lower_bound와 upper_bound를 통하여 탐색 지점을 정해놓고 비교해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373.. 더보기
BOJ)5038 Flight Planning 문제: icpc.me/5038 트리가 주어질 때 하나의 간선을 삭제하고 다시 하나의 간선은 연결하여 만든 트리의 지름이 최소가 되도록 하는 문제이다. N제한이 2500밖에 안되기 때문에 모든 간선을 다 삭제해 본 뒤 지름을 비교해보는걸 생각해볼 수 있다. 그렇다면 하나의 간선을 제거하였을 때 트리의 지름이 최소가 되도록 간선을 이어붙이려면 어떻게 붙여야할까? 바로 트리의 반지름을 이용하면 된다. 트리의 간선을 하나를 제거하면 두개의 트리가 생기게 된다. 이 때 두 트리의 반지름을 각각 구해준 뒤 반지름을 형성하는 정점들 사이에 간선을 연결하면 트리의 지름은 max(트리1의 지름,트리2의 지름,트리1의 반지름+트리2의 반지름+1)이 된다. 따라서 모든 경우에 대하여 트리의 지름을 구해준 뒤 비교하여 답을 .. 더보기
BOJ)8872 빌라봉 문제: icpc.me/8872 문제의 내용을 풀어서 설명하면 결국 포레스트가 주어졌을 때 해당 포레스트에 몇개의 간선을 추가하여 만들어진 트리의 지름의 최솟값을 구하는 문제이다. 문제의 답은 세 경우중 하나가 될 수 있는데 1.기존의 포레스트내의 트리에서의 지름중 최댓값 2-3. 포레스트 내부의 서브트리들의 반지름 중 가장큰 반지름을 가지는 서브트리에 나머지 반지름들을 길이 L로 연결하였을 때2.가장 긴 반지름 + 두번째로 긴 반지름 +L3.두번째로 긴 반지름 + 세번째로 긴 반지름 +L+L 이 세값 중 최댓값이 답이된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555.. 더보기

티스토리툴바