Atcoder Beginner Contest 285 후기

A. Edge Checker 2

 주어진 그림과 같은 트리처럼 트리가 구성된다고 할 때 주어지는 두 정점이 부모와 자식관계인지 판별하는 문제이다. 

<그림 1. 문제 예시>

import sys

a, b = map(int, sys.stdin.readline().split())
if max(a, b) == 2 * min(a, b):
    print('Yes')
elif max(a, b) == 2 * min(a, b) + 1:
    print('Yes')
else:
    print('No')

B. Longest Uncommon Prefix

 길이가 n인 문자열 S가 주어지고, n이하인 양수 i가 있을 때 각각의 i에 대하여 $S_{1} \neq S_{1 + i}, S_{2} \neq S_{2 + i} \cdots S_{k} \neq S_{k + i}$를 만족하는 k의 최대값을 구하는 문제이다. 단, i와 k의 합은 n을 초과할 수는 없으며, 그러한 양수 k가 없다면 0을 출력해야 한다.

<그림 1. i가 1인 경우>

 위 그림 1은 예제 입력으로 주어진 abcbac의 경우이다. 우선 i가 1이고 k가 1인 경우라고 생각하면 된다. 현재 빨간색 글자인 a와 b는 다르므로 조건을 만족한다. 이제 k를 늘려보자

<그림 2. i가 1이고 k가 2인 경우>

 위 그림 2는 k를 2로 늘린 그림이다. 역시나 빨간색 글자인 b와 c는 다르므로 조건을 만족한다. 이런식으로 k를 늘려가다보면 k는 3,4,5일때도 모두 만족하기 때문에 k의 최대값은 5가 된다. i와 k를 더한값이 6을 넘을 수는 없음에 유의하자

<그림 3. i가 4이고 k가 1인 경우>

 위 그림 3은 i가 4이고 k가 1인 경우이다. 이 때 빨간색 글자인 a는 서로 같으므로 더 이상 k를 늘릴 수 없다. 따라서 이때는 0을 출력해야 한다. 

import sys

n = int(sys.stdin.readline())
s = sys.stdin.readline().rstrip()
for i in range(1, n):
    val = 0
    for j in range(1, n + 1):
        if j + i - 1< n and s[j - 1] != s[j + i - 1]:
            val = j
        else:
            break
    print(val)

C. abc285_brutmhyhiizp

 알파벳의 길이별로 1차 정렬, 사전 상 순서로 2차 정렬한 결과로 대응되는 순서를 출력하는 문제이다. 따라서, A는 1이고 Z는 26, AA는 27 등이다. 즉, 알파벳 대문자로 주어지는 26진수를 10진수로 변환하는 문제이다. 

import sys, string

s = sys.stdin.readline().rstrip()
n = len(s)
ans = 0
for i in range(n - 1, -1, -1):
    ans += pow(26, n - 1 - i) * (ord(s[i]) - ord('A') + 1)
print(ans)

D. Change Usernames

 n명의 유저가 있고 각각 현재 자신의 닉네임과 바꾸고 싶은 닉네임이 입력으로 주어진다. 이 때 한번에 한명의 유저의 닉네임만 바꿀 수 있으며 한명의 닉네임을 단 한번만 바꿀 수 있고 바꾼 이후에 같은 닉네임이 존재하면 안된다는 규칙을 만족하면서 n명의 유저의 닉네임을 바꿀 수 있는 방법이 존재하는지 묻는 문제이다.

 간단하게 방향 그래프로 모델링 후 사이클을 검출할 수 있는지를 묻는 문제이다. 만약 사이클이 아니라면 방향 그래프 상에서 가장 마지막에 도착하는 유저를 바꿔주는 방식으로 닉네임을 바꿔주면 모든 조건을 만족할 수 있지만, 사이클이 있다면 같은 닉네임이 존재하기 때문에 조건을 만족할 수 없다

<그림 1. 예제 입력 3번의 그래프 모델링>

 위 그림 1은 문제의 예제 입력 3번을 그래프 모델링을 시각화한 그림이다. 각 사람 밑에 있는 글자는 슬래시를 기준으로 왼쪽은 현재의 닉네임, 오른쪽은 바꾸고 싶은 닉네임이라고 생각하면 된다. 따라서 1번 밑에 있는 aaa / bbb는 1번의 현재 닉네임은 aaa이고, 바꾸고 싶은 닉네임은 bbb라는 뜻이다. 따라서, 현재 임의의 유저가 바꾸고 싶은 닉네임을 현재 닉네임으로 사용하고 있는 유저를 방향 그래프로 모델링하면 된다. 

 만일 현재 그림 1의 경우처럼 사이클이 없는 경우라면 3번, 5번, 1번순으로 닉네임을 바꾸면 된다. 2번과 4번은 아무 순서나 상관없다. 그러나, 사이클이 있는 경우라면 조건을 만족하지 않는다. 따라서 시간복잡도는 일반적인 dfs와 동일하기에 n이 $10^5$이라고 하더라도 시간안에 충분히 정답을 도출할 수 있다

