AtCoder ABC #309 UpSolving + 첫 앳코더 후기

1. 앳코더를 신청한 계기

BOJ 문제를 100일 넘게 꾸준히 풀면서 점점 문제 푸는데에 긴장감이 없어지는 것 같았다. 시간 제한이 있는 것도 아니고, 내가 풀고 싶은 시간 아무때나, 난이도를 자유롭게 골라서 풀면 되는 점이 오히려 역효과로 작용했다.

이 역효과에 대해 좀 더 자세히 설명하자면, 내 컨디션에 맞춰서 문제 풀이가 느슨해진다는 점이다. 매일 어려운 문제, challenging 한 문제, 새로운 알고리즘에 도전해야 실력이 빨리 늘텐데 앞으로 나아가기 보다 쉬운 문제를 풀면서 제자리에 안주하는 느낌이 들기 시작했다. 별로 배운 것도 없는 수준이고, 다른 사람들이 웰노운이라고 말하는 것조차 다 소화하지 못했는데도 내가 피곤하다는 이유, 시간이 모자라다는 이유 등으로 새로운 것을 배우는데에 게을러졌다.

그래서 방학이기도 하니, CP를 다시 열심히 해야겠다고 생각했다. 아직 랜디 실력도 부족해서 contest의 앞부분을 빨리, 정확하게 푸는 것을 연습하고 시간 내에 못 푼 문제들을 모아 업솔빙하는 식으로 발전 속도에 박차를 가하려고 한다. 물론 지금 계절학기를 듣느라 오전 시간이 아예 없지만, 남은 오후 시간에 PS/CP/개발까지 꽉 채워서 알찬 일정을 소화하지 않으면 안되는 시기가 왔음을 직감했다.

여태껏 그랬듯이 하면 된다는 마음가짐으로 처음으로 앳코더 ABC를 신청했다.

 

2. ABC #309

앳코더의 첫인상을 말해보자면, "앳코더스럽다", "앳코더스러운 문제다" 라는 다른 PS러들의 말이 무엇인지 알게 된다. CF에는 엄청 긴 지문과 그 속에서 그리디, 규칙 등을 찾아내는 종류가 많았다면, 앳코더는 이와 반대로 깔끔하고 짧은 지문이 인상 깊었다. 아무래도 영어로 문제를 풀어야 하는 입장에서, 영어가 모국어만큼 자유롭지 않다면 CF 지문의 긴 요구사항을 놓치기 쉽다. (실수하기 쉽다는 의미 + pre-test system도..) 그러나 앳코더는 지문이 짧고 깔끔해서 푸는 사람이 이해하기 쉬웠고, 대신 그것을 구현하기 위한 아이디어와 알고리즘을 떠올리는 시간에 더 길게 투자해야하는 느낌이었다.

 

---

 

A. Nine

앳코더가 처음인 나에게 A는 약간의 충격이었다. 이렇게나 쉬운 문제가 나오다니..? 예상을 못하고 5분 정도 당황했다. 처음에는 3x3 그래프에서 수평 인접, 수직 인접 case를 다 구하는 것이라고 생각해서 그렇게 코드를 짜다가... "Horizontally" 라는 단어를 보고.. 와 정말 수평 인접 여부 하나만 구하면 돼? 그렇게 쉬워? 라는 감탄사를 연발하며 쉽게 AC를 받았다.

내가 짠 코드는 B-A 의 차가 1이고, 같은 row에 속하면 인접하다고 판단했다. 다른 사람의 코드를 구경해보니 다들 비슷하게 풀었는데, 아이디어 중에서 같은 row를 판별할 때 i%3 을 이용해서 수평 인접이라고 판단한게 인상 깊었다. 왜냐하면 나는 그냥 정직하게 수를 때려박았기 때문.. 이렇게 아이디어를 또 하나 얻었다.

 

B. Rotate

평범한 구현 문제라고 생각했는데, 당시에 너무 피곤해서 구현이 손에 안잡혔다. 좀 더 재밌는 걸 풀고 싶어서 5분정도 고민하다가 C번으로 넘어갔다..

import sys
input = sys.stdin.readline

N = int(input())
A = [list(input().rstrip()) for i in range(N)]
B = []

#Row 1
b = [A[1][0]] + A[0][:N-1]
B.append(b)

#Row 2 ~ Row N-1
for i in range(1, N-1):
    b = [A[i+1][0]] + A[i][1:N-1] + [A[i-1][-1]]
    B.append(b)

#Row N-1
b = A[N-1][1:] + [A[N-2][-1]]
B.append(b)

for i in range(N):
    print("".join(B[i]))

 

 

C. Medicine

보자마자 누적합 + 투포인터 문제라고 생각해서 아는대로 빨리 구현하려고 했다. 첫 제출까지 구현은 나름 빠르게 됐는데 (최근에 투포인터 문제를 두 개정도 풀었던게 기억나서 나름 빨리 됐다) 로직에서 실수한 부분이 있었다.

