[TIL][Krafton Jungle] 2주차 - (7) : 누적 합과 스위핑

드디어 어제 마지막으로 2주차 문제를 모두 풀었다 !

1주차 남겨둔 두문제도 풀고 이번주 여유롭게 넘어가보자.

 

`시간 많다고 농땡이 피우지 말고 운영체제 책 읽기`

 

일단 오늘은 백준 문제 푸느라 미뤄둔 컴퓨터 시스템 책을 읽으며 시스템에 대해 공부 좀 해보려고 한다.

 

그전에 알고리즘 공부도 개인적으로 조금 한 것을 정리해보겠다.

 

---

누적 합(Prefix Sum)

만약 a1 ~an 까지의 수열을 모두 더하면 시간 복잡도는 O(n)이다.

하지만 특정 구간 q개에 대하여 구간 합을 물어본다면? -> O(qn)

 

이 시간 복잡도를 O(n)로 처리할 수 있게 하기 위해 누적된 합을 저장하는 누적 합 알고리즘을 수행한다.

특정 구간 i~j 사이의 수열 합을 구할 때, 누적합 P 수열에서는 pj - p(i-1) 만 하면 되기 때문이다.

 

 

스위핑 

스위핑은 직선이나 공간에서 한쪽 시작점을 기준으로 반대쪽까지 한 번만 훑으면서 답을 구하는 방법이다.

훑으면서 우선순위 큐 등의 자료구조를 사용해 답을 구한다.

 

따라서 스위핑은 입력된 자료들이 n개라면, 주로 O(n)이나 O(nlogn)이 걸린다.

 

이 알고리즘은 문제에 적용하면 바로 이해가 되므로 골4의 문제를 예제로 한번 이해해보자.

 

BaekJun - #2170 : 선 긋기 (스위핑)

출처 : https://www.acmicpc.net/problem/2170

2170번: 선 긋기

선 긋기 문제는 스위핑의 가장 기초 문제로, 중복되는 선들을 하나의 긴 선으로 인식하여 길이를 재야 한다.

 

알고리즘 풀이 방법은 이렇다. (편의상 선분의 왼쪽 점의 x좌표를 x, 가장 오른쪽의 x좌표를 y라고 하겠음)

 

1. 선분들의 x,y좌표를 받는다.

2. x좌표로 오름차순 정리한 뒤 for 문으로 제일 낮은 (좌표상 제일 왼쪽 선분) x 좌표의 선분부터 돌린다.

3. for문 안에서 y좌표를 now 변수에 기억하며 다음 선분과 비교한다.

4-1. 만약 now보다 현재 선분의 x좌표가 더 크다면 그 사이 공간이 생긴 것이므로,

공간을 그 사이값 만큼 저장한 뒤 now를 현재 선분의 y좌표로 바꿔준다.

4-2.(4-1)의 경우가 아니라면 현재 선분의 y좌표와 지금까지 기록된 now좌표 중 큰 값을 now에 저장한다.

5. now에는 선분의 제일 오른쪽 좌표가, 선분들의 x좌표 중 가장 작은 1번째 인덱스 선분의 x좌표는 선분의 제일 왼쪽 좌표가 들었다.

따라서 now-line[0][0] -space(선분 사이에 발생한 공간) 을 해준다.

 

 

해당 알고리즘의 코드는 다음과 같다.

import sys

n = int(sys.stdin.readline())
line = []
for i in range(n):
    x,y = map(int,sys.stdin.readline().strip().split())
    line.append((x,y))

line = sorted(line)
space = 0
now = 0
for i in range(n):
    if i == 0:
        now = line[i][1]
    else:
        if now < line[i][0]:
            space += line[i][0] - now
            now = line[i][1]
        else :
            now = max(now,line[i][1])

print(now-line[0][0]-space)

 

---

BaekJun - # 13334 : 철로 (우선순위 큐, 스위핑)

출처 : https://www.acmicpc.net/problem/13334

13334번: 철로

위의 스위핑의 개념을 배경으로 1주차 마지막 철로 문제를 해결했다.

 

문제 풀이 서사

스위핑 알고리즘을 이용하지 않고는 절대 풀 수 없도록 n = 10^5 의 조건을 걸어 놓은 것을 보고는,

스위핑 적용에 집중한 나머지,