import sys

# 재귀깊이 해제
sys.setrecursionlimit(200000)

# dfs : 현재 now번째 정점에서 사이클이 검출되는지를 리턴하는 함수
def dfs(now):
    vis[now] = True
    for next in adj[now]:
        if not vis[next]:
            if dfs(next):
                return True
        elif not fin[next]:
            return True
    fin[now] = True
    return False

# 입력부
n = int(sys.stdin.readline())
# s : 현재 유저의 닉네임을 key, 현재 유저의 인덱스를 value로 갖는 dictionary
s = dict()
# e : 현재 유저의 바꾸고 싶은 닉네임을 key, 현재 유저의 인덱스를 value로 갖는 dictionary
e = dict()
arr = []
for i in range(n):
    temp = list(sys.stdin.readline().split())
    s[temp[0]] = i
    e[temp[1]] = i
    arr.append((temp[0], temp[1]))
    
# adj : 인접 그래프
adj = [[] for _ in range(n)]
# vis : 정점 방문 여부를 저장하는 배열
vis = [False] * n
# fin : 정점이 순회를 마쳤는지를 저장하는 배열
fin = [False] * n

# 현재 유저의 바꾸고 싶은 닉네임을 자신의 닉네임으로 가지고 있는 유저와 연결
for i in range(n):
    if arr[i][1] in s:
        adj[i].append(s[arr[i][1]])
        
# 사이클 검출 후 정답 출력
for i in range(n):
    if not vis[i]:
        if dfs(i):
            print('No')
            sys.exit(0)
print('Yes')

E. Work or Rest

 한 주가 n일이며 휴일이 반드시 하루는 있어야 하며 각각의 날에 대응되는 생산성이 존재한다. 평일의 경우 몇일 전에 휴일이었는지와 앞으로 몇일 뒤에 휴일인지를 계산하여 그 중 더 작은 값의 생산성을 해당 평일의 생산성으로 정의하고 휴일의 생산성은 0으로 할 때, 적절히 휴일의 정하여 얻을 수 있는 생산성의 최대값은 얼마인지 구하는 문제이다

<그림 1. 예제 입력 1의 경우>

 위 그림 1은 예제 입력 1에서 휴일을 1번째와 3번째 날(빨간색 글자)로 지정한 경우이다. 이 때 6번째 날의 생산성을 구해보자. 우선 6번째 날 기준으로 가장 최근의 휴일은 3번째 날이었다. 또한 앞으로 다가올 휴일은 다음주 1번째 날이다. 따라서, 가장 최근의 휴일과 6번째 날의 거리는 3일, 앞으로 다가올 휴일과 6번째 날의 거리는 2일이다. 따라서, 문제의 조건에 따라 더 작은 일수인 2일의 생산성이 6일의 생산성이 된다. 즉, 6일의 생산성은 $arr[min(2, 3)]$이 된다.

 이런 논리로 휴일을 제외한, 즉 1번째 날과 3번째 날을 제외한 나머지 평일의 생산성의 합은 50이 되며 50보다 더 큰 생산성을 만들 수는 없다. 브루트 포스로 모든 조합의 수를 검사한다면 $2^{5000}$이기 때문에 절대로 시간안에 답을 낼 수 없다.

