[알고리즘] 백준 파이썬 11663 선분 위의 점

📍 문제 탐색하기선분 위의 점 문제는 1차원 좌표 상의 N개의 점과 M개의 선분이 주어졌을 때,각 선분에 속하는 점의 개수를 빠르게 구하는 문제이다.점의 좌표와 선분의 시작점, 끝점이 주어지며, 점의 좌표는 중복되지 않는다.문제 조건점의 개수 N: 1≤N≤100,000선분의 개수 MMM: 1≤M≤100,000점의 좌표: 서로 중복되지 않으며, 1≤xi≤1,000,000,000선분의 시작점과 끝점: 1≤li,ri≤1,000,000,000출력 조건각 선분마다 포함된 점의 개수를 한 줄에 하나씩 출력한다.가능한 시간 복잡도N,M이 최대 100,000이므로 단순한 선형 탐색을 수행할 경우 O(N×M)으로 비효율적이다.효율적인 탐색을 위해 이분 탐색을 사용하면 O(Nlog⁡N+Mlog⁡N)로 해결 가능하다.📍..
알고리즘 2025. 1. 19. 23:51
1