정글 W02 - 분할정복, 이분탐색, 스택, 큐, 우선순위 큐

W01과 마찬가지로 이번주도 새로운 알고리즘들에 대해 익히고 문제를 통해 체화하는 주였습니다.
저번주에 비해 난이도가 꽤나 올라간것이 느껴졌습니다.

푼 문제는 백준 27문제 + 개인적으로 푼 리트코드 8문제 해서 35문제네요. 블로그를 쓰며 생각해보니 추가적으로 문제 푸는데 들인 시간을 문제 별 시간복잡도를 정확하게 분석하는데 썼으면 더 좋았을 듯 합니다.

한주치 분량으로 주어지는 백준 문제들의 경우는 구글 닥스에 난이도가 써있는데, 중~ 상 문제들 중 처음 마주해서 온전히 제 힘으로 푼 문제는 거의 없네요... 방금 세보니까 행렬제곱, 탑, 크게만들기, 뱀, 카드 정렬하기 해서 딱 다섯개는 어떻게 어떻게 답안의 힘을 빌리지 않고 풀었습니다.

근데 풀면서 느낀게 답안의 힘을 빌렸냐, 안 빌렸냐가 그렇게까지 중요한 요소는 아닌 것 같습니다.

• 일단, 처음 접하는 유형의 문제는 아예 생각이 나지 않는 경우도 많은데, 이런 경우는 답안을 빨리 체크하고 해당 문제를 다루는 사고의 과정을 익히는 것이 더 효율적인 것 같습니다.
• 또, a방식으로 해결한 문제라고 해도, b등의 다른 방식으로 풀 수 있는데, 한 문제에 대한 여러 접근 방법을 확인하면서 문제를 마주했을때 접근하고 해결할 수 있는 카드들을 여러개 구비할 수 있도록 하는게 좋은것 같습니다.

그니까... 답을 보냐 안보냐가 중요한건 아니고, 문제에 대한 접근과, 접근에서 파생되는 논리적인 흐름을 잘 익히는게 더 중요한 것 같다.. 뭐 그런 생각을 했습니다.

사실 한 주 내내 주구장창 알고리즘만 풀어서 별로 쓸 말이 없기에, 복기하면 좋을만한 문제 풀이 몇가지만 남기겠습니다.

가장 가까운 두점

문제 분류에 "기하학" 이 있길래 살짝 쫄았습니다.
제가 문과라 수학만 보면 긴장해서..
근데 막상 풀어보니 "기하학"이 뭔지는 여전히 모르겠다만, x축 y축에 대한 이해만 있으면 충분히 풀 수 있는 문제였습니다.

아이디어는 이러합니다.
1. 좌표들을 x축 기준으로 양분하여서, 각 사이드에서 가장 작은 점을 찾아냅니다. 이를 minVal이라 하겠습니다.
2. 좌, 우측 영역에서 제일 작은 점의 거리는 찾았으나, 두 영역에 걸쳐있는 점의 거리를 최솟값에 반영해주지 않았습니다. 이때 "걸쳐있는 점들"을 모두 탐색하지 않고, 시간 효율을 위하여 바운더리를 정해줍니다.
3. 첫번째 바운더리는 x축 기준입니다. x축 단일 거리를 기준으로, 기존에 두 영역을 양분했던 mid 점 까지의 거리가 minVal 미만인 점들을 필터링합니다.
만약에 어떠한 점에서, mid까지의 수평 거리가 minVal이상이라면, 어차피 해당 점에서 다른 영역의 점까지의 거리가 minVal보다 더 작은 값이 될 수 없기에 이렇게 필터링을 해줍니다.
4. 다음 바운더리는 y축입니다. 앞서 x축 기준의 필터링을 진행할때에는 이미 x축으로 오름차순 정렬이 돼있었지만, 이번에는 아니기에 y축을 기준으로 정렬을 해줍니다.
이때, 밑의 점부터, 자신 위의 점들에 대해 거리를 확인하는데, 만약에 나의 위의 점들 중, 나와의 y축 거리가 minVal 이상이 나오는 경우, 이제 그 점 이후로는 앞서 x축의 경우와 마찬가지로 minVal을 업데이트할 가망이 없는 아이들만 나올 것이기에, break을 걸어줍니다.
5. 1~4의 양측 분할 후 가장 가까운 점 구하기 -> 영역을 걸치는 점들 중 더 가까운 거리를 가지는 점이 있는지 확인하기...의 분할정복 방식을 재귀적으로 되풀이해줍니다.

코드는 다음과 같습니다

import sys

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

points = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
points.sort()

def dist(a , b):
    return (a[0] - b[0])**2 + (a[1] - b[1])**2

left = 0
right = len(points) - 1

def computeMin(left, right): 
    if right - left == 1:
        return dist(points[right], points[left])
    
    mid = left + (right - left) // 2

    minVal = min(computeMin(left, mid), computeMin(mid, right))

    target = []
    # O(N)
    for i in range(left, right + 1):
        if (points[i][0] - points[mid][0]) ** 2 < minVal: # mid까지의 x거리가 minVal과 같은것은 고려할 필요가 없다
            target.append(points[i])
    
    target.sort(key = lambda x: x[1]) 
    
 
    for i in range(len(target) - 1):
        for j in range(i + 1, len(target)):
            if (target[i][1] - target[j][1]) ** 2 < minVal:
                minVal = min(minVal, dist(target[i], target[j]))
            else:
                break

    return minVal

print(computeMin(left, right))

원 영역

x 단일 축만 고려하면 되고, 서로 교차하지 않는 것을 미리 캐치한다면 조금 덜 당황할 수 있는 문제라 생각합니다.

아이디어는 다음과 같습니다
1. 입력받은 원들에 대해 왼쪽 위치와 오른쪽 위치를 기록해줍니다 - ("L또는R", 위치) 모양의 튜플 사용.
2. 1의 튜플들을 담은 points 배열을 위치 기준 오름차순, 같다면 R이 먼저오게 정렬합니다.
3. 스택을 하나 두고, points배열을 순회합니다.
4. 이때 L을 만나면 스택에 넣습니다. 이 L은 추후에 스택에서 꺼내짐으로써 하나의 원을 완성하는 요소입니다.
5. R을 만나면 어떠한 원의 x축 오름차순 기준 종단점에 다다른 것이기에, 스택에 있는 값들을 꺼내면서 해당 원에 대한 정보를 확인해야 합니다.
6. 스택에서 꺼내는 과정에서, "C"를 만나면 현재 확인하는 원의 내부 원이기에 내부 원의 넓이에 더해줍니다
7. "L"을 만나면 앞서 말했듯이 원의 왼쪽 끝에 다다른 것이기에, 앞서 "C"를 만나는 순간마다 계산했던 내부 원들의 넓이와 현재 원의 넓이를 비교해주어 영역을 결정합니다.
8. 마지막으로 현재의 원은 또 다른 큰 원의 일부가 될 수 있기에, "C"태그를 활용하여 다시 스택에 넣어줍니다.

import sys

input = sys.stdin.readline

n = int(input())

# 좌표배열 
points = []
for _ in range(n):
    x, r = map(int, input().split())
    points.append(("L", x - r))
    points.append(("R", x + r))

points.sort(key = lambda x: (-x[1],x[0]), reverse=True) # 숫자 오름차순, 같으면 R먼저오게(문자 내림차순) 

stk = []
area = 1

for i in points:
    if i[0] == "L":
        stk.append(i)
        continue

    # i[0] 이 R인 경우 
    right = i[1]
    width = 0

    while stk:
        poped = stk.pop()

        if poped[0] == "C": # ("C", 왼쪽, 오른쪽 순서)
            width += poped[2] - poped[1]

        elif poped[0] == "L":
            left = poped[1]

            if right - left > width:
                area += 1
            
            else:
                area += 2

            stk.append(("C", left, right))
            break
    
print(area)

히스토그램에서 가장 큰 직사각형

이게 제일 어려웠습니다.

스택을 활용하여 푸는 방법 / 분할정복을 활용하여 푸는 방법 두가지가 존재합니다.

스택을 활용하여 풀려면
1. 높이를 기록하는 스택
2. 위치를 기록하는 스택, 두가지가 필요합니다.
3. 각 직사각형에 대해 for문을 돌면서,
4. 높이 스택이 존재하지 않거나, 높이스택의 맨 위 값이 현재 높이보다 작으면 현재 높이와 현재 위치를 스택에 기록해줍니다
5. 반대로, 현재 높이보다 스택의 맨 위 값이 크면, 그 높이의 사각형이 경우, 종결이 필요합니다. 따라서 높이 스택과 위치스택에서 각각 값들을 pop해주어서, size를 구해주고, 최대 사이즈인지를 확인합니다.
이 행위를 스택 꼭대기의 값이 현재 높이값보다 큰 조건이 반복되는 동안 계속해줍니다.
6. 그리고 현재 높이와, 위치를 스택에 기록해줘야 하는데, 이때 Pstk(위치 스택)의 경우, 가장 마지막으로 위치스택에서 나온 위치값을 넣어줍니다. 왜? 스택에서 빠져나오는 값들은 현재 막대기 왼쪽(이전)의 값들인데, 마지막으로 나온 값의 위치까지는 다 현재 높이보다 높았기 때문에, 해당 위치에서 "현재 막대기 높이의 직사각형" 이 시작한다고 볼 수 있기 때문입니다.
7. 모든 for문을 다 돌더라도 여전히 스택에 값들이 존재할 수 있습니다. 계속 자신의 위로 더 큰 값들이 쌓여와서 종결할 기회를 얻지 못한 경우들입니다. 따라서 이들 높이와 위치를 스택에서 꺼내면서 maxSize를 업데이트 시켜줍니다.

