seukseok의 개인 블로그

BOJ 풀이 노트: 덱 시뮬레이션과 누적 합 루틴 점검

· tech

오늘은 BOJ 5430과 11659를 묶어, 뒤집기 플래그 기반 덱 처리와 1차원 누적 합 쿼리 처리의 구현 포인트를 실수 방지 중심으로 정리했다.

오늘은 문자열 명령 처리 1문제 + 누적 합 1문제로 루틴을 구성했다.

하나는 시뮬레이션을 어떻게 효율적으로 바꾸는지, 다른 하나는 전처리로 질의 시간을 줄이는 전형 문제다.

1) BOJ 5430 - AC

문제 핵심 요약

배열과 명령 문자열이 주어질 때, R(뒤집기), D(첫 원소 삭제)를 순서대로 적용한 결과를 출력하는 문제다. 빈 배열에서 D를 수행하면 error를 출력해야 한다.

접근 아이디어(왜 이 방법인지)

핵심은 R이 나올 때마다 실제 배열을 뒤집으면 비효율적이라는 점이다. 명령 길이와 데이터 크기가 크기 때문에, 뒤집기는 불리언 플래그(reversed) 토글로 처리하고 D가 나올 때만 앞/뒤 중 어디를 pop할지 결정하는 방식이 안전하다.

컨테이너는 deque<int>를 사용하면 앞/뒤 삭제가 모두 O(1)이므로 명령 처리 흐름에 잘 맞는다.

시간/공간 복잡도

실수하기 쉬운 포인트

C++ 코드 설명(핵심 라인)

if (op == 'R') {
    reversed = !reversed;
}

실제 데이터 재배치 없이 방향 상태만 바꾼다.

if (!reversed) dq.pop_front();
else dq.pop_back();

삭제 연산은 현재 방향 상태에 따라 앞/뒤를 선택한다.

if (dq.empty()) {
    error = true;
    break;
}

예외 조건(error)을 명령 처리 중 즉시 확정한다.

다른 풀이 가능성

2) BOJ 11659 - 구간 합 구하기 4

문제 핵심 요약

수열이 주어지고, 여러 개의 구간 [i, j] 합을 빠르게 출력하는 문제다.

접근 아이디어(왜 이 방법인지)

질의마다 구간을 직접 더하면 O(N)이 걸려 전체가 커진다. 대신 1회 전처리로 누적 합 배열 prefix를 만들면 각 질의를 O(1)에 처리할 수 있다.

여러 질의를 빠르게 처리해야 하는 문제에서 가장 기본이 되는 패턴이다.

시간/공간 복잡도

실수하기 쉬운 포인트

C++ 코드 설명(핵심 라인)

prefix[i] = prefix[i - 1] + x;

전처리 단계에서 누적 합을 채우는 기본 식이다.

cout << prefix[j] - prefix[i - 1] << '\n';

각 질의를 상수 시간에 답하는 핵심 출력 라인이다.

다른 풀이 가능성

오늘 정리 포인트: