2022 성균관대학교 프로그래밍 경진대회 검수와 상수 커팅 이야기

작성일 | In

서론

2022년 성균관대학교 프로그래밍 경진대회에 검수자로 참여했습니다.
이번 대회에는 저보다 훨씬 실력이 좋은 분들이 검수자로 함께 참여했습니다. 다른 검수자들이 저보다 훨씬 빠르고 정확하게 풀이 검증을 해주셨기 때문에 저는 상수 최적화를 통한 데이터 강화에 더 집중했습니다. 평소에는 대회 검수 후기를 잘 남기지 않는 편이지만, 이번 검수에서 시도한 상수 최적화 방법들이 인상적이라서 오랜만에 검수 후기를 작성해봅니다.
캐시 히트, 분기 예측, SIMD를 알고 있으면 글을 읽는데 도움이 될 수 있습니다.

BOJ 24529 이야기 배열 - 문제 설명

3개의 이야기 보따리에 각각 $N$개의 이야기가 있다. 이야기는 길이와 재미있는 정도를 갖고 있다.
$3N$의 이야기 중 $N$개의 이야기를 뽑아 나열해서 재미있는 정도의 합을 최대화해야 하는데, 이때 $i$번째로 오는 이야기의 길이는 $D_i$ 이하가 되어야 한다.
$D_i$가 단조 증가할 때($D_i \leq D_{i+1}$), 이야기의 재미있는 정도의 합의 최댓값을 구하자.

문제 풀이를 먼저 설명하겠습니다.
이야기 길이의 상한 조건을 만족하는 임의의 이야기 배열은, 같은 보따리에서 나온 이야기를 길이가 단조 증가하는 형태로 바꿀 수 있습니다. 그러므로 각 보따리에 있는 이야기를 길이 오름차순으로 정렬한 뒤 순서대로 뽑아도 됩니다. 이 아이디어를 이용하면 아래와 같은 점화식을 쉽게 떠올릴 수 있습니다.
$D[n][a][b][c][p] := $ 세 개의 보따리에서 각각 $a, b, c$ 번째 이야기까지 사용해서 $n$개의 이야기를 선택했고, 마지막으로 선택한 보따리가 $p$일 때 재미의 최댓값

이 점화식은 $O(N^4)$개의 상태가 있고, 각 상태의 답을 $O(1)$에 계산할 수 있기 때문에 $O(N^4)$에 문제를 해결할 수 있습니다. 이것이 출제자가 의도한 풀이지만, 열심히 최적화를 하면 $O(N^5)$로도 문제를 해결할 수 있습니다.

BOJ 24529 이야기 배열 - $O(N^5)$ 최적화

시작

가장 기본적인 코드는 다음과 같습니다. GetDP 함수를 $O(N^4)$번 호출하고, GetDP 함수는 상태 3개의 답을 $O(N)$에 계산하기 때문에 $O(N^5)$입니다. 이 코드의 실행 시간은 2400ms 입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

int N, L[64], D[64][64][64][64][3];
pair<int,int> A[64], B[64], C[64];

