32bit Blog

https://www.acmicpc.net/problem/23740#스위핑  문제 요약시작점과 끝점(s, e)으로 구성된 n개의 버스 노선 중 겹치는 구간이 있는 노선을 병합하여 중복 노선을 최소화하는 문제버스 노선을 합칠 때, 요금은 더 낮은 값을 따른다. 우선 스위핑이 무엇인지 알아볼 필요가 있습니다. Sweeping라인 스위핑이라고도 불리며, "쓸어 모으다" 라는 뜻이 있습니다. (일반적으로) 한 방향으로 탐색해가며 특정 연산을 진행하는 것입니다. 스위핑은 스택이나 정확한 솔루션이 존재하는 알고리즘처럼 정해진 방법은 없으며 하나의 개념이라고 생각하시면 됩니다. 우리는 한 방향으로 탐색할 것이기 때문에, 탐색할 방향으로 정렬된 상태여야 합니다. 우리가 풀어야 할 문제인 버스 노선으로 살펴봅시다.  이..

https://www.acmicpc.net/problem/3063#기하학 문제 요약겹쳐진 두 포스터(직사각형)가 존재한다면, 아래에 덮힌 포스터의 보이는 넓이를 구하는 문제입니다.먼저 생각해볼 것은 어떤 경우가 있는지를 살펴볼 필요가 있습니다. 쉽게 표현하기 위해:- 밑에 있는 포스터를 A (보이는 넓이를 계산할 직사각형)- 위에 있는 포스터를 B (A를 가리는 직사각형)로 표현합니다. 문제에서 단서들을 모아보자면, 주어지는 데이터의 입력 범위에서 A와 B가 항상 겹친다는 보장이 없습니다. 첫 단추는 두 직사각형이 겹치는지를 알아내는 것이 됩니다. 덧붙여 B가 A를 완전히 가리는 경우도 있을 수 있죠. 여기서 크게 3가지로 나눌 수 있음을 알 수 있습니다.A와 B가 겹치지 않는다.A와 B가 겹쳐져 있으나..

https://www.acmicpc.net/problem/14400#기하학  오랜만에 백준에서 문제를 풀었는데, 블로그를 만들어서 심심할 때(?) 하나씩 글을 써볼까 합니다. 고객(n개의 점)들의 거리의 합을 최소로 한다는 것은 n개의 점들에서 중앙값을 의미합니다.두 위치의 거리는 | x1 - x2 | + | y1 - y2 | 로 정의한다. 문제의 지문에서 유클리드 거리를 말하는 것이 아니라고 친절하게 설명하고 있기 때문에, 맨해튼 거리를 이용합니다. 맨해튼 거리를 이용하는 것은 유클리드 거리를 이용하는 것보다 보통 더 쉽습니다. 맨해튼 거리는 체스판의 룩이 이동하는 거리와 비슷한 개념입니다. 위 사진에서 백의 룩이 빨간 지점까지 가장 빠르게 가는 단순한 방법은 a8 -> h8 또는 h1 -> h8로 이..