16강: 구간을 지배하는 자, 세그먼트 트리(Segment Tree)
AI 사용 안내: 이 포스팅은
Claude Opus 4.7언어 모델을 활용하여 작성되었습니다.
16강: 구간을 지배하는 자, 세그먼트 트리(Segment Tree)
안녕하세요! 여러분의 코딩 멘토, 재준봇입니다!
“1번부터 100만 번까지 데이터 중에서, 27번~84,213번 사이의 최댓값 좀 1초 안에 알려주세요. 아, 그리고 매초마다 데이터가 바뀌니까 매번 빠르게요.” — 이런 미친 요구를 받았다면, 여러분에게 필요한 건 단 하나, 세그먼트 트리입니다!
여러분, 안녕하세요. 오늘은 코딩 테스트의 고난도 자료구조 끝판왕 중 하나로 불리는 세그먼트 트리를 다뤄볼 거예요. 이름만 들으면 “어휴 어렵겠네…” 싶지만, 한 번 익혀두면 여러분 머릿속의 무기고에 핵폭탄 하나 들어가는 격이라고 보시면 됩니다. 진짜 신기한 게, 이거 모르고 코딩 테스트 보러 가면 특정 유형 문제에서 그냥 시간 초과로 통째로 날려먹는 사태가 벌어지거든요. 이거 모르면 큰일 납니다!
1. 도대체 왜 세그먼트 트리가 필요한가요?
자, 상황극을 한 번 해볼게요. 여러분이 게임 회사에 입사한 신입 개발자라고 칩시다. 운영팀에서 이렇게 요구해요.
“유저 100만 명의 점수가 배열로 저장돼 있어요. 자, 이제 우리는 두 가지 작업을 미친 듯이 자주 해야 해요. 첫째, 특정 등수 구간의 최고 점수를 조회하기. 둘째, 특정 유저의 점수를 갱신하기. 두 작업을 합쳐서 초당 10만 번씩 처리해야 해요. 부탁해요!”
여러분이 처음 떠올릴 방법은 두 가지일 겁니다.
방법 1: 그냥 배열로 처리 (Naive)
- 점수 갱신 →
O(1). (그냥 인덱스로 값만 바꾸면 끝) - 구간 최댓값 조회 →
O(N). (구간을 처음부터 끝까지 다 훑어야 함)
쿼리 M번 처리하면? 총 O(N × M) = 10^12. 슈퍼컴퓨터를 써도 답 안 나옵니다.
방법 2: 미리 구간별 최댓값을 모두 저장 (Prefix-style)
- 점수 갱신 →
O(N). (저장해둔 구간 최댓값들을 다 다시 계산해야 함) - 구간 최댓값 조회 →
O(1). (저장된 값만 읽으면 끝)
이것도 마찬가지로 갱신할 때 폭망이죠.
결론: 갱신과 조회 둘 중 하나만 빠르면 의미가 없어요. 둘 다 빨라야 합니다.
이 골치 아픈 모순을 해결하는 마법의 자료구조가 바로 세그먼트 트리입니다. 이 친구를 쓰면 갱신과 조회가 둘 다 O(log N)으로 끝납니다. 100만 개 데이터에서 log₂(1,000,000) ≈ 20번이면 끝난다는 소리죠. 미친 성능이죠?
2. 세그먼트 트리, 그래서 정체가 뭔데요?
한 줄 요약: “전체 구간을 절반씩 쪼개고, 각 쪼개진 구간의 정보(합, 최대, 최소 등)를 트리 노드에 미리 저장해두는 자료구조” 입니다.
말로 하면 헷갈리니까 바로 그림으로 봅시다. 배열 [3, 1, 4, 1, 5, 9, 2, 6] (8개)이 있다고 칩시다. 구간 합을 저장하는 세그먼트 트리는 이렇게 생겼어요.
[0~7] 합:31
/
[0~3] 합:9 [4~7] 합:22
/ \ /
[0~1] 4 [2~3] 5 [4~5] 14 [6~7] 8
/ \ / \ / \ /
[0]3 [1]1 [2]4 [3]1 [4]5 [5]9 [6]2 [7]6
핵심 아이디어를 보세요.
- 리프 노드(맨 아래)에는 원본 배열 값이 그대로 들어갑니다.
- 내부 노드는 자기 두 자식이 담당하는 구간의 합을 저장합니다.
- 그러니까 “0~7 구간의 합” 같은 큰 정보를, 트리를 한 번도 다 안 훑고 루트에서 바로 알 수 있어요.
그럼 임의의 구간(예: 2~6)은 어떻게 조회해요?
[2~3]노드에서 한 방에 5를 가져오고[4~5]노드에서 한 방에 14를 가져오고[6]리프에서 2를 가져오면 끝!- → 합: 5 + 14 + 2 = 21
8개짜리 배열인데, 우리는 단 3개의 노드만 봤습니다. N이 100만이라도 약 20개 노드만 보면 끝인다는 거죠. 이게 O(log N)의 위력입니다.
초보자 폭풍 질문! “근데 트리를 메모리에 어떻게 저장해요? 노드마다 자식 포인터 만들어야 하나요?”
답변: 아닙니다! 세그먼트 트리는 1차원 배열로 깔끔하게 표현하는 게 정석이에요. 트리의 루트를
tree[1]에 두면, 어떤 노드tree[k]의 왼쪽 자식은tree[2*k], 오른쪽 자식은tree[2*k+1]이 됩니다. 마법이죠? 그래서 배열 크기는 안전하게4*N으로 잡으면 됩니다.
3. 시간 복잡도 정리
| 연산 | 단순 배열 | 세그먼트 트리 |
|---|---|---|
| 트리 구축 | - | O(N) |
| 점 갱신 | O(1) | O(log N) |
| 구간 조회 | O(N) | O(log N) |
| M번 쿼리 처리 | O(N × M) | O((N + M) log N) |
100만 개 배열 + 10만 쿼리라면? 약 (1,000,000 + 100,000) × 20 ≈ 2,200만 번 연산. 1초 안에 가뿐히 끝납니다.
4. 자, 이제 진짜 문제 풀어봅시다!
라면 끓이기 챔피언십 실시간 점수 시스템
전 국민이 열광하는 ‘라면 끓이기 챔피언십’ 결승전이 시작됐습니다. N명의 참가자가 1번부터 N번 자리에 앉아 라면을 끓이고, 각자 매운맛 점수를 받습니다. 그런데 방송 중에 진행자가 자꾸 이런 질문을 던져요. “5번부터 18번 참가자 중 가장 매운 라면 점수는?” 동시에 참가자들은 라면을 다시 끓여 자기 점수를 갱신하기도 합니다.
입력 형식:
- 첫째 줄: N (참가자 수, 1 ≤ N ≤ 100,000), M (쿼리 수, 1 ≤ M ≤ 100,000)
- 둘째 줄: N개의 초기 매운맛 점수
- 다음 M줄: 쿼리가 둘 중 하나로 들어옵니다.
1 i v: i번 참가자의 점수를 v로 업데이트2 l r: l번부터 r번까지 중 최댓값 출력
예시 입력: 8 5 3 7 2 9 1 5 8 4 2 3 7 1 4 10 2 3 7 1 1 100 2 1 8
예시 출력: 9 10 100
실무주의보! 코딩 테스트에서 “여러 번 갱신과 구간 조회”가 보이면 99% 세그먼트 트리 또는 펜윅 트리(BIT) 문제예요. 혹시라도 “그냥 매번 for문으로 구간 순회하면 되지 않나?” 싶은 유혹이 들어도, 제약 조건의 N과 M을 곱해서 10^8을 넘으면 무조건 의심하세요. 그게 코딩 테스트 시간 초과를 피하는 첫 번째 방어선입니다.
잠깐! 합(sum)이 아니라 최댓값(max)이라구요?
네, 세그먼트 트리는 합산 말고도 최댓값, 최솟값, 곱, GCD 등 결합법칙이 성립하는 어떤 연산이든 다 처리할 수 있어요. 그러니까 위 예시 그림은 합 트리지만, 우리 문제에서는 각 노드에 자식 둘 중 큰 값을 저장하면 그게 곧 “구간 최댓값 트리”가 됩니다.
자, 이제 직접 풀어보시고 막히면 아래 정답을 펼쳐보세요.
해결 방안 및 정답 코드 보기 (클릭)
해결 방안 가이드 (알고리즘 설계)
이 문제는 점 갱신 + 구간 최댓값 쿼리 의 정석 패턴입니다. 세그먼트 트리를 다음 4단계로 설계합니다.
Step 1. 트리 배열 크기 정하기
- 입력 N에 대해 트리 배열 크기를
4 * N으로 잡습니다. - 이유: N이 2의 거듭제곱이 아니면 트리 높이가 살짝 더 길어져서, 안전하게 4N을 잡는 게 관례입니다.
Step 2. 트리 구축 (build)
- 재귀적으로 구간을 절반씩 쪼개면서, 리프에 도달하면 원본 값을 저장합니다.
- 내부 노드로 돌아올 때 두 자식 중 큰 값을 자기 값으로 저장합니다.
- 시간 복잡도: O(N) (총 노드 수가 약 2N개라서)
Step 3. 점 갱신 (update)
- 갱신할 인덱스가 현재 구간 안에 있을 때만 재귀를 타고 내려가서, 리프에 도달하면 값을 바꿉니다.
- 돌아올 때 부모 노드도 두 자식의 max로 갱신합니다.
- 시간 복잡도: O(log N) (트리 높이 만큼만 내려가니까)
Step 4. 구간 조회 (query)
세 가지 케이스로 구간을 다룹니다.
- 완전히 벗어남: 조회 구간이 현재 노드 구간과 겹치지 않음 → 무시 (max에서는 음의 무한대, 비음수만 다루면 0 반환)
- 완전히 포함됨: 현재 노드 구간이 조회 구간에 통째로 들어옴 → 트리 값 바로 반환 (이게 핵심! 이 덕분에 빠름!)
- 일부만 겹침: 양쪽 자식으로 재귀해서 두 결과 중 큰 값 반환
이 세 케이스 분기를 정확히 짜는 게 세그먼트 트리의 8할입니다.
파이썬 정답 코드 및 상세 해설
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def build(node, start, end):
"""[start, end] 구간을 담당하는 node를 빌드"""
if start == end:
# 리프 노드: 원본 배열 값을 그대로 저장
tree[node] = arr[start]
return
mid = (start + end) // 2
# 왼쪽 절반: 노드 번호 2*node, 구간 [start, mid]
build(node * 2, start, mid)
# 오른쪽 절반: 노드 번호 2*node+1, 구간 [mid+1, end]
build(node * 2 + 1, mid + 1, end)
# 부모 노드는 두 자식 중 큰 값을 가짐 (구간 최댓값 트리)
tree[node] = max(tree[node * 2], tree[node * 2 + 1])
def update(node, start, end, idx, val):
"""idx 위치의 값을 val로 갱신"""
# idx가 현재 구간 밖이면 패스 (가지치기)
if idx < start or idx > end:
return
if start == end:
# 리프에 도달하면 값 교체
tree[node] = val
return
mid = (start + end) // 2
# 양쪽 자식으로 내려가면서 갱신 시도
update(node * 2, start, mid, idx, val)
update(node * 2 + 1, mid + 1, end, idx, val)
# 돌아올 때 부모도 갱신
tree[node] = max(tree[node * 2], tree[node * 2 + 1])
def query(node, start, end, left, right):
"""[left, right] 구간의 최댓값을 반환"""
# 케이스 1: 완전히 벗어남 → 영향 없는 값(-1) 반환
# (점수가 0 이상이라고 가정. 음수도 가능하면 float('-inf') 사용)
if right < start or left > end:
return -1
# 케이스 2: 현재 구간이 조회 구간에 완전히 포함됨 → 트리 값 그대로 반환
if left <= start and end <= right:
return tree[node]
# 케이스 3: 일부만 겹침 → 양쪽 자식으로 재귀
mid = (start + end) // 2
left_max = query(node * 2, start, mid, left, right)
right_max = query(node * 2 + 1, mid + 1, end, left, right)
return max(left_max, right_max)
# ==== 메인 로직 ====
n, m = map(int, input().split())
arr = list(map(int, input().split()))
# 안전하게 4N 크기로 트리 배열 할당 (음수 점수까지 다루려면 -inf로 초기화)
tree = [0] * (4 * n)
# 트리 구축: 루트 노드는 1번, 전체 구간 [0, n-1]
build(1, 0, n - 1)
output = []
for _ in range(m):
parts = list(map(int, input().split()))
if parts[0] == 1:
# 갱신 쿼리: 1 i v (문제는 1-based이므로 i-1로 보정)
_, i, v = parts
update(1, 0, n - 1, i - 1, v)
else:
# 조회 쿼리: 2 l r (1-based → 0-based 보정)
_, l, r = parts
output.append(str(query(1, 0, n - 1, l - 1, r - 1)))
print('\n'.join(output))
코드 한 줄 한 줄 핵심 포인트:
node * 2,node * 2 + 1인덱싱: 트리를 1차원 배열로 표현하는 마법의 공식. 루트는 반드시 1번부터 시작해야 이 공식이 통합니다. (0번부터 시작하면 0 곱하기 2가 0이 되어버려서 망함.)tree = [0] * (4 * n): 안전한 4N 할당. 점수가 음수일 수 있다면float('-inf')로 초기화해야 함.- 조회 함수의 세 케이스 분기 순서: 1번(벗어남) → 2번(완전 포함) → 3번(일부 겹침) 순서가 깔끔합니다.
sys.setrecursionlimit(10**6): 파이썬 기본 재귀 제한(1,000)을 풀어줘야 N이 클 때 안 터집니다.input = sys.stdin.readline: 이거 안 쓰면 입력 받다가 시간 초과 나는 일 빈번해요. 코테 단골 함정.
한계점 및 실무 개선점
한계점 1. 재귀 깊이 문제 (파이썬 특화)
파이썬은 재귀가 느리고 스택 오버플로우 위험도 있어요. N이 10^7 이상이면 재귀 대신 반복문(iterative) 세그먼트 트리로 구현하거나, PyPy3 환경을 활용해야 합니다.
개선 방향: 반복형 세그먼트 트리는 트리 크기를 2N으로 잡고 인덱싱 트릭으로 위로 올라가며 갱신하는데, 코드가 더 짧고 빠릅니다. 다만 처음에는 직관적인 재귀형부터 익히는 걸 추천합니다.
한계점 2. 구간 갱신(Range Update)에 약함
지금 구현은 점 하나씩 갱신하는 구조입니다. 만약 “5번부터 100번까지 모두 점수에 +10 해주세요!” 같은 구간 갱신 요청이 오면, 단순히 100번을 반복해서 95 × log N이 걸려 비효율적이에요.
개선 방향: 레이지 프로파게이션(Lazy Propagation)이라는 기법을 추가하면 구간 갱신도 O(log N)에 가능합니다. 노드마다 “나중에 자식들에게 전달해야 할 변경 사항”을 게으르게 저장해두는 트릭이에요. 백준 10999번이 대표 문제입니다.
한계점 3. 동적 크기 문제
배열 크기가 미리 정해져 있어야 합니다. 실시간으로 데이터가 추가/삭제되는 환경(예: 이벤트 스트림)에서는 부적합합니다.
개선 방향: 동적 세그먼트 트리(Dynamic Segment Tree)나 세그먼트 트리 비트 압축(Segment Tree on coordinates)을 검토하세요. 좌표 범위가 10^9처럼 거대해도 실제 등장하는 좌표만 압축해 처리하는 좌표 압축(Coordinate Compression) 기법과 결합하면 강력합니다.
한계점 4. 메모리 사용량
4N짜리 배열이라 N=10^7이면 4천만 정수 = 약 320MB로, 채점 환경 메모리 제한(보통 256MB)을 넘길 수 있어요.
개선 방향: 반복형 세그먼트 트리는 정확히 2N 메모리만 쓰니, 메모리 제한이 빠듯하면 이쪽으로 갈아타세요. 또는 펜윅 트리(BIT, Binary Indexed Tree)가 합 쿼리만 필요한 경우 N + 1짜리 메모리만 쓰니 훨씬 가볍습니다. 단, 최댓값/최솟값은 BIT로 깔끔하게 안 됨.
한계점 5. 결합법칙 없는 연산
세그먼트 트리는 결합법칙이 성립하는 연산(합, 최대, 최소, GCD, XOR 등)에만 쓸 수 있어요. “구간의 중앙값” 같은 비결합 연산은 못 합니다.
개선 방향: 머지 소트 트리(Merge Sort Tree), 퍼시스턴트 세그먼트 트리(Persistent Segment Tree) 등 변형을 검토. 다만 대회용 고급 자료구조라 실무 환경에서는 거의 안 씀.
실무 환경 적용 시 주의점
실제 게임 리더보드, 광고 입찰 시스템 등에서는 세그먼트 트리를 직접 구현하기보다는 Redis Sorted Set(내부적으로 스킵 리스트 사용), DB의 인덱스(B-Tree), 또는 Apache Druid 같은 OLAP 엔진의 구간 집계 기능을 쓰는 게 일반적입니다. 다만 세그먼트 트리의 사고방식은 이런 시스템들의 내부 구조를 이해할 때 결정적으로 도움이 돼요. 알고리즘은 바로 못 써먹어도 알고 있는 것과 모르는 건 천지차이입니다.