void GetDP(int i, int a, int b, int c){
    if(A[a].first <= L[i]){
        int &now = D[i][a][b][c][0];
        for(int j=0; j<a; j++){
            if(D[i-1][j][b][c][1] != -1) now = max(now, D[i-1][j][b][c][1] + A[a].second);
            if(D[i-1][j][b][c][2] != -1) now = max(now, D[i-1][j][b][c][2] + A[a].second);
        }
    }
    if(B[b].first <= L[i]){
        int &now = D[i][a][b][c][1];
        for(int j=0; j<b; j++){
            if(D[i-1][a][j][c][0] != -1) now = max(now, D[i-1][a][j][c][0] + B[b].second);
            if(D[i-1][a][j][c][2] != -1) now = max(now, D[i-1][a][j][c][2] + B[b].second);
        }
    }
    if(C[c].first <= L[i]){
        int &now = D[i][a][b][c][2];
        for(int j=0; j<c; j++){
            if(D[i-1][a][b][j][0] != -1) now = max(now, D[i-1][a][b][j][0] + C[c].second);
            if(D[i-1][a][b][j][1] != -1) now = max(now, D[i-1][a][b][j][1] + C[c].second);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i].second >> A[i].first;
    for(int i=1; i<=N; i++) cin >> B[i].second >> B[i].first;
    for(int i=1; i<=N; i++) cin >> C[i].second >> C[i].first;
    for(int i=1; i<=N; i++) cin >> L[i];

    sort(A+1, A+N+1);
    sort(B+1, B+N+1);
    sort(C+1, C+N+1);

    memset(D, -1, sizeof D);
    for(int i=0; i<3; i++) D[0][0][0][0][i] = 0;

    for(int i=1; i<=N; i++){
        for(int a=0; a<=N; a++) for(int b=0; b<=N; b++) for(int c=0; c<=N; c++)
            GetDP(i, a, b, c);
    }

    int mx = -1;
    for(int a=0; a<=N; a++) for(int b=0; b<=N; b++) for(int c=0; c<=N; c++){
        for(int d=0; d<3; d++) mx = max(mx, D[N][a][b][c][d]);
    }
    cout << mx;
}

캐시 히트

사용하는 메모리의 크기가 커질수록 캐시 미스가 더 많이 발생하기 때문에 DP 테이블의 크기를 줄여야 합니다. GetDP 함수에서 $D[i]$의 값을 계산할 때 $D[i-1]$만 사용하므로 토글링을 사용해서 DP 테이블의 크기를 $N\cdot N\cdot N\cdot N\cdot 3$에서 $2\cdot N\cdot N\cdot N\cdot 3$으로 줄일 수 있습니다.
GetDP 함수에서 모든 i와 i-1 뒤에 &1이 붙었으며, 47번째 줄에 memset(D[i&1], -1, sizeof(D) / 2);이 추가되었습니다. 이 코드의 실행 시간은 2100ms 이며, 이전 코드에 비해 300ms 정도 감소했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;

int N, L[64], D[2][64][64][64][3];
pair<int,int> A[64], B[64], C[64];

void GetDP(int i, int a, int b, int c){
    if(A[a].first <= L[i]){
        int &now = D[i&1][a][b][c][0];
        for(int j=0; j<a; j++){
            if(D[i-1&1][j][b][c][1] != -1) now = max(now, D[i-1&1][j][b][c][1] + A[a].second);
            if(D[i-1&1][j][b][c][2] != -1) now = max(now, D[i-1&1][j][b][c][2] + A[a].second);
        }
    }
    if(B[b].first <= L[i]){
        int &now = D[i&1][a][b][c][1];
        for(int j=0; j<b; j++){
            if(D[i-1&1][a][j][c][0] != -1) now = max(now, D[i-1&1][a][j][c][0] + B[b].second);
            if(D[i-1&1][a][j][c][2] != -1) now = max(now, D[i-1&1][a][j][c][2] + B[b].second);
        }
    }
    if(C[c].first <= L[i]){
        int &now = D[i&1][a][b][c][2];
        for(int j=0; j<c; j++){
            if(D[i-1&1][a][b][j][0] != -1) now = max(now, D[i-1&1][a][b][j][0] + C[c].second);
            if(D[i-1&1][a][b][j][1] != -1) now = max(now, D[i-1&1][a][b][j][1] + C[c].second);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i].second >> A[i].first;
    for(int i=1; i<=N; i++) cin >> B[i].second >> B[i].first;
    for(int i=1; i<=N; i++) cin >> C[i].second >> C[i].first;
    for(int i=1; i<=N; i++) cin >> L[i];

    sort(A+1, A+N+1);
    sort(B+1, B+N+1);
    sort(C+1, C+N+1);

    memset(D, -1, sizeof D);
    for(int i=0; i<3; i++) D[0][0][0][0][i] = 0;

    for(int i=1; i<=N; i++){
        memset(D[i&1], -1, sizeof(D) / 2);
        for(int a=0; a<=N; a++) for(int b=0; b<=N; b++) for(int c=0; c<=N; c++)
            GetDP(i, a, b, c);
    }

    int mx = -1;
    for(int a=0; a<=N; a++) for(int b=0; b<=N; b++) for(int c=0; c<=N; c++){
        for(int d=0; d<3; d++) mx = max(mx, D[N&1][a][b][c][d]);
    }
    cout << mx;
}

분기 예측

GetDP 함수의 각 for문마다 복잡한 if문이 2개씩 있습니다. -1과 비교하고, 다시 now와 비교해서 더 큰 값을 now에 대입하는 것은 매우 복잡합니다.
현대 CPU는 분기 예측이라는 기술을 사용합니다. 이는 조건문이 어떤 곳으로 분기할 것인지 미리 예측해서 계산하는 기술입니다. 하지만 예측에 실패하면 미리 계산한 결과를 폐기해야 하기 때문에 어느정도 손해를 보게 됩니다. BOJ 채점 서버에서 사용하는 Intel Haswell의 경우 분기 예측 실패시 15-20 클럭 정도를 낭비한다고 합니다.
PS는 최악의 경우를 고려해야 하기 때문에 분기 예측 실패가 발생할 여지를 줄여야 합니다. 조건문의 개수를 줄여봅시다.

아래 코드는 위에서 본 복잡한 조건문 대신 max 함수만 2개씩 사용합니다. 이 코드의 실행 시간은 900ms 이며, 초기 버전에 비해 1500ms 정도 감소했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void GetDP(int i, int a, int b, int c){
    if(A[a].first <= L[i]){
        int now = -1;
        for(int j=0; j<a; j++){
            now = max(now, D[i-1&1][j][b][c][1]);
            now = max(now, D[i-1&1][j][b][c][2]);
        }
        if(now != -1) D[i&1][a][b][c][0] = now + A[a].second;
    }
    if(B[b].first <= L[i]){
        int now = -1;
        for(int j=0; j<b; j++){
            now = max(now, D[i-1&1][a][j][c][0]);
            now = max(now, D[i-1&1][a][j][c][2]);
        }
        if(now != -1) D[i&1][a][b][c][1] = now + B[b].second;
    }
    if(C[c].first <= L[i]){
        int now = -1;
        for(int j=0; j<c; j++){
            now = max(now, D[i-1&1][a][b][j][0]);
            now = max(now, D[i-1&1][a][b][j][1]);
        }
        if(now != -1) D[i&1][a][b][c][2] = now + C[c].second;
    }
}

컴파일러 최적화

혹시 모르니 O3 최적화를 켜고 AVX2 명령어를 사용할 수 있도록 컴파일 옵션을 넣어봅시다.
-O3 옵션만 넣은 코드의 실행 시간은 여전히 900ms 정도지만, -mavx2 옵션까지 넣은 코드의 실행 시간은 600ms 정도입니다. 처음에 작성한 코드에 비해 4배 가까이 빨라졌습니다.

1
2
3
4
5
6
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;

// 이하 생략