<그림 2. n이 10인 임의의 경우>

 위 그림 2는 n이 10이고 0번째 날, 1번째 날, 5번째 날이 휴일로 지정된 경우를 나타낸 그림이다. 각 평일날마다 글자가 하나 더 씌여있는데, 이는 가장 최근의 휴일과 앞으로의 휴일 중 더 작은 일수를 나타낸 것이다. 예를 들어 7번째 날을 기준으로 하면 가장 최근의 휴일은 2일 전의 5번째 날이었고 앞으로의 휴일은 3일 뒤인 다음주 0번째 일이기 때문에 더 작은 2가 쓰인것이다. 

 여기서 약간의 관찰을 통해 규칙을 파악할 수 있다. 두 휴일이 정해지는 순간 해당 휴일에 속한 평일 구간의 생산성은 정해진다는 것이다. 왜냐하면 결국 정확히 가장 최근의 휴일과 앞으로의 휴일이 절반이 되는 거리를 기준으로 대칭이 되기 때문이다. 예를 들어 3번째 날을 생각해보자. 3번째 날은 두 휴일인 1번째 날과 5번째 날의 정확히 중간이다. 따라서 어디를 고르든 상관이 없으므로 2이지만, 3을 기준으로는 1번째날과 4번째 날이 서로 1로서 대칭을 이루는 모습을 보인다. 

 따라서, 두 휴일 간의 거리가 짝수이고 거리를 l이라고 할 때, 두 휴일에 속한 평일들의 생산성의 합은 $arr[0] + arr[1] + \cdots + arr[\left \lfloor \frac{l}{2} \right \rfloor - 1] + arr[\left \lfloor \frac{l}{2} \right \rfloor  - 2] + arr[\left \lfloor \frac{l}{2} \right \rfloor  - 3] + \cdots + arr[0]$이다. (0-base index임에 주의하자. 1-base index로 풀어도 무방하다)

 또한, 두 휴일 간의 거리가 홀수이고 거리를 l이라고 할 때, 두 휴일에 속한 평일들의 생산성의 합은 $arr[0] + arr[1] + \cdots + arr[\left \lfloor \frac{l}{2} \right \rfloor - 1] + arr[\left \lfloor \frac{l}{2} \right \rfloor - 1] + arr[\left \lfloor \frac{l}{2} \right \rfloor - 2] + \cdots + arr[0]$이다.

 그런데 자세히 살펴보면 이는 위는 누적합으로도 나타낼 수 있기에, 식을 정리하면 두 휴일 간의 거리가 짝수인 경우에는 $arr[\left \lfloor \frac{l}{2} \right \rfloor - 1] + 2 * pf[\left \lfloor \frac{l}{2} \right \rfloor  - 2]$이고 두 휴일 간의 거리가 홀수인 경우에는 $2 * pf[\left \lfloor \frac{l}{2} \right \rfloor  - 1]$이다.

<그림 3. 예외 케이스>

 위 그림 3은 그림 2에서 관찰한 성질에 위배되는 예외 케이스를 나타낸 그림이다. 우선 그림 3의 좌측 상단부터 보자. 0과 1사이의 2는 최근의 휴일인 1번째 날로부터도 하루만 떨어져 있고, 앞으로 다가올 다음주 0번째 날로부터도 하루만 떨어져 있고 이미 구한 일반화에 대입해도 문제가 되는 부분은 없다. 그러나, 좌측 하단의 0번째 날과 1번째 날 사이도 엄연히 두 휴일로 이루어진 구간이다. 단지 평일이 없을 뿐이다. 그런데 위에서 구한 일반화에 대입하면 인덱스가 음수가 나오게 된다. 파이썬과 같이 음수 인덱스를 지원한다고 해도 이것은 문제가 된다. 어쩌면 더 심각한 문제가 될 수도 있다. 왜냐하면 현재 0번째 휴일과 1번째 휴일 사이의 평일이 없기 때문에 좌측 하단에서 구할 수 있는 생산성은 0이지만, 음수 인덱스를 지원하게 되면 0이 아닌 다른 값으로 왜곡된 생산성이 더해질 수 있기 때문이다. 

 마찬가지로 우측 상단을 보자. 우측 상단은 3번째 날과 3번째 날 사이의 3개의 평일들로 이루어진 구간, 즉 두 휴일 간의 실제 거리는 4일인 구간이다. 그림 2에서 정의한 공식은 실제로 서로 다른 두 휴일을 전제로 만든 것이기 때문에 우측 상단 그림과 같이 서로 같은 두 휴일이라면 두 휴일의 거리는 0이기 때문에 실제로는 0번째 날, 1번째 날, 2번째 날의 생산성을 가져갈 수 있음에도 그렇지 못하게 되는 왜곡이 발생할 수 있다. 따라서 좌측 하단과 우측 상단과 같은 경우의 예외를 적절히 처리하여야 한다.

 결국 해당 문제는 2차원 다이나믹 프로그래밍 문제로 해결할 수 있다. 상태 공간을 현재 now번째 날이고 이전에 뽑은 휴일이 prev번째 날일 때 얻을 수 있는 생산성의 최대값이라고 정의하자. 그런데 이 문제는 일반적인 다이나믹 프로그래밍이 아니라 원형 다이나믹 프로그래밍이기 때문에 마지막 구간을 유의해야 한다

