[백준] 25954 LCS 9 C++,번외 PyPy3

최적화와 포인터 활용을 통한 효율적인 DP 알고리즘 구현

C++의 강력한 최적화 기능과 효율적인 메모리 관리 기법을 활용한 DP 알고리즘을 소개합니다.

이 코드는 두 문자열을 입력받아 특정 계산을 수행하며, #pragma GCC optimize와 같은 최적화 기법과 포인터를 활용해 성능을 극대화한 예시입니다.

 

코드의 주요 특징

1. GCC 최적화 옵션:
   코드 상단에 #pragma GCC optimize("O3,unroll-loops")를 추가하여 컴파일러가 가능한 한 성능을 극대화하도록 설정합니다. unroll-loops는 반복문 언롤링을 통해 실행 속도를 높입니다.
2. 메모리 사용 최적화:
   short 타입을 사용하여 메모리를 절약합니다. 배열 크기는 최대 7000 x 7000이므로, int 대신 short(2바이트)를 선택하면 메모리 사용량을 절반으로 줄일 수 있습니다.
3. 포인터를 활용한 참조 속도 개선:
   반복문 내부에서 자주 접근하는 배열을 지역 포인터로 저장하여 인덱스 계산 오버헤드를 줄입니다.

코드 분석

1. 입력 및 초기화

string a, b;
cin >> a >> b;
int n = (int)a.size();
int m = (int)b.size();

// 초기화
for(int j = 0; j <= m; j++){
    ih[0][j] = j;
}
for(int i = 0; i <= n; i++){
    iv[i][0] = 0;
}

• a와 b는 입력 문자열입니다.
• ih[i][j]와 iv[i][j]는 DP 배열로, 각각 수평(horizontal)과 수직(vertical) 방향으로의 연산 결과를 저장합니다.
• ih[0][j]와 iv[i][0]는 문제의 초기 상태를 나타냅니다.

2. DP 배열 채우기

for(int i = 1; i <= n; i++){
    char ca = a[i-1];
    short* ih_i = ih[i];
    short* ih_im1 = ih[i-1];
    short* iv_i = iv[i];
    short* iv_i_1 = iv[i];
    short* iv_im1 = iv[i-1];

    for(int j = 1; j <= m; j++){
        if(ca == b[j-1]){
            ih_i[j] = iv_i[j-1];
            iv_i[j] = ih_im1[j];
        } else {
            short up = ih_im1[j];
            short left = iv_i[j-1];

            if(up > left){
                ih_i[j] = up;
                iv_i[j] = left;
            } else {
                ih_i[j] = left;
                iv_i[j] = up;
            }
        }
    }
}

• ih[i][j]와 iv[i][j]를 갱신하는 부분입니다.
• 최적화 포인트:
  • ca = a[i-1]로 반복문 내 문자열 접근을 최소화합니다.
  • 배열 참조에 포인터를 사용하여 성능을 높입니다.

3. 결과 계산

long long ans = 0;
for(int t = 1; t <= n; t++){
    short* ih_t = ih[t];
    for(int k = 1; k <= m; k++){
        short val = ih_t[k];
        if(val < k){
            ans += (long long)(m - k + 1) * (k - val);
        }
    }
}
cout << ans << "\n";

• 최종 결과는 ih 배열의 값들을 기반으로 계산됩니다.
• 특정 조건(val < k)을 만족하는 경우에만 연산을 수행하며, 이로 인해 효율적인 계산이 가능합니다.

주요 최적화 포인트

1. 배열 접근 최적화:
   • 반복문에서 배열에 자주 접근하는 경우, 포인터로 배열 참조를 저장하여 성능을 향상시켰습니다.
   • 예: short* ih_i = ih[i];
2. 메모리 절약:
   • short 자료형을 활용해 메모리 사용량을 줄였습니다.
3. GCC 최적화 활용:
   • #pragma GCC optimize("O3,unroll-loops")를 통해 컴파일러가 성능 향상 작업을 자동으로 처리합니다.

코드의 시간 복잡도

• DP 배열을 채우는 반복문과 결과를 계산하는 반복문이 각각 O(n * m)이므로, 전체 시간 복잡도는 **O(n * m)**입니다.

실행 예시

입력:

abcd  
bcde

5

