빠르고 편하게 코딩하는 팁

제가 PS를 할 때 사용하는 여러 코딩 팁을 소개하려고 합니다.

일반

0/1-based

zero-based와 one-based 중 무엇을 써야 하는지에 대한 질문을 종종 봐요. 저는 one-based로 일단 가다가, 몇 가지 사정이 생기면 zero-based로 바꾸는 편이에요.

• circular array, 환형 배열. 크기가 n인 배열이 있는데, 마지막 원소 다음이 첫 번째 원소인 것처럼 원형으로 취급하고 싶다고 합시다. zero-based에서 i번째 원소의 다음 원소는 (i+1)%n, 이전 원소는 (i+n-1)%n입니다. one-based에서 i번째 원소의 다음 원소는 (i%n)+1, 이전 원소는 (i+n-2)%n+1입니다. zero-based가 훨씬 깔끔해요. 나눗셈 연산은 삼항 연산자(ternary operator)로 쓰면 속도도 빨라질 수 있죠.
• vector 등 zero-based 자료구조와 오가야 할 때. 가끔 이런 걸 하긴 해요. one-based로 저장한 자료를 vector에 쓰고 처리하는데, 진짜 헷갈리고 비효율적이에요. 그냥 zero-based로 통일하는 게 훨씬 낫죠. lower_bound()같은 함수를 쓸 때에도 zero-based인 경우가 훨씬 예뻐요.

one-based를 쓰는 게 훨씬 나은 상황도 있어요.

• DP의 base case가 필요할 때. 냅색 알고리즘의 예를 들게요. 이 알고리즘은 물건을 하나씩 추가하면서 그에 맞게 배열을 가꾸며 작동해요. 그런데 i번째 물건을 추가하기 위해서 (i-1)번째의 상태를 참조하는 식으로 코딩한 경우, (i-1)이 음수이면 이를 인덱스로 쓰기 곤란하잖아요? 그래서 첫 번째 원소가 1이고, 아무 것도 없는 상태를 0으로 놓으면 깔끔하게 코딩할 수 있어요. 물론 base case가 예쁘게 산출되지 않는 경우에는 이러나 저러나 큰 차이가 없어요.
• 비어 있는 경우를 0으로 구분하고 싶을 때. 그러니까 nxt[i] == 0이면 값이 비어 있고, 1 <= nxt[i] && nxt[i] <= n이면 값이 차 있다는 식으로 취급하고 싶을 때 굉장히 유용해요. 전역 변수는 0으로 초기화되니까 비어 있는 경우를 처음에 고려할 필요가 없어요. 만약 zero-based를 쓴다면 nxt[i] == -1일 때를 비어 있는 걸로 취급하고, memset() 등으로 초기화해야겠죠.

목록 저장하기

이건 뭐라고 할까요, 제가 쓰는 원리? 방법론? 패턴? 일단 설명할게요.

값 여러 개를 순서대로 저장해야 할 경우가 있어요.

bool chk[maxn];
for (int i=1; i<=n; ++i) {
    if (chk[i]) { /* ... */ }
}

chk[i] == true인 i들을 모으고 싶다고 합시다. 물론 vector를 쓰는 방법이 있죠.

bool chk[maxn];
vector<int> lst;
for (int i=1; i<=n; ++i) {
    if (chk[i]) lst.push_back(i);
}

그런데 저는 vector 사용을 되도록 삼가는 편이에요. 시간이나 메모리 사용이 아쉬운 일이 가끔 있고, 또 아예 #include를 하지 않은 경우엔 이거 하나를 위해 #include하기도 아깝거든요.

그래서 저는 배열을 더 많이 써요.

bool chk[maxn];
int lst[maxn], lstn = 0;
for (int i=1; i<=n; ++i) {
    if (chk[i]) lst[lstn++] = i;
}

해당 목록을 저장할 배열 이름(lst) 뒤에 n을 붙인 이름의 변수(int lstn)로 원소 개수를 저장해요. 원소의 추가가 보시다시피 lst[lstn++] = i; 이렇게 깔끔하게 나와요. 사실 스택을 배열로 구현할 때 이런 모양이 나오는데, 그 때도 0/1-based 등 구현 디테일이 조금씩 다르잖아요. ++을 전항으로 할 지 후항으로 할 지도 그 선택에 따라 달라지는데, 저는 항상 이렇게 해요.

lstn은 원소의 개수, lst[lstn]은 새로 추가할 원소가 들어갈 위치, lst[lstn-1]은 마지막으로 넣은 원소의 위치지요.

