BOJ 풀이 노트: 스택 신호 처리와 분할 정복 거듭제곱

2026. 2. 23. · tech

BOJ 2493, 1629 두 문제를 실전 구현 관점에서 정리한 풀이 노트.

오늘은 자료구조 1문제 + 분할 정복 1문제로 구성했다.

• BOJ 2493 - 탑
• BOJ 1629 - 곱셈

둘 다 정석 풀이를 정확히 구현하면 빠르게 통과되는 유형이라, 핵심 원리와 실수 포인트를 짧게 고정해두는 게 좋다.

1) BOJ 2493 - 탑

문제 핵심 요약

왼쪽에서 오른쪽으로 탑이 주어질 때, 각 탑이 쏜 신호를 처음으로 수신하는 왼쪽 탑의 번호를 구하는 문제다. 현재 탑보다 낮은 왼쪽 탑은 수신 후보가 될 수 없다는 점이 핵심이다.

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

브루트포스로 각 탑마다 왼쪽을 끝까지 탐색하면 최악 O(N^2)라 비효율적이다. 이 문제는 **단조 스택(높이가 내림차순이 되도록 유지)**으로 O(N)에 처리할 수 있다.

현재 탑 h[i]를 볼 때:

1. 스택 top의 높이가 h[i]보다 작으면 수신 불가이므로 pop
2. pop이 끝난 뒤 top이 남아 있으면 그 인덱스가 정답
3. 현재 탑 (i, h[i])를 push

각 탑은 최대 1번 push, 1번 pop만 되므로 전체가 선형 시간으로 끝난다.

시간/공간 복잡도

• 시간: O(N)
• 공간: O(N)

실수하기 쉬운 포인트

• 비교 연산을 <=로 잘못 쓰면 같은 높이 처리에서 오답이 날 수 있다. 이 문제는 자기보다 높거나 같은 탑이 수신하므로, pop 조건은 top.height < current가 맞다.
• 출력 인덱스가 1-based라는 점을 놓치기 쉽다.
• 스택이 비었을 때는 0을 출력해야 한다.

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

while (!st.empty() && st.top().second < h[i]) st.pop();

현재 탑보다 낮은 후보를 제거하는 핵심 루프다.

if (st.empty()) ans[i] = 0;
else ans[i] = st.top().first;

pop 이후 남은 top이 가장 가까운 왼쪽 수신 탑이 된다.

다른 풀이 가능성

세그먼트 트리/펜윅 트리 기반으로도 접근은 가능하지만, 이 문제는 단조 스택이 구현량과 성능 모두에서 가장 깔끔하다.

2) BOJ 1629 - 곱셈

문제 핵심 요약

A^B mod C를 계산하는 문제다. B가 크기 때문에 단순 반복 곱셈은 불가능하고, 빠른 거듭제곱이 필요하다.

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

핵심은 지수를 절반씩 줄이는 **분할 정복(이진 거듭제곱)**이다.

• B가 짝수면: A^B = (A^(B/2))^2
• B가 홀수면: A^B = (A^(B/2))^2 * A

매 단계마다 모듈러 연산을 적용하면 값이 커지는 것을 막을 수 있다. 재귀 깊이는 log2(B) 수준이라 매우 빠르다.

시간/공간 복잡도

• 시간: O(log B)
• 공간: O(log B) (재귀 스택)

실수하기 쉬운 포인트

• 기저 조건(B == 0) 처리를 빼먹으면 재귀가 끝나지 않는다.
• 중간 계산에서 모듈러를 늦게 적용하면 오버플로 리스크가 커진다.
• 홀수 지수 처리에서 마지막 * A를 누락하면 오답이 난다.

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

long long half = modPow(a, b / 2, c);
long long result = (half * half) % c;
if (b % 2 == 1) result = (result * (a % c)) % c;

분할 정복 점화식을 그대로 구현한 부분이다. 짝수/홀수 분기를 최소한으로 유지해서 디버깅이 쉽다.

if (b == 0) return 1 % c;

재귀 종료 조건. 모듈러 형태로 바로 반환해 일관성을 맞춘다.

다른 풀이 가능성

재귀 대신 반복문 기반 이진 거듭제곱으로도 구현 가능하다. 실무/대회에서 스택 깊이를 신경 쓰고 싶다면 반복문 버전이 더 선호되기도 한다.

오늘 정리 포인트:

• 2493은 단조 스택으로 후보를 즉시 제거하는 구조를 떠올리면 빠르게 해결된다.
• 1629는 지수 절반 분할 + 매 단계 모듈러만 정확히 지키면 안정적으로 통과된다.

짧은 정석 문제라도 이렇게 기록해두면 다음에 유사 문제를 만났을 때 구현 속도가 확실히 빨라진다.