알고리즘 스터디 기록 24.01.06

23년 여름 대회 참가를 위해서 급조(?)한 팀이 같은 뜻을 가지고 오래 지속되어 기쁘다. 대회 이후에도 쭉 같이 스터디를 하고 내용을 기록하고 있다. 다만 블로그에 전부 올리기는 무리라서.. 지금까지 한 번도 안올렸는데, 중간 점검 차원에서 블로그에 포스팅하게 되었다.

아무래도 우리 학교는 알고리즘보다 개발 동아리/개발쪽 행사들이 메인인 분위기라서 같이 알고리즘 공부할 사람을 찾는 게 어렵다. 그나마 찾으려고 하면 거의 졸업할 때 쯤 코테를 준비하느라 효율적으로 몇문제 푸시는 분들 정도? 그동안 교내 자율 스터디에 조금씩 참여했었는데 다들 하루 한문제 인증만 하는 식이고, 알고리즘에 대해서 더 공부하거나 같이 이야기를 나누거나 하는 일은 없었다. 아무래도 알고리즘에 재미를 붙이고 쭉 이어나가는 사람은 적은 것 같다. 23년 초에는 이렇게 체념하고 있었고... 그 이후로 만나게 된 우리 스터디원들을 통해서 "아직 희망이 있구나..?!" 하고 생각했다. 소중한 인연이다.

방학이 시작하고 나서 주 1회 모임을 가지고 있다. 그동안 웰노운 문제들을 같이 풀어보았는데, 매주 주제를 바꿔가면서 해당 주제에 대한 문제를 하나씩 가져와서 공유하는 식으로 진행했다. 문제에 대해 혼자 아이디어나 풀이를 생각한 다음 서로 의견을 나누면서 풀이를 찾고, 코드를 완성하는 식이다. 또한, 본인이 준비해온 문제는 모든 팀원이 이해할 수 있게 설명할 수 있어야 한다.

그동안 진행했던 주제는 DP, 수학, 기하, 세그트리였고, 24년 1월 6일자 모임에서는 100% 자료구조로 이루어진 문제-자료구조가 풀이에 핵심 포인트인 문제..를 선정했다.

문제 준비 과정에서 서로 이야기한 것도 없는데 마치 짜온 것처럼 셋 다 우선순위 큐 문제를 들고왔다..ㅎㅎ 아무래도 자료구조를 키워드로 문제를 찾다보니 우선순위 큐로 값을 관리해주면서 후처리에 무언가를 더 추가하는? 식의 문제가 많았던 것 같다.