내 풀이가 특정 케이스에서 문제를 해결하지 못하는 것을 놓치고 계속 삽질을 했다..

 

처음 잘못된 풀이의 코드의 작동 방식은 다음과 같다.

 

1. 모든 사람들의 출근지와 집의 좌표를 받아서(한사람 당 하나의 선분)

더 왼쪽의 좌표를 x에, 오른쪽 좌표를 y에 대입하여 리스트에 튜플로 넣고 x로 모든 선분을 정렬한다.

2. 정렬 후 하나씩 for문을 통해 선분을 확인하며 L 선분 값을 변경해주며 result 값을 기록해둔다.

2-1. 특정 선분 길이가 L보다 길다면 다음 선분으로 넘어간다.

** 모든 선분은 본인 길이, 상황에 맞는 if문을 끝내고 queue.append(선분의x좌표)로 queue에 저장한다.

3. L 선분 값은 lx , ly로 기억해둔다.

4-1. 만약 L 선분의 ly보다 검사하는 현재의 특정인물의 y좌표가 더 크다면 ly를 현재 선분의 y좌표로 바꿔준다.

4-2. 그후 queue의 가장 처음 저장된 요소를 확인하고 만약 ly-L의길이보다 작다면 pop을 한다. (이 구간을 반복)

5. for문을 다음 선분으로 넘어가기전에 result의 값과 queue의 길이(L선분 안에 있는 동선들)중에 큰 값을 result에 대입한다.

 

이 문제 풀이 방식은 문제를 정확히 해결해 줄 것이라고 착각했다.

 

이 풀이 방식의 코드는 다음과 같다.

from collections import deque
import sys

n = int(sys.stdin.readline())
ways = []
for _ in range(n):
    x,y = map(int,sys.stdin.readline().strip().split())
    if x > y:
        x,y = y,x
    ways.append((x,y))

l = int(sys.stdin.readline())

ways = sorted(ways)
result = 0
lx = 0
ly = 0
queue = deque()
for i in range(len(ways)):
    way_x, way_y = ways[i]
    if way_y - way_x > l:
        continue
    if part_result == 0:
        lx = way_x
        ly = lx + l
        queue.append(way_x)
    else:
        if way_y <= ly :
            queue.append(way_x)
        else :
            last_result = max(last_result,part_result)
            ly = way_y
            lx = way_y - l
            while queue:
                if queue[0] < lx:
                    queue.popleft()
                else :
                    break
            queue.append(way_x)
	result = max(result,len(queue))

print(result)

 

하지만 특정 상황을 커버하지 못한다.

 

예를 들면 x좌표로 오름차순으로 for문에 들어오는 동선의 선분들 중

이전 좌표보다 y좌표가 작은 선분이 들어온다면?

 

그 경우 이전 좌표에서 갱신한 ly보다 더 뒤에서 갱신되어야 함.

 

그때 깨달았다. 아 이거 y좌표로 오름차순을 해서 풀어야 되겠구나.

 

그러면 문제가 또 발생한다.

먼저 탐색한 경로보다 x좌표가 더 낮은 게 늦게 for문을 돌게 되면 queue의 선입 선출 알고리즘으로 커버를 할 수 없다.

 

그래서 생각했다.

"최소힙 자료구조를 이용해서 x좌표가 낮은 순으로 pop이 될 수 있게 우선순위 큐를 써야되겠구나."

 

최종적으로 작성한 코드는 다음과 같다.

 

import sys
import heapq

n = int(sys.stdin.readline())
ways = []
for _ in range(n):
    x,y = map(int,sys.stdin.readline().strip().split())
    if x > y:
        x,y = y,x
    ways.append((x,y))

l = int(sys.stdin.readline())

ways = sorted(ways)

result = 0
lx = ways[0][0]
ly = lx+l
heap = []
heapq.heapify(heap)
ways = sorted(ways,key = lambda x :x[1])

for i in range(len(ways)):
    way_x, way_y = ways[i]
    if way_y - way_x > l:
        continue

    if way_y <= ly :
        heapq.heappush(heap,way_x)
    else :
        ly = way_y
        lx = way_y - l
        while heap:
            if heap[0] < lx:
                heapq.heappop(heap)
            else :
                break
        heapq.heappush(heap,way_x)
    result = max(result,len(heap))
        

print(result)

 

 

---