전체코드

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// 최대 7000이므로 short(2바이트)로 충분
static const int MAXN = 7000;
static short ih[MAXN+1][MAXN+1];
static short iv[MAXN+1][MAXN+1];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string a, b;
    cin >> a >> b;
    int n = (int)a.size();
    int m = (int)b.size();

    // 초기화
    // ih[0][j] = j, iv[i][0] = 0
    for(int j = 0; j <= m; j++){
        ih[0][j] = j;
    }
    for(int i = 0; i <= n; i++){
        iv[i][0] = 0;
    }

    // DP 채우기
    // ih[i][j], iv[i][j] 갱신
    for(int i = 1; i <= n; i++){
        // a[i-1]을 미리 받아둔다 (미세 최적화)
        char ca = a[i-1];
        // 이 줄의 ih, iv 배열 참조를 지역 포인터로 받아 두면 인덱스 계산이 약간 줄어듦
        short* ih_i   = ih[i];
        short* ih_im1 = ih[i-1];
        short* iv_i   = iv[i];
        short* iv_i_1 = iv[i];
        short* iv_im1 = iv[i-1];

        for(int j = 1; j <= m; j++){
            if(ca == b[j-1]){
                // a[i-1] == b[j-1]
                // ih[i][j] = iv[i][j-1], iv[i][j] = ih[i-1][j]
                ih_i[j] = iv_i[j-1];
                iv_i[j] = ih_im1[j];
            } else {
                // ih[i][j] = max( ih[i-1][j], iv[i][j-1] )
                // iv[i][j] = min( ih[i-1][j], iv[i][j-1] )
                short up = ih_im1[j];
                short left = iv_i[j-1];

                if(up > left){
                    ih_i[j] = up;
                    iv_i[j] = left;
                } else {
                    ih_i[j] = left;
                    iv_i[j] = up;
                }
            }
        }
    }

    // 결과 계산
    // ans += (m - k + 1) * max(0, k - ih[t][k])
    // 여기서 ans가 최대 n*m*(m+1)/2 정도 될 수 있으므로 long long 사용
    long long ans = 0;
    for(int t = 1; t <= n; t++){
        // 한 번 더 포인터 최적화
        short* ih_t = ih[t];
        for(int k = 1; k <= m; k++){
            short val = ih_t[k];
            if(val < k){
                ans += (long long)(m - k + 1) * (k - val);
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

번외

import sys
from array import array

def solve():
    # 한 번에 입력 읽기 (조금 더 빠를 수 있음)
    data = sys.stdin.read().split()
    p = data[0]
    q = data[1]
    
    n, m = len(p), len(q)

    # 2D 배열 s, b를 1D로 펴서 저장: 각 크기는 (n+1)*(m+1)
    # short(2바이트)로 선언해 메모리를 절약 (0~65535 범위)
    s = array('H', [0]*((n+1)*(m+1)))
    b = array('H', [0]*((n+1)*(m+1)))

    # b[0][j] = j 초기화
    # => b[j] = j  (i=0 행)
    for j in range(m+1):
        b[j] = j

    r = 0  # 결과 누적

    # DP 채우면서 바로 r에 더해준다
    # 원래 코드:
    #  for i in range(1, n+1):
    #    for j in range(1, m+1):
    #      b[i][j] = s[i][j-1]
    #      s[i][j] = b[i-1][j]
    #      if p[i-1] != q[j-1]:
    #        b[i][j] = max(...)
    #        s[i][j] = min(...)
    #      r += (m-j+1)*max(0, j - b[i][j])
    #
    # 2D → 1D 변환: index(i,j) = i*(m+1) + j
    
    for i in range(1, n+1):
        # 행의 시작 오프셋
        row_i = i*(m+1)
        row_i_m1 = (i-1)*(m+1)
        
        pi_char = p[i-1]  # p[i-1] 미리 저장

        # 내부 루프
        # b[i][j] = s[i][j-1], s[i][j] = b[i-1][j] → 1D로는:
        # b[row_i + j] = s[row_i + (j-1)]
        # s[row_i + j] = b[row_i_m1 + j]
        for j in range(1, m+1):
            b_ij = s[row_i + (j-1)]        # 임시 저장 (b[i][j] 먼저 계산)
            s_ij = b[row_i_m1 + j]        # 임시 저장 (s[i][j])

            if pi_char != q[j-1]:
                # b[i][j] = max(b[i-1][j], s[i][j-1])
                # s[i][j] = min(b[i-1][j], s[i][j-1])
                up   = b[row_i_m1 + j]
                left = s[row_i + (j-1)]
                if up > left:
                    b_ij = up
                    s_ij = left
                else:
                    b_ij = left
                    s_ij = up

            # b, s에 실제 반영
            b[row_i + j] = b_ij
            s[row_i + j] = s_ij

            # r += (m-j+1) * max(0, j - b[i][j])
            diff = j - b_ij
            if diff > 0:
                r += (m - j + 1)*diff

    print(r)

if __name__ == "__main__":
    solve()

PyPy3 Code