스위핑 알고리즘

스위핑 알고리즘

스위핑 알고리즘은 1차원이나 2차원 공간에서 여러 개의 객체가 주어졌을 때, 특정 축을 기준으로 한 방향으로 진행(스위핑)하며 문제를 해결하는 알고리즘으로 주로 기하학적 문제의 풀이에서 많이 사용된다.

아래의 예시와 같이 전체 선분의 범위 만큼의 배열을 잡은 후 선분의 시작 점에 +1, 나갈 때 -1 하는 방식으로 어느 x좌표에서 중복되는 선분의 갯수를 파악하기 편리하다.

 

해당 문제를 단순 구현할 경우 통상적으로 O(n*m)의 시간이 걸리지만 

        for (int i = start; i <= end; i++) {
            int tmp=0;
            for (Pos height : heights) {
                int max = Math.max(height.start,height.end);
                int min = Math.min(height.start,height.end);
                if(min<=i&&i<max)
                    tmp++;
            }
            count = Math.max(count,tmp);
        }

스위핑 알고리즘을 적용할 경우 O(n+m)의 시간 복잡도로 문제 해결이 가능하다.

	for (Pos height : heights) {
                int max = Math.max(height.start,height.end);
                int min = Math.min(height.start,height.end);
                CountX[max]--;
        		CountX[min]++;
        }
	for (int i = 1; i < CountX.length; i++) {
            CountX[i]+=CountX[i-1];
            CountY[i]+=CountY[i-1];
        }

해당 알고리즘을 사용한 문제 풀이

https://suhanlim.tistory.com/249