import sys

cases = []
while True:
    tmp = list(map(int, sys.stdin.readline().split()))

    if tmp[0] == 0:
        break

    cases.append(tmp[1:])

for hist in cases:
    Hstk = []
    Pstk = []
    maxSize = -sys.maxsize - 1

    for pos in range(len(hist)):
        h = hist[pos]

        if not Hstk or h > Hstk[-1]:
            Hstk.append(h)
            Pstk.append(pos)
        
        elif h < Hstk[-1]:
            while Hstk and h < Hstk[-1]:
                tempH = Hstk.pop()
                tempP = Pstk.pop()
                tempSize = tempH * (pos - tempP)
                maxSize = max(maxSize, tempSize)

            Hstk.append(h)
            Pstk.append(tempP)
    
    while Hstk:
        tempH = Hstk.pop()
        tempP = Pstk.pop()
        tempSize = tempH * (pos - tempP + 1)
        maxSize = max(maxSize, tempSize)

    print(maxSize)

분할정복으로도 문제를 해결할 수 있습니다.
앞서 "가장 가까운 두 점 구하기"와 비슷하게, 왼쪽 영역에서의 높이, 오른쪽 영역에서의 높이 중 최대 높이를 구한후, 가운데를 포함하는 영역의 높이를 마지막으로 비교해주어 최대 영역을 구하는 방식입니다.

이때, 가운데를 포함하는 영역을 구하는 방법은 다음과 같습니다.
mid에서 시작하는 두개의 포인터를 두고, 우측 진행 방향과 좌측 진행 방향 중 더 큰 쪽으로 영역을 넓힙니다. 이때, 높이는 현재까지의 높이와 , 진행방향의 높이 중 더 낮은것을 선택합니다(더 큰쪽을 기준으로 높이를 선택하면 가능한 크기보다 더 큰 넓이의 사각형을 계산하게 됩니다).
높이와, 두개 포인터간의 차이를 통해 최대 영역을 업데이트 해줍니다.

좌측 또는 우측 중에서 어느 한쪽 끝에 다다르면, 앞서의 방식을 적용하여서 남은 방향에 대해 최대영역에 대한 업데이트를 진행해줍니다.

import sys

cases = []
while True:
    tmp = list(map(int, sys.stdin.readline().split()))

    if tmp[0] == 0:
        break

    cases.append(tmp[1:])

def getMidArea(lo, hi, mid, hist):
    toLeft = mid
    toRight = mid

    height = hist[mid]

    maxArea = height

    while lo < toLeft and hi > toRight:
        if hist[toLeft-1] < hist[toRight+1]:
            toRight += 1
            height = min(hist[toRight], height)
        else:
            toLeft -= 1
            height = min(hist[toLeft], height)
        
        maxArea = max(maxArea, height * (toRight - toLeft + 1))
    
    # 왼쪽 또는 오른쪽 끝에 다다름 
    while toLeft > lo:
        toLeft -= 1 
        height = min(hist[toLeft], height)
        maxArea = max(maxArea, height * (toRight - toLeft + 1))
    
    while toRight < hi:
        toRight += 1 
        height = min(hist[toRight], height)
        maxArea = max(maxArea, height * (toRight - toLeft + 1))
    
    return maxArea
    
def getArea(lo, hi, hist):
    if lo == hi:
        return hist[lo]

    mid = lo + (hi - lo) // 2

    leftArea  = getArea(lo, mid, hist)
    rightArea = getArea(mid + 1, hi, hist)

    maxArea = max(leftArea, rightArea)

    # lo ~ hi구간의 최대넓이 구현
    maxArea = max(maxArea, getMidArea(lo, hi, mid, hist))
    
    return maxArea

for hist in cases:
    print(getArea(0, len(hist) - 1, hist))