구간 최댓값 세그먼트 트리
2357번: 최솟값과 최댓값문제 상황길이 $N$인 배열이 주어졌을 때, 구간 $[l, r]$의 최댓값을 빠르게 구해야 한다.방법전처리쿼리브루트포스$O(1)$$O(N)$세그먼트 트리$O(N)$$O(\log N)$핵심 아이디어배열을 이진 트리 형태로 분할하여, 각 노드가 해당 구간의 최댓값을 저장한다. 쿼리 시 필요한 구간만 방문하므로 $O(\log N)$에 처리된다.예) 배열 [2, 5, 1, 4, 9, 3] 9 [0,5] / \ 5 [0,2] 9 [3,5] / \ / \ 5[0,1] 1[2,2] 9[3,4] 3[5,5] / \ / \ 2[0] 5[1] 4[3] 9[4]구현1..
2026. 1. 23.
백준 32162번: n, 3n, 5n
문제 요약서로 다른 양의 정수로 구성된 증가 수열 중, 다음 조건을 만족하는 사전순으로 최소인 수열을 찾는 문제입니다:임의의 양의 정수 n에 대해, n, 3n, 5n 중 정확히 하나만 수열에 등장한다.입력: 테스트 케이스 T개, 각각 인덱스 i (1 ≤ i ≤ 100,000)출력: 각 i번째 수열 원소 ai"사전순 최소"란?두 수열을 앞에서부터 비교할 때, 처음으로 다른 위치에서 더 작은 값을 가진 수열이 사전순으로 앞섭니다.수열 A: [1, 2, 4, ...]수열 B: [1, 2, 5, ...]→ 3번째 위치에서 4 즉, 가능한 한 작은 수부터 그리디하게 선택하되, 조건을 만족해야 합니다.수열 생성 예시1부터 차례로 확인하며 선택 가능 여부를 판단:1 선택 → n=1일 때 {1, 3, 5} 중 1 선택..
2025. 10. 11.
Python `pow()` 3항 형태와 모듈러 거듭제곱 최적화
모듈러 거듭제곱이란?기본 개념모듈러 거듭제곱은 큰 지수 계산 결과를 특정 수로 나눈 나머지를 구하는 연산입니다.(a^b) mod m예를 들어, 2^10 mod 1000을 계산하려면:일반적 방법: 2^10 = 1024 → 1024 % 1000 = 24Python: pow(2, 10, 1000) → 24왜 필요한가?큰 지수를 계산할 때 문제가 발생합니다:# ❌ 이렇게 하면 안 됩니다result = (2 ** 1000000) % 1000000007 # 메모리 폭발!# ✅ 올바른 방법result = pow(2, 1000000, 1000000007) # 빠르고 안전pow(a, b, m)의 동작 원리정의pow(a, b, m) # (a^b) mod m을 반환제약 조건:a, b, m은 모두 정수m ≠ 0b 일 때..
2025. 10. 3.
