# sweeping

8개의 포스트

5419. 북서풍

시간 제한: 256MB메모리 제한: 1초Naive 하게 풀면, N(N-1) 가지 쌍을 모두 조사하면 되지만 오래 걸린다. 대신, Segment Tree로 원하는 범위에 존재하는 섬을 조사할 수 있다면, 시간을 단축시킬 수 있을 것이다.남쪽 섬부터 시작해서 북쪽 섬 순서

2022년 5월 21일
·
0개의 댓글

[백준] 13334번: 철로

문제링크h <= o 라는 조건이 없기 때문에 시작점과 도착점을 통일시켜주기 위해 h <= o 조건을 구현해줍니다.도착점을 기준으로 오름차순 정렬을 합니다.0부터 (n-1)까지 순회를 합니다.최소힙에 시작점을 넣어주고, peek 값이 (현재 도착점 - d) 값

2022년 4월 21일
·
0개의 댓글

[백준] 2170번: 선 긋기

문제링크입력 x에 대해 오름차순으로 정렬합니다.시작 정보(0번째 인덱스)를 저장하고, 1부터 (n-1)번째까지 순회합니다.분리된 선인지 더 긴 선 정보가 있는지 확인하면서 길이를 누적해주고 길이 정보를 변경시켜줍니다.분리된 선을 만났을 때에만 길이를 누적해주기 때문에

2022년 4월 21일
·
0개의 댓글

백준 17131번: 여우가 정보섬에 올라온 이유

백준 17131번: 여우가 정보섬에 올라온 이유스위핑을 두 번 해주면 된다. 왼쪽부터 훑으면서 나보다 y좌표가 큰 별이 몇개인지 세고, 오른쪽부터 훑으면서 나보다 y좌표가 큰 별이 몇개인지 센 후에 곱해주면 된다. 셀때 y좌표는 무조건 작은걸 먼저 세야 한다 큰걸 먼저

2021년 12월 12일
·
2개의 댓글

백준 5419번: 북서풍

백준 5419번: 북서풍자기보다 x좌표가 크면서 y좌표가 작은 점이 몇개인지 세면 된다. x좌표 오름차순으로 정렬해서 순서대로 자기보다 y좌표가 작은 애가 몇개나 있는지 보면 하나도 빼놓지 않고 찾을 수 있다. y좌표가 작은 애가 몇개인지 찾기 위해 좌표압축을 하고,

2021년 12월 11일
·
2개의 댓글
post-thumbnail

<Baekjoon> #2170 선 긋기 (Making an Line) c++

sweeping algorithm은 line sweeping 이라고도 불리고, 정렬된 순서대로 처리되는 이벤트의 집합으로 문제를 모델링 하는 방법이다.문제에 있는 예시를 보면 길이 (1,3), (2,5), (3,5), (6,7)인 선분이 4개 있다. 이를 그림으로 그려

2021년 11월 8일
·
0개의 댓글
post-thumbnail

백준 알고리즘 2170,15922번 : 선 긋기,아우으 우아으이야!!

https&#x3A;//www.acmicpc.net/problem/2170https&#x3A;//www.acmicpc.net/problem/15922두 문제 모두 같은 코드로 풀 수 있습니다.https&#x3A;//m.blog.naver.com/kks227/220907

2021년 8월 19일
·
0개의 댓글

17619: 개구리 점프

문제 보기 입력이 너무 많아서 싱크를 끊지 않고서는 cin/cout 사용으로 해결할 수 없습니다. 핵심 아이디어 그리디한 생각으로 가봅시다! 위, 아래로 뻗어가면서 그래프를 그려 나가야 하나, 하는 생각도 했지만, 그럴 필요가 없다는 것을 깨달을 수 있습니다. 왜냐면 수직적으로 겹치는 구간에 있는 통나무끼리는 점프가 가능하기 때문입니다. 따라서 그리디라...

2020년 12월 31일
·
0개의 댓글