lstn이 개수라서 초기값이 0이라 전역으로 잡아도 깔끔해요. 순회도 쉽게 가능하고요.

// Longest increasing subsequence
int a[maxn];
int lis[maxn], lisn;
for (int i=1; i<=n; ++i) {
    int j = upper_bound(lis, lis+lisn, a[i]) - lis;
    lis[j] = a[i];
    if (lisn < j) lisn = j;
}

// one-side convex hull
pair<int,int> hull[maxn]; int hn;
for (int i=1; i<=n; ++i) {
    while (hn>=2 && ccw(hull[hn-2], hull[hn-1], pt[i])) --hn;
    hull[hn++] = pt[i];
}

convex hull 예시에서는 hulln이 너무 기니까 hn으로 줄여서 썼어요. ans도 ansn 타이핑이 굉장히 헷갈리니까 an으로 쓰구요. 벡터는 자기가 크기를 가지고 있기 때문에 int(v.size()) 이렇게 가져 와야 하는데, 위의 방법처럼 배열로 쓰면 변수 하나로 해결되는 장점이 있어요.

앞에서 vector의 문제점을 몇 개 들었는데 저건 대부분 제가 그렇게 느끼는 것뿐이에요. 실제로 성능에 끼치는 영향은 보통 미미할 거거든요. 다만 이 배열 접근이 굉장히 잦다든가, 서너 개밖에 안 저장할 예정이라든가 하는 경우에는 성능 차이가 약간 날 수 있어요. 전역 변수는 컴파일 타임에 메모리 주소가 정해지기 때문에 동적으로 포인터를 잡아 사용하는 벡터보다 indirection이 하나 적게 들거든요. 로컬 변수도 레지스터 기준 상대 위치가 고정이니 값에 한 번에 접근할 수 있구요.

반복문 매크로

#define rep(i, n) for (int i=0; i<n; ++i)
#define rrep(i, n) for (int i=1; i<=n; ++i)

// 이항계수 (binomial coefficient)

const int mod = int(1e9)+7;
int comb[100][100];
comb[0][0] = 1;
rrep(i, 100) {
    comb[i][0] = comb[i][i] = 1;
    rrep(j, i-1) comb[i][j] = (comb[i-1][j-1]+comb[i-1][j])%mod;
}

// Floyd-Warshall 알고리즘

int dist[101][101];
int n;
rrep(j, n) rrep(i, n) rrep(k, n) {
    dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k]);
}

// 3-SUM, naïve
// 이번엔 zero-based로 써 볼까요?

int a[100];
int n;

rep(i, n) rep(j, i) rep(k, j) {
    if (a[k]+a[j]+a[i] == 0) printf("(%d, %d, %d)\n", k, j, i);
}

이거, 처음에는 싫어했거든요. 미관을 해치는 느낌? 정격 C++가 아닌 느낌으로요. 근데 써 보면 확실히 좋아요. 플로이드-와샬 알고리즘을 한 번 for문 매크로로 짜고 나면 그 쾌감을 잊을 수가 없어요! 엄청 편하고, 일정하게만 쓴다면 알아보기도 쉬워요. 반복문 매크로는 PS 바깥에서도 많이 쓰더라구요.

쓰신다면 0-based/1-based 매크로를 둘 다 추가해 두시는 게 편해요. 전자는 vector를 순회할 때 특히 유용하구요, 후자는 human-friendly한 인덱싱을 쓸 때 유용해요. 또 제가 쓰는 것과 다른 모양도 가끔 있더라구요.

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define FOR(i, n) for (int i=1; i<=n; ++i)
#define F0R(i, n) for (int i=0; i<n; ++i)
//       ^ 이거는 알파벳 o가 아니라 숫자 영이에요!

STL

std::pair 매크로

#define x first
#define y second

// 아래는 사용 예시입니다.
long long l2(pair<int,int> p) { return p.x*1ll*p.x + p.y*1ll*p.y; }

#define xy(a) a.x, a.y

// 아래는 사용 예시입니다.
pair<int,int> pt[1000];
int ia = 3, ib = 5;

// 이렇게 하면 어렵고 실수할 여지도 있습니다.
printf("line: (%d, %d) -> (%d, %d)\n", pt[ia].x, pt[ia].y, pt[ib].x, pt[ib].y);

