sweeping [백준] 13334번: 철로 h <= o 라는 조건이 없기 때문에 시작점과 도착점을 통일시켜주기 위해 h <= o 조건을 구현해줍니다. 도착점을 기준으로 오름차순 정렬을 합니다. 0부터 (n-1)까지 순회를 합니다. 최소힙에 시작점을 넣어주고, peek 값이 (현재 도착점 - d) 값보다 작은 경우 모두 pop을 해줍니다. 최소힙의 사이즈는 (현재 도착점 - d)에 포함되어 있는 철로의 개수를 의미합니다. 시간복잡도 O... heapsweepingSortkotlinSort [백준] 2170번: 선 긋기 입력 x에 대해 오름차순으로 정렬합니다. 시작 정보(0번째 인덱스)를 저장하고, 1부터 (n-1)번째까지 순회합니다. 분리된 선인지 더 긴 선 정보가 있는지 확인하면서 길이를 누적해주고 길이 정보를 변경시켜줍니다. 분리된 선을 만났을 때에만 길이를 누적해주기 때문에 순회가 끝난 뒤에 잊지말고 반드시 길이를 누적해주어야 합니다. 시간복잡도 O(n)... sweepingSortkotlinSort <Baekjoon> #2170 선 긋기 (Making an Line) c++ 여기서 선이 여러 번 그려진 곳은 한 번씩만 계산한 그려진 선의 총 길이는 (1,5), (6,7) 길이 합인 5이다. 신경써야 할 부분은 선을 그을 때 선택할 두 점의 위치 (x,y)를 받고 x의 값을 기준으로 오름차순으로 정렬한 뒤 문제를 해결해야 한다. 먼저 한 선분당 점 2개를 입력받아야 하므로 선분의 시작 지점 (start), 끝 지점 (end)를 받는 Line 구조체를 만든다. li... baekjoonalgorithmsweepingalgorithm
[백준] 13334번: 철로 h <= o 라는 조건이 없기 때문에 시작점과 도착점을 통일시켜주기 위해 h <= o 조건을 구현해줍니다. 도착점을 기준으로 오름차순 정렬을 합니다. 0부터 (n-1)까지 순회를 합니다. 최소힙에 시작점을 넣어주고, peek 값이 (현재 도착점 - d) 값보다 작은 경우 모두 pop을 해줍니다. 최소힙의 사이즈는 (현재 도착점 - d)에 포함되어 있는 철로의 개수를 의미합니다. 시간복잡도 O... heapsweepingSortkotlinSort [백준] 2170번: 선 긋기 입력 x에 대해 오름차순으로 정렬합니다. 시작 정보(0번째 인덱스)를 저장하고, 1부터 (n-1)번째까지 순회합니다. 분리된 선인지 더 긴 선 정보가 있는지 확인하면서 길이를 누적해주고 길이 정보를 변경시켜줍니다. 분리된 선을 만났을 때에만 길이를 누적해주기 때문에 순회가 끝난 뒤에 잊지말고 반드시 길이를 누적해주어야 합니다. 시간복잡도 O(n)... sweepingSortkotlinSort <Baekjoon> #2170 선 긋기 (Making an Line) c++ 여기서 선이 여러 번 그려진 곳은 한 번씩만 계산한 그려진 선의 총 길이는 (1,5), (6,7) 길이 합인 5이다. 신경써야 할 부분은 선을 그을 때 선택할 두 점의 위치 (x,y)를 받고 x의 값을 기준으로 오름차순으로 정렬한 뒤 문제를 해결해야 한다. 먼저 한 선분당 점 2개를 입력받아야 하므로 선분의 시작 지점 (start), 끝 지점 (end)를 받는 Line 구조체를 만든다. li... baekjoonalgorithmsweepingalgorithm