https://github.com/min-99/boj-step-coach
GitHub - min-99/boj-step-coach: 백준 온라인 저지(BOJ) 단계별 문제풀이를 **연간 클리어 목표**에 맞춰 체
백준 온라인 저지(BOJ) 단계별 문제풀이를 **연간 클리어 목표**에 맞춰 체계적으로 코칭하는 Claude Code 스킬입니다. - min-99/boj-step-coach
github.com
> "1629번 문제 풀거야"
// 파일 생성 로그 (생략)
문제를 읽어봤다면, 어떤 방식으로 풀 생각인지 대략적으로 말해주세요!
예시:
- "재귀로 반씩 나눠서 거듭제곱 구할 것 같아"
- "반복문으로 B번 곱하면 될 것 같아"
- "BigInt 써서 그냥 계산하면 되지 않을까?"
완전히 정확하지 않아도 괜찮아요. 떠오르는 대로 말해주세요!
모르겠으면 "모르겠어"라고 해도 됩니다.
> "그냥 문제에서 요구한대로 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 거야"
그 방법이면 A를 B번 반복해서 곱하는 거죠? B의 최댓값이 얼마인지 한번 확인해보세요.
B가 2,147,483,647 (약 21억)인데, 반복문을 21억 번 돌리면 시간 제한 0.5초 안에 가능할까요?
> "안될 것 같은데 오버플로우도 날것 같고, 그러면 어떻게 해?"
좋은 관찰이에요! 두 가지 문제를 잘 짚었어요:
1. 시간: O(B)는 21억 번 → 시간 초과
2. 오버플로우: A를 계속 곱하면 수가 엄청나게 커짐
힌트 하나 드릴게요.
▎ 💡 Lv.1: 이 문제는 분할정복 단계에 있는 문제예요. B번 곱하는 걸 반으로 나눠서 생각해보면 어떨까요?
▎
▎ 예를 들어, 10^11 을 구할 때 10을 11번 곱하는 대신... 10^11 = 10^5 × 10^5 × 10 이렇게 쪼갤 수 있지 않을까요?
▎
▎ 그러면 곱하는 횟수가 어떻게 줄어들까요?
(오버플로우 문제는, 곱셈할 때마다 매번 C로 나머지를 취하면 해결할 수 있어요. (a * b) % c == ((a % c) * (b % c)) % c 성질을 활용하면 됩니다.)
다시 한번 생각해보고 접근법을 말해주세요!
> "조금 더 힌트를 줘"
💡 Lv.2: 이 문제는 분할정복을 이용한 거듭제곱 (Exponentiation by Squaring) 알고리즘을 사용합니다.
▎
▎ 핵심 아이디어는 이거예요:
▎ - B가 짝수면: A^B = (A^(B/2))^2
▎ - B가 홀수면: A^B = A × A^(B-1)
▎
▎ 이렇게 하면 B가 매번 절반으로 줄어들기 때문에, 21억 번 곱하는 대신 약 31번만에 답을 구할 수 있어요. (log₂(2,147,483,647) ≈ 31)
이 아이디어로 재귀 함수를 한번 짜보세요!
> "모르겠어"
Lv.3: 의사코드 수준으로 설명해볼게요.
▎
▎ function power(A, B, C):
▎ 1) B가 1이면 → A % C를 반환 (기저 조건)
▎
▎ 2) half = power(A, B/2, C) → B를 절반으로 나눠서 재귀 호출
▎
▎ 3) B가 짝수면:
▎ → half * half % C 를 반환
▎ B가 홀수면:
▎ → half * half * A % C 를 반환
▎
▎ 흐름 예시 (10^11 mod 12):
▎ power(10, 11) → 홀수: power(10,5) * power(10,5) * 10
▎ power(10, 5) → 홀수: power(10,2) * power(10,2) * 10
▎ power(10, 2) → 짝수: power(10,1) * power(10,1)
▎ power(10, 1) → 10 % 12 = 10
주의할 점은 오버플로우예요. TypeScript의 number로 큰 수를 곱하면 정밀도를 잃을 수 있어서, BigInt를 사용하거나 중간 계산에서 항상 % C를 해줘야 해요.
이걸 참고해서 1629.ts에 코드를 작성해보세요!
> "모르겠어!!"
💡 Lv.4: 핵심 코드 부분만 보여드릴게요.
▎
▎ const power = (a: bigint, b: bigint, c: bigint): bigint => {
▎ if (b === 1n) return a % c
▎
▎ const half = power(a, b / 2n, c)
▎
▎ if (b % 2n === 0n) return (half * half) % c
▎ else return (half * half % c * a) % c
▎ }
이 power 함수를 1629.ts에 넣고, 입력받은 A, B, C를 BigInt로 변환해서 호출하면 됩니다. console.log로 결과를 출력하는 부분을 작성해보세요!
> "답 알려줘"
Lv.4에서 핵심 함수는 이미 다 드렸어요! 남은 건 입출력 부분뿐이에요.
1629.ts에 이미 이 부분이 있잖아요:
const [A, B, C] = input
여기서 power 함수를 호출하고 결과를 console.log로 출력하면 끝입니다. 한번 시도해보세요!
> "코드 작성했어. 확인해줘"
예제 1 통과! 나머지 케이스도 확인해볼게요.
모든 케이스 통과!
📝 코드 리뷰 - BOJ #1629
⏱️ 복잡도 분석
- 시간복잡도: O(log B) — B를 매번 절반으로 나누므로
- 공간복잡도: O(log B) — 재귀 호출 스택
- 제한 시간 내 통과: ✅ 충분 (log₂(2,147,483,647) ≈ 31번 연산)
✅ 잘한 점
- BigInt를 사용해서 오버플로우 문제를 올바르게 해결
- 분할정복 재귀 구조가 깔끔
💻 코드 개선 조언
23번 라인의 홀수 처리에서 연산자 우선순위에 주의하세요:
// 현재 코드
return (half * half % c * a) % c
// 더 명확한 버전
return (half * half % c * a % c)
현재 코드도 BigInt에서는 왼쪽→오른쪽으로 계산되어 결과적으로 맞지만, 괄호를 명시적으로 써주면 의도가 더 명확해집니다:
return ((half * half) % c * a) % c
🎓 배운 점 정리
- 핵심: 거듭제곱을 O(log N)에 계산하는 분할정복 기법 (Exponentiation by Squaring)
- 관련 유형: 11401번 (이항 계수 3), 1031번 (거듭제곱) 등 모듈러 연산이 필요한 문제에서 자주 활용됩니다
백준에 제출해보세요!
> "나 문제 다시 풀었어. 다시 검사해줘" (틀린 케이스 테스트)
테스트 실패가 있어요.
┌────────┬─────────────────┬──────────┬────────┐
│ 테스트 │ 입력 │ 기대 │ 결과 │
├────────┼─────────────────┼──────────┼────────┤
│ 예제 1 │ 10 11 12 │ 4 │ 4 ✅ │
├────────┼─────────────────┼──────────┼────────┤
│ B=1 │ 5 1 3 │ 2 │ 2 ✅ │
├────────┼─────────────────┼──────────┼────────┤
│ 큰 수 │ 2 30 1000000007 │ 73741817 │ 256 ❌ │
└────────┴─────────────────┴──────────┴────────┘
🔍 반례 분석
반례 1
- 입력: 2 30 1000000007
- 기대 출력: 73741817
- 실제 출력: 256
💡 코드에서 변경한 부분을 다시 한번 살펴보세요. b를 나누는 값이 이전과 달라졌는데, 그게 올바른지 확인해보세요!