내가 고른 문제는 1655번(https://www.acmicpc.net/problem/1655) 이었는데, 나만 모르는 웰노운 같은 문제이다. 우선순위 큐로 중간값을 max heap의 top 위치에 계속 올라가게 관리해주는 문제였다. 처음에 이 문제를 풀 때, 시간 제한 조건을 보고 뭔가 중간값을 항상 쉽게 알 수 있는? 트릭? 이 있지 않을까 고민하다가 우선순위 큐를 떠올렸다. 

웰노운 모르면 손해?니까 팀원들에게도 알려주자!! 라는 마인드로 준비했다. 아마 팀원들 중에서 예전에 풀었던 사람도 있을 것 같다. 그래도 이 문제를 리마인드 하면서 다른 우선순위 큐를 사용하는 문제들에 접근하기 더 쉬워진 것 같다.

[max heap] / 중간값 (max heap의 top) / [min heap] 이런 모양새를 생각하면 된다. 홀짝을 잘 구분해서 중간값이 항상 max heap의 top에 위치하게끔 만들고, 중간값과 다음 입력으로 들어오는 수를 비교하면서 두 힙에 적절하게 나눠서 넣어주면 된다. 나는 편의상, 중간값을 기준으로 작은 수를 왼쪽에 있다고 생각하고 left라는 이름의 max heap을 만들었고 큰 수들을 right라는 이름의 min heap으로 만들어서 넣어주었다. 중간값 관리는.. 일단 홀짝 나눠서 heappush 해준다음에 left top, right top 비교하면서 값을 옮겨주는 식으로 진행했다.

import sys
input = sys.stdin.readline

n = int(input())
left = [] #max heap
right = [] #min heap

import heapq as hq

for i in range(n):
    now = int(input())
    if len(left) == len(right):
        hq.heappush(left, -now)
    else:
        hq.heappush(right, now)

    if right and right[0] < -left[0]:
        left_top = -hq.heappop(left)
        right_top = hq.heappop(right)
        hq.heappush(left, -right_top)
        hq.heappush(right, left_top)

    print(-left[0])

 

H벗이 준비한 문제는 13334번(https://www.acmicpc.net/problem/13334) 이었다. 이 문제도 역시 우선순위 큐를 사용하는 문제였는데, 추가로 스위핑 기법까지 사용하는 문제이다. 스위핑 Sweeping은 쓸다는 뜻으로, 한 쪽에서 시작해서 다른 방향으로 쭉 쓸어나가듯이 스캔하는 것이라고 한다... 이 문제를 풀면서 어디서 들어본 적 있었던 스위핑 단어의 뜻을 알게 됐다.

L 선분의 길이 d와 같거나 작은 선분들을 골라서 리스트에 넣고 선분이 끝나는 좌표를 기준으로 정렬한 후,  맨 앞부터 차근차근 heap에 넣을지 말지 조건을 관리해준다. heap이 비어있으면 우선 하나 집어넣고, 그 다음에 오는 좌표를 보고 길이 d에 만족하는지 아닌지 체크해준다. 이런식으로 heap에 넣을 수 있는 최대 좌표 개수를 찾으면 된다.

import sys
input = sys.stdin.readline
n = int(input())
arr = []

for i in range(n):
    arr.append(list(map(int, input().split())))
d = int(input())

check = []
for node in arr:
    h = node[0]
    o = node[1]
    if abs(o-h) <= d:
        check.append([min(h, o), max(h, o)])

check.sort(key=lambda x:x[1])

import heapq as hq

h = []
res = 0
for node in check:
    if not h:
        hq.heappush(h, node)
    else:
        while h[0][0] < node[1]-d:
            hq.heappop(h)
            if not h:
                break
        hq.heappush(h, node)
    res = max(res, len(h))
print(res)

 

마지막 문제는 M벗이 준비한 앳코더 문제이다. ABC325 라운드의 D번 - Printing Machine (https://atcoder.jp/contests/abc325/tasks/abc325_d)

앳코더 특유의 스타일이 있는데, 문제 지문을 간결하게 하려고 설명을 충분히 해주지 않기 때문에 한 문장씩 조건을 계속 떠올리면서 풀이를 진행해야한다... 이 문제를 처음 봤을때도 마찬가지로 문제 지문만으로는 정확히 뭐를 해서?? 뭐를 구하라는지?? 이해가 안됐다. 그래서 예제를 보고 생각해보면서 + M벗의 설명을 듣고서야 이해했다.

코포 스타일은 지문이 더 긴 편이고, 문제 상황을 풀어서 설명해주는 경우가 많다보니 앳코더 지문이 뭔가 불친절하다고 느껴졌다. 이에 비해 점수나 결과, 시스텟은 코포보다 더 친절하고 빠른 ㅋㅋㅋㅋ 각자 나름의 장점이 있는 것 같다.

사실 이 문제... M벗 설명을 들었을 때 그럭저럭 이해가 갔는데 백지 창에서 다시 풀어보려니까 또 생각을 하게 된다... 나중에 완전히 업솔빙해서 코드를 올릴 생각이다.

 

+ 계속 이 모임을 이어나가면서 다양한 문제들을 같이 풀어보고 싶다. 아마 졸업하고 나면.. 학부생 신분으로 대회 나가는게 무리니까.. 학교 이름을 달고 하는 마지막 활동이라고 생각하고 임해야겠다.