// 이렇게 하면 알아보기 쉽고 편리합니다.
printf("line: (%d, %d) -> (%d, %d)\n", xy(pt[ia]), xy(pt[ib]));

저는 (x, y)로 쓰는 게 습관인데, 다른 분들은 아래처럼도 많이 쓰시더라구요.

#define fi first
#deifne se second

first와 second는 굉장히 길어요. 또 글자 수도 달라서 예쁘게 정렬되지도 않구요. pair 사용이 어느 정도 익숙해지셨다면 매크로를 쓰는 걸 추천드려요.

x나 y라는 이름의 변수를 잡더라도 자동으로 치환된다는 게 단점이에요. 즉 디버거에서 int x;의 변수를 찾고 싶다면 first라는 이름의 변수를 검색해야 하는 거지요. 또 애초에 first나 second라는 이름의 변수를 잡고 싶으신 분은 곤란할 수도 있어요. 저는 변수 이름을 짧게 짓는 습관이 있어서 그런 점에서 불편함은 많이 못 느꼈어요.

컨테이너 관련 매크로

#define pb push_back
#define eb emplace_back

vector<int> v;
vector<pair<int,int>> v2;

// 너무 길어요...
v.push_back(3);
v2.emplace_back(2, 5);

// 이렇게 하면 짧죠
v.pb(5);
v.pb(-4);
v2.eb(v[0]+1, v[1]+3);

#define all(v) (v).begin(), (v).end()

// 컨테이너 전체를 처리해야 할 때 굉장히 편리해요.
sort(all(v));
v.erase(unique(all(v)), v.end());

int i = lower_bound(all(v), 2) - v.begin();

// 물론 set에도 쓸 수 있구요.
set<int> s;
s.insert(3); s.insert(2); s.insert(5);
v.insert(v.end(), all(s));

#define sz(v) ((int)v.size())
for (int i=0; i<v.size(); ++i) {} // 컴파일러가 경고를 띄워요.
for (int i=0; i<sz(v); ++i) {}    // 이러면 괜찮구요.

for (int i=0; i<v.size()-10; ++i) {} // 이러면 underflow로 낭패를 볼 수 있는데,
for (int i=0; i<sz(v)-10; ++i) {}    // 이건 안전해요.

자료구조

Indexed tree

이걸 옛날에 설명한 다른 글도 블로그에 있는데, 그새 코딩 습관이 달라져서 새로 적어요.

const int M = 524288; // M은 원소의 최대 개수. 0부터 (M-1)번까지 있다고 생각합니다.
int tree[M<<1];
int range_sum(int l, int r) {
    int ret = 0;
    // 아래의 for문 선언이 핵심이에요.
    for (l+=M, r+=M; l <= r; l/=2, r/=2) {
         if (l%2 == 1) ret += tree[l++];
         if (r%2 == 0) ret += tree[r--];
     }
     return ret;
}

위와 같이 코드를 짜는 습관을 들이고 나니까 실수가 확실히 줄었어요. 옛날엔 아래처럼 짰던 것 같아요.

int range_sum(int l, int r) { // 옛날에 짜던 방식
    int ret = 0;
    l+=M; r+=M; /** (1) **/
    while (l<=r) {
         if (l%2) ret += tree[l++];
         if (r%2 == 0) ret += tree[r--];
         l/=2; r/=2; /** (2) **/
     }
     return ret;
}

1번과 2번으로 표시한 줄을 빠트리는 실수를 정말 많이 했어요. 처음 코드는 for문의 세 요소에 각각 중요한 내용을 채워 넣어야 하니 까먹을 일이 없죠. 또 l%2와 r%2 == 0의 글자 수가 달라서, 똑같은 코드인데도 정렬되지 않았구요. l%2와 l%2 == 1은 의미상으로는 다르지만 최적화를 걸고 컴파일하면 똑같아요.

Merge sort tree 초기화

const int M = 524288;
vector<int> ys[M<<1];

void add_point(int x, int y) { ys[x+M].push_back(y); }

void init() {
    for (int i=0; i<M; ++i) sort(all(ys[M+i]));
    for (int i=M-1; 1<=i; --i) {
        auto &v = ys[i], &vl = ys[i*2], &vr = ys[i*2+1];
        v.resize(vl.size()+vr.size());
        merge(all(vl), all(vr), v.begin()); // std::merge() in <algorithm>
    }
}

이렇게 하면 각 원소가 $\log (N)$단계만 올라가기 때문에 $O(N \log N)$ 시간에 완성이 돼요.