<그림 4. n이 7인 임의의 경우>

 위 그림 4는 n이 7이고 휴일이 1번째 날, 4번째 날, 6번째 날인 경우를 나타낸 그림이다. 여기서 각 구간은 같은 색의 실선으로 나타내었다. 1번째 날부터 4번째 날까지의 구간은 보라색이며 4번째 날부터 6번째 날까지의 구간은 주황색, 마지막으로 6번째 날부터 1번째 날까지의 구간은 초록색으로 나타냈다. 

 이 때 상태 공간의 정의대로 가령 1번째 날을 첫번째 휴일로 뽑고, 4번째 날을 두번째 휴일로 뽑고 6번째 날을 마지막 휴일로 뽑는 경우를 생각해보자. 1번째 날을 휴일로 이미 뽑고 4번째 날을 새로운 휴일로 뽑는 순간, 즉 now가 4이고 prev가 1일 때 보라색 구간의 생산성은 얻을 수 있다. 왜냐하면 위 그림 2에서 정의한 일반화 공식으로 O(1)만에 구할 수 있기 때문이다. 그 다음으로 4번째 날을 이미 휴일로 뽑고 6번째 날을 새로운 휴일로 뽑는 순간, 즉 now가 6이고 prev가 4인 경우라면 마찬가지로 주황색 구간의 생산성은 얻을 수 있다. 

 그런데 초록색 구간을 얻으려면 1번째 날을 다시 휴일로 뽑아야 하는데, 그러기 위해서는 now는 6이고 prev는 1이어야 한다. 또한 한바퀴를 모두 돌았기 때문에 더이상의 상태 전이가 일어나서는 안된다. 그런데 현재 now나 prev만 가지고는 어디가 시작점이었는지를 모르기 때문에 최초로 뽑은 휴일의 정보를 가져야 한다. 그런데 최초로 뽑은 휴일은 상태 전이에 있어서 변하는 정보는 아니기 때문에 상태공간의 차원이 3차원이 되지는 않기 때문에 복잡도가 증가하지는 않는다.

 그런데 마지막 구간인 초록색 구간을 계산할 때 이미 그림 2에서 정의한 일반화 공식을 쓸 때 일주일이 넘어가는 경우는 반드시 더 작은 수에 n을 더해줘야 올바른 거리를 구할 수 있다. 6번째 날과 1번째 날의 거리는 실제로는 (1 + 7) - 6 = 2일이 됨에 유의하자. 추가로, 마지막 구간을 구해주는 경우는 base case에서 처리해야 함에 유의하자.

 따라서, 상태 공간을 재정의하면, 현재 now번째 날이고 이전에 뽑은 휴일이 prev번째 날이며 가장 처음에 뽑은 휴일이 first일 때 얻을 수 있는 생산성의 최대값으로 정의할 수 있다. 점화식은 아래와 같은데, 점화식에서 등장하는 calc 함수는 특정 두 휴일에 속한 구간의 생산성의 총합을 누적합을 이용하여 O(1)만에 계산하는 함수이다. $$dp[now][prev] = max(dp[now][prev], dp[now + 1][now] + calc(now, prev), dp[now + 1][prev])$$

// 파이썬으로 같은 로직을 수행 시 TLE 이슈로 인해 C++ 코드로 첨부

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

// dp : 현재 now번째 날이고 이전에 뽑은 휴일이 prev번째 날이며 가장 처음에 뽑은 휴일이 first일 때 
//      얻을 수 있는 생산성의 최대값을 저장하는 2차원 배열
ll dp[5000][5000];
int n;
// arr : 현재 날짜의 생산성을 저장하는 배열
ll arr[5000];
// pf : 생산성의 누적합을 저장하는 배열
ll pf[5000];

// calc : 두 휴일 사이의 생산성의 합을 리턴하는 함수
ll calc(int now, int prev) {
    // 두 휴일 간의 거리가 1보다 작은 경우 예외처리
    if (abs(now - prev) <= 1) {
        return 0;
    }
    // 두 휴일 간의 거리가 짝수인 경우
    else if (abs(now - prev) % 2 == 0) {
        // 두 휴일 사이에 평일이 하나만 있는 경우라면 누적합이 필요없으며
        // 두 휴일 사이에 평일이 복수개 있는 경우라면 누적합이 필요하다
        return abs(now - prev) / 2 - 1 == 0 ? arr[abs(now - prev) / 2 - 1] : arr[abs(now - prev) / 2 - 1] + pf[abs(now - prev) / 2 - 2] * 2;
    }
    // 두 휴일 간의 거리가 홀수인 경우
    else {
        return pf[abs(now - prev) / 2 - 1] * 2;
    }
}

// go : 현재 now번째 날이고 이전에 뽑은 휴일이 prev번째 날이며 가장 처음에 뽑은 휴일이 first일 때 
//      얻을 수 있는 생산성의 최대값을 리턴하는 함수
ll go(int now, int prev, int first) {
    // Base Case : n번째 정점까지 모두 뽑은 경우
    if (now == n) {
        // 휴일이 하나만 있는 경우라면 거리가 n이기 때문에 예외처리
        return prev != first ? calc(prev, first + n) : calc(0, n);
    }
    // Memoization
    if (dp[now][prev] != -1) {
        return dp[now][prev];
    }
    // 점화식
    dp[now][prev] = 0;
    dp[now][prev] = max(dp[now][prev],
                        max(go(now + 1, now, first) + calc(now, prev), go(now + 1, prev, first)));
    return dp[now][prev];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 입력부
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    pf[0] = arr[0];
    for (int i = 1; i < n; i++) {
        pf[i] = pf[i - 1] + arr[i];
    }
    memset(dp, -1, sizeof(dp));
    // 정답 계산 및 출력
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, go(i, i, i));
    }
    cout << ans;
}

 

후기 : 약 한달 정도의 휴식기를 갖고 앳코더를 쳐보았다. 생각보다는 감이 많이 떨어진거 같진 않다. 다만 C번의 경우 엄청 쉬운 문제인데 스스로 생각을 이상하게 해버려서 한번만에 맞췄지만 D번보다도 늦게 풀어버린게 아쉽다. 사실 쫄보라서 언레로 등록하고 쳤다.  e번의 경우는 종료 약 20분을 남겨두고 아이디어는 떠올렸으나 예외 케이스를 생각하지 못했고 구현 상 실수가 있어서 시간내에 풀지는 못했지만 업솔빙을 자력으로 하게 되어 기쁘다. 이번 대회는 원래 무조건 풀어야 하는 A~D를 풀긴했으나 아직도 속도가 너무 느려 충분히 1000등 이내에 들어올 수 있었음에도 그러지 못해서 그게 제일 아쉽다. 아니 항상 아쉽다..

 또 하나의 후기는 10개월 간의 우아한테크코스 4기를 끝내고 일생의 운을 모두 끌어다가 쓴거 같이 기적적으로 우아한형제들에 백엔드 신입 개발자로 입사하게 되었다는 것이다. 예전만큼 ps를 열심히 하지는 못하지만 일주일에 한번의 앳코더만은 놓치지 않으려 노력할 것이다. 일주일에 한번 앳코더를 응시하고 일주일동안 업무를 끝내고 시간이 남는 경우에만 한하여 업솔빙을 하는 방식으로 하려한다. 

 다행히도 가장 가고 싶었던 팀에 합격하게 되어 너무 좋았고 지금은 겨우 출근한지 한달도 안되어서 적응 중에 있지만 팀원분들께서 정말 진심으로 많이, 세심히 챙겨주셔서 너무 고마울 따름이다. 올해는 작년에 우테코때문에 달성하지 못한 앳코더 스카이블루찍기에 도전할 예정이다. 아니 우테코에서도 못한걸 입사하고 도전하는게 대가리가 어떻게 된거 아닌지? 

 생각해보면 경영학과였던 필자가 이렇게 될거라고는 전혀 생각지도 못했다. 걸어온 길이 항상 좋았던 것은 아니었지만, 누구보다 열심히 한것도 아니었지만, 솔직히 잘해내지도 못했지만, 포기하지 않고 스스로를 믿고 꾸준히 한 것이 두번째로 크게 작용했다고 생각한다. 첫번째로 크게 작용한건 정말 무조건 운이라고 생각한다. 그거말고는 설명할 길이 없다. 나는 정말 정규분포곡선 상의 평균선보다 좌측에 있는 사람이기 때문에 분명히 이 글을 보는 사람이라면 해낼 수 있다고 생각한다.

 모쪼록 이 블로그를 방문하는 너무나도 고마운 이들(나 포함)이 정말 잘되기를 바랍니다. 늦었지만 새해복 많이 받으세요. 원래 이런 남사스런 후기 남기지 않는데 다음부터는 드라이하고 짧게만 남기겠습니다