본문 바로가기

sweeping1

[개념정리] 스위핑 알고리즘 스위핑 알고리즘이란 특정 기준에 따라 정렬된 순서대로 문제를 처리하는 방법이다. 스위핑 알고리즘을 사용해야하는 문제들의 특징은 러프한 방법 (일반적으로 O(N^2)의 시간복잡도를 갖는 방법)으로는 해결이 불가능하며, DP를 사용하기에는 메모이제이션 해야할 수가 너무 많은 경우가 일반적이다. 스위핑 알고리즘으로 문제를 풀 경우, 해당 시간 복잡도는 정렬에서 발생하는 O(NlogN)안에서 해결된다. 백준 - 8982. 사냥꾼 일반적인 방법으로 풀게되면 O(N*M)의 시간복잡도를 가지게 되고 시간초과가 발생한다. 그렇다고 좌표에 대한 정보를 기억할 수도 없기 때문에 스위핑 알고리즘을 통해 해결해야 한다. 먼저, 사대와 동물을 모두 x축 순서로 정렬하고 동물을 기준으로 사냥이 가능한지 확인한다. 확인 과정은 동.. 2021. 2. 26.

이전 1 다음

티스토리툴바