백준 2261번 가장 가까운 두 점 플래티넘2
푼 것, 배운 것
https://st-lab.tistory.com/256
https://my-coding-notes.tistory.com/103
- 다른 사람의 풀이를 보고 이해했다.
- 분할 정복이니까 범위를 나눠야겠지
- x좌표 y좌표가 다른데 범위를 어떻게 나눌까? 축을 하나 정해서 정렬
- 점이 있는 곳들을 포인트 이 포인트들을 분할정복으로 탐색
- 가운데를 기준으로 왼쪽과 오른 쪽으로 나눠서 각 영역에서 가장 가까운 거리로 갱신
- 가운데를 기준으로 지금 나온 최소거리 안쪽(x좌표만 따졌을 때)으로 들어온 애들을 모아
- 이 애들을 y축 기준으로 정렬
- 자신보다 위에 있는 점을 찾으면서 최소 거리 이상이 되면 break
기존에 풀었던 문제들 자바로 다시 풀었다
- (13문제)
복습하면서
- 이분탐색을 하면서 가장 가까운 값을 찾을 때
- 1) lower_bound 이용해서 그 앞뒤를 검색
- 2) 만약 나와 가장 가까운 놈을 찾는 다고 했을 때, 나보다 작으면 start = mid + 1, 나보다 크면 end = mid - 1을 하는 와중에, 중간에 변수를 두고 계속 확인한다. 가장 가까운 값을. 변수를 갱신해주면서.
spring, java학습