Day 1부터 -> 2, 3, 4 이렇게 left 포인터만 하나씩 이동하면서 누적합을 계산해주면 되는데 이전에 투포인터를 짤 때 right 포인터도 움직이는 코드를 많이 짜서 그런지 right 포인트 다루는 걸 이상하게 생각해서 삽질을 했다. (이것 때문에 테케가 2개 정도 WA를 받아서 차근차근 로직을 돌아보고 고치다보니 시간이 30분 정도 남았다..)

이런 종류의 실수는 처음이라 차분하게 로직을 떠올리는 것이 중요하다는 걸 배웠다. 내가 삽질한 이유는.. 문제를 빨리 풀어보려고 로직을 완성하지 않고 누적합 + 투포인터 코드를 막 갈기다가 그렇게 된 것이다. 로직을 잘 끝맺은 후에 빠르게 구현하는 방향으로 옮겨야겠다.

아래는 내가 제출하여 AC를 받은 코드이다.

import sys
input = sys.stdin.readline
 
N, K = map(int, input().split())
pre = []
 
for i in range(N):
    a, b = map(int, input().split())
    pre.append((a,b))
 
pre.sort(key=lambda x:x[0])
pre_s = [pre[i][1] for i in range(N)]
 
for i in range(1, N):
    pre_s[i] += pre_s[i-1]
 
left, right = -1, N-1
 
while left < N:
    if left == -1:
        if pre_s[right] <= K:
            print(1)
            sys.exit()
        else:
            left += 1
 
    if pre_s[right] - pre_s[left] > K:
        left += 1
 
    if pre_s[right] - pre_s[left] <= K:
        day = pre[left][0] + 1
        print(day)
        sys.exit()
 
print(pre[-1][0] + 1)

 

 

D. Add One Edge

시간이 남아서 D번 문제를 구경했다. 딱봐도 흥미로운 그래프 문제였는데 지문과 테케를 이해하다가 시간을 다써서 제출하지는 못했다. 나중에 구현하면서 AC 코드를 구경해봤는데 여러 가지 방법을 사용해서 풀 수 있었다.

그 중에서도 매우 흥미로웠던 2 가지 코드를 정리해보았다.

 

1. 우선순위 큐를 이용한 다익스트라

from collections import defaultdict
import heapq
from math import inf
 
def dijkstra(v0,verteces,edges):
    dist = {v:inf for v in verteces}
    dist[v0] = 0
    q = [(0,v0)]
    while q:
        d,u = heapq.heappop(q)
        for v in edges[u]:
            d1 = d+1
            if dist[v] > d1:
                dist[v] = d1
                heapq.heappush(q,(d1,v))
    return dist
 
n1,n2,m = (int(s) for s in input().split())
g1 = defaultdict(list)
g2 = defaultdict(list)
for _ in range(m):
    a,b = (int(s) for s in input().split())
    g = g1 if a <= n1 else g2
    g[a].append(b)
    g[b].append(a)
 
dist1 = dijkstra(1,list(range(1,n1+1)),g1)
dist2 = dijkstra(n1+n2,list(range(n1+1,n1+n2+1)),g2)
print(max(dist1.values())+max(dist2.values())+1)

 

2. BFS 이용

from collections import deque
 
N1, N2, M = map(int, input().split())
adj1 = [[] for _ in range(N1)]
adj2 = [[] for _ in range(N2)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    if u < N1:
        adj1[u].append(v)
        adj1[v].append(u)
    else:
        u, v = u - N1, v - N1
        adj2[u].append(v)
        adj2[v].append(u)
 
 
def bfs(adj, root, inf=10**18):
    n = len(adj)
    que = deque()
    dis = [inf for _ in range(n)]
 
    que.append(root)
    dis[root] = 0
 
    while len(que) > 0:
        u = que.popleft()
        for v in adj[u]:
            if dis[u] + 1 < dis[v]:
                dis[v] = dis[u] + 1
                que.append(v)
 
    return max(dis)
 
d1 = bfs(adj1, 0)
d2 = bfs(adj2, N2 - 1)
print(d1 + d2 + 1)

---

 

3. 다른 사람의 코드를 보면서 느낀 점

나는 코드를 읽기 쉽게 쓰는 편이다. 너무 길지 않게, 주석도 최소로(핵심 아이디어나 꼭 필요한 부분에만) 달려고 하고 변수명도 너무 길거나 짧지 않게 모두 이해할 수 있는 단어를 쓰고 있다. 이번에 다른 사람들이 제출한 코드를 여러 개 살펴보았는데, 실시간 대회 중에 제출한 코드라서 그런지 코드에 막 주석이 20줄 넘게 달려있고.. 작성하다가 만 코드를 집어넣거나 본인의 라이브러리 코드를 엄청 집어넣어놨다가 죄다 주석처리 해버리거나.. 이런 경우가 많이 보였다.

덕분에 알아보기는 힘들었지만 힘든 업솔빙이 나중에 도움이 되겠지..? 하면서 그냥 했다..! << 중요한건 꺾여도 그냥 하는 마음..

+ 본인만의 코드 라이브러리를 준비하면 CP에 도움이 될 것 같다. 문제 푼 시간도 레이팅에 반영되므로 다른 참가자들이 전략적으로 잘 준비했다고 생각했다. 나도 나중에 아는 웰노운 유형이 더 많아지게 되면 나만의 라이브러리 코드를 깃헙에 정리하고 싶다.