2024 한양대학교 ERICA X 코드트리 전국 SW 프로그래밍 경진대회

지난번 구름edu에서 진행된 대회 이후에 또 다른 대회에 참여하였습니다.

지난 대회는 한동대 / 우송대 / 한밭대 이렇게 세 대학교끼리 주최하여 진행한 것 같은데,

이번 대회는 전국 대학교에서 참여하였습니다.

 

대회 진행

1. 마스코트 선별 시험 [실버 2]

배열에서 K개의 element를 골랐을 때 element 간의 차이 중에서 최소 차이를 묻는 문제였습니다.

정렬해서 a[i]와 a[i+K-1]의 차이를 구하여 그 중 최솟값을 구하면 되는 문제였습니다.

정렬 + 그리디 유형으로 백준에서도 실버 2 정도 받았을 것 같네요.

시간복잡도 : O(NlogN)

 

2. 개구리 점프 [골드 2]

https://www.acmicpc.net/problem/1937 이 문제가 생각나는 문제였습니다.

(1,1), (1,2) ,... (N,M-1), (N,M) 순서대로 DP 테이블을 갱신하는 데, 각 테이블 값은 해당 좌표까지 가는 데에 최대 시간을 저장할 겁니다. (최단거리면 다익스트라로 풀 수 있어요.)

 

그러나 도중에 스킬을 사용하는 경우도 있는데, 이를 위해서 또 (N,M)에서 (i,j)까지의 최대 거리를 계산을 해주어야 합니다.

그리고 (i,j) 이하의 좌표들 중에서 (N,M)까지의 최대 거리를 바로 구할 수 있도록 또 업데이트를 해주어야죠.

 

이후에는 각 칸에 대해서 DP 테이블 값과 해당 칸에서 스킬을 사용했을 때의 최대 거리를 더하면 됩니다.

백준에서는 골드 2~1 사이가 적당할 것 같은 문제였어요.

시간복잡도 : O(NM(N+M))

 

3. 최댓값 갱신 함수의 반환값 [플레티넘 4]

 

함수는 대강 다음과 같습니다.

# Python style pseudo-code

def func(a,b,c):
    cnt = 0
    maxx = 0
    for i in range(a, b+1):
        if(A[i] > maxx) :
            maxx = A[i]
            cnt += 1
    if(cnt == c) : return maxx
    return -1

 

그런데 잘 생각해보면, index값 i에서 다음으로 갱신될 index j는 항상 정해져 있습니다.

그리고 index j에서 다음으로 갱신될 index도 마찬가지 일 것이고요.

 

이를 트리 구조처럼 생각을 해봅시다. 즉, p[i] = j 라면 A[i] 이후에 갱신될 다음 값은 A[j]이다 이렇게 표현해보죠.

그러면 c번 갱신한 결과 == p[i]에서 c-1번째 위의 parent의 값이 됩니다.

이는 또 Sparse table을 활용한다면 O(logN) 만에 구할 수가 있죠.

 

트리 구조는 priority queue나 set으로 O(NlogN)만에 구현할 수 있습니다.

(전에 매칭이 안 된 index들을 pop하면서 parent 배열을 채워주면 되므로)

그리고 sparse table을 세우는 데도 O(NlogN), 이후 각 쿼리별로 대답해주는 건 O(QlogN)만에 가능합니다.

 

Time complexity : O((N+Q)logN)

 

4. 제 점수는요 [플레티넘 2]

쿼리 두 가지를 처리해야 하는 문제였습니다.

 

<쿼리>

1. update(idx, val) : idx 위치의 값을 val로 바꾼다.

2. query(idx) : [idx-R, idx+R] 사이의 값들 중 idx위치의 값과 동일한 값의 개수를 구한다.

 

2번 쿼리만 있다면 Mo's나 Merge sort tree로 풀 수 있었는데, 1번 쿼리가 들어옴에 생각을 좀 바꿨어야 했습니다.

Merge sort tree에 PBDS를 같이 박는 생각도 해보아 직접 구현했는데, 시간초과과 났고

 

결국 Memory 문제는 있을 수도 있겠지만, PBDS가 다이나믹으로 할당해주는 세그일 것이라 믿고 PBDS를 100'000개를 만들어 이를 해결하였습니다.

정해는 Sqrt-decomposition이었다고 하네요.

Time complexity : 제 풀이는 O((N+Q)logN) 

 

결과 및 후기

결과는 아직 안 나왔는데, 너무 잘하는 사람들이 많아 상은 하나도 못 탈 예감은 듭니다.

다만, 문제들의 난이도가 상당했고 티어 분류도 백준이랑 유사해서 매우 놀랐습니다.

매우 재밌고 도전되는 문제들이었습니다.