경험을 통해 배운 디버깅 사례들을 정리합니다. 비슷한 실수를 반복하지 않기 위한 기록입니다.

위상 정렬: 인덱스 실수

원본 코드:

while (front < rear) {
    int cur = queue[front++];
    for (int idx = adj[cur]; idx; idx = nxt[idx]) {
        int nxtNode = to[idx];  // 정상
        indeg[nxtNode]--;
        if (indeg[nxtNode] == 0) {
            dist[nxtNode] = dist[cur] + 1;
            queue[rear++] = nxtNode;
        }
    }
}

오타:

int nxtNode = to[cur];  // idx 대신 cur 사용

인접 리스트 순회 시 현재 노드가 아닌 엣지 인덱스로 접근해야 합니다.

정적 배열 크기: 오차 하나의 폭

// 문제: 2×10^5 범위
struct Edge { int dest, nxt; } graph[200005];  // 누락된 0
// 올바른 선언
struct Edge { int dest, nxt; } graph[2000005];

최단 경로 개수: 자료형 선택

NOI2007 소셜 네트워크 문제에서 경로 개수가 10^10을 초과할 수 있어 long long 필수:

long long pathCnt[101][101];

비트마스킹: 연산자 우선순위

// 위험한 코드
if (j < width && (1 << j) & state == 0 && i > 0)

// 안전한 코드
if (j < width && (((1 << j) & state) == 0) && (i > 0))

비트 연산은 산술/비교 연산보다 우선순위가 낮습니다. 명시적 괄호 사용이 필수적입니다.

TSP 동적 계획법: 두 가지 전이 방식

상향식(Top-down) 접근:

for (int mask = 1; mask < pow3[n]; mask++) {
    for (int last = 0; last < n; last++) {
        if ((mask / pow3[last]) % 3 == 2) continue;
        for (int prev = 0; prev < n; prev++) {
            if (last == prev) continue;
            dp[last][mask + pow3[last]] = min(
                dp[last][mask + pow3[last]],
                dp[prev][mask] + cost[prev][last]
            );
        }
    }
}

하향식(Bottom-up) 접근:

for (int mask = 1; mask < pow3[n]; mask++) {
    for (int from = 0; from < n; from++) {
        for (int to = 0; to < n; to++) {
            if (from == to) continue;
            if (dp[from][mask] == INF) continue;
            if ((mask / pow3[from]) % 3 < 2) {
                dp[to][mask + pow3[to]] = min(
                    dp[to][mask + pow3[to]],
                    dp[from][mask] + cost[from][to]
                );
            }
        }
    }
}

순열 DP:边界的教訓

// 위험: 크기가 정확히 1 작음
long long memo[(1 << 16) - 1][16];

// 안전: 충분한 여유 공간
long long memo[(1 << 16) + 1][16];

또한 인덱스 순서 실수 주의:

// 오류
if (memo[j][mask]) continue;

// 정상
if (memo[mask][j]) continue;

세그먼트 트리: 게으른 전파

void apply(int node, int left, int right, int val) {
    tree[node] = (val == 0) ? (right - left + 1) : 0;
    lazy[node] = val;
}

void propagate(int node, int left, int right) {
    if (lazy[node] != -1) {
        int mid = (left + right) >> 1;
        apply(node << 1, left, mid, lazy[node]);
        apply(node << 1 | 1, mid + 1, right, lazy[node]);
        lazy[node] = -1;
    }
}

태그의 의미와 전파 시점을 명확히 구분해야 합니다.

이분 탐색: 경계값 처리

문제 조건: 0 ≤ M ≤ N ≤ 50000

// 위험
const int MAXN = 50000;

// 안전
const int MAXN = 50005;

세그먼트 트리 등에서는 4배 이상 할당이 표준입니다.