블로그

정적 세그먼트 트리

이 포스트에서는 세그먼트 트리에 대해 알아보려고 한다.

세그먼트 트리는 배열의 특정 구간에 대한 연산(구간 합, 최솟값, 최댓값 등)과 특정 원소의 값에 대한 갱신이 빈번하게 일어날 때 사용하는 이진 트리 기반 자료구조이다. 여기서는 자바 코드를 활용할 것이니, 자바에 익숙하지 않은 사람은 다른 블로그를 들리길 바란다.

일반적인 1차원 배열을 생각해 보자. 만약 이게 처음 만들어지고 업데이트가 이루어지지 않는 방식이고 특정 구간의 합만 질의하는 방식이라면, 1차원 누적합을 자체적으로 O(N)을 활용해 만들어 평생 활용(인덱스 3부터 60까지의 누적합을 구하라는 질의가 들어오는 경우 (60 인덱스 위치의 누적합) - (2 인덱스 위치의 누적합)을 통해 O(1)로 바로 해결 가능)하는 것이 효율적일 것이다.

그러나, 배열의 요소에 대해서 수정이 자주 일어난다면 어떻게 될까?

가령, 길이 N = 10,000인 배열이 있고, 그 요소들에 대해서 무작위로 십만 번의 수정이 일어난다면? 그때그때 새로 누적합 배열을 만들어 줘야 하기 때문에 100,000 * 10,000 = 1,000,000,000번, 즉 10억 번의 연산이 업데이트 하는 데에만 활용이 될 것이다. 그렇다면 기존 방식으로는 이런 경우에 대응하기가 곤란해진다. 이럴 때 쓰라고 있는 자료구조가 바로 세그먼트 트리이다.

구간합 세그먼트 트리 이미지 예시.

구간합 세그먼트 트리를 예로 들면 위의 그림과 같다. 원본 배열 arr이 따로 있을 때, 트리 배열 tree를 생성하여 각 노드마다 arr 배열의 start 인덱스부터 end 인덱스까지 범위를 담당하여 해당 구역의 누적합을 저장한다. 리프 노드는 해당 arr 배열의 값만 저장하고 있으며, 부모 노드는 담당하고 있는 리프 노드들의 값의 합을 저장한다.

세그먼트 트리에서는 크게 세가지의 메소드가 기본적으로 필요하다.

첫 번째로, 기존 배열 arr을 바탕으로 초기 세그먼트 트리 tree를 구축하는 함수 build().

두 번째로, tree를 구축한 상태에서 arr의 특정 index의 값을 value로 업데이트 하고자 할 때, tree를 그에 따라 수정해주는 update() 함수.

마지막으로, 현재 tree 상에서 특정 구간(left부터 right)의 누적합을 반환하는 query() 함수.

build()

Build의 실제 실행 순서

arr이 {2, 1, 5, 3}인 배열일 때, build(1, 0, 3)를 호출할 시 값이 저장되는 순서는 다음과 같다.

원리를 알았다면 이제 코드로 구현해보자. 각 함수의 세부 내용을 구현하기 전, 먼저 기본 구조를 만들어본다.

public class SegmentTree {
  
    static int[] arr = {2, 1, 5, 3};
    static long[] tree = new long[arr.length * 4];
    static void build(int node, int start, int end) {
        // TODO
    }
    static void update(int node, int start, int end, int index, int value) {
        // TODO
    }
    static long query(int node, int start, int end, int left, int right) {
        // TODO
        return 0;
    }
}

여기에서 arr은 세그먼트 트리가 아니며, 기본적으로 주어지는 1차원 배열이다.

세그먼트 트리인 tree가 이 arr을 기반으로 누적합 자료구조를 관리하기 위해 따로 생성된다. tree 배열의 길이는 일반적으로 arr 길이의 4배로 설정하면 충분하다.

build() 함수는 다음과 같다.

static void build(int node, int start, int end) {
    // 1. 리프 노드에 도착한 경우
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    // 2. 리프 노드가 아닌 경우
    // 2 - 1. 구간의 중간 지점 구하기
    int mid = start + (end - start) / 2;
    // 2 - 2. 왼쪽과 오른쪽 자식 구축
    build(node * 2, start, mid);
    build(node * 2 + 1, mid + 1, end);
    // 2 - 3. 자식의 결과를 합쳐 부모 노드 계산
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

기본적으로 트리를 배열로 구현해 본 사람이라면, 자식 노드로 접근할 때 왼쪽 자식은 node * 2, 오른쪽 자식은 node * 2 + 1로 접근하면 된다는 것을 알 것이다.

세그먼트 트리에서 해당 노드가 책임지는 범위가 한 칸(start와 end가 동일)일 경우엔 해당 노드는 리프 노드가 되며, arr 배열의 해당 인덱스 값을 세그먼트 트리의 리프노드에 그대로 가져간다.

리프 노드가 아닐 경우에는 구간을 더 쪼개서 자식 노드들에 접근하여 같은 과정을 반복한다. 자식 노드들의 작업이 끝난 이후에는 해당 노드의 값을 자식 노드 값들의 합으로 지정한다.

update()

다음으로 update()의 코드를 알아보자. 업데이트를 하는 이 함수는 arr 배열에서 특정 인덱스 값의 변경이 일어날 때 세그먼트 트리 또한 같이 수정한다. 코드는 다음과 같다.

static void update(int node, int start, int end, int index, int value) {
    
    // 1. 현재 구간이 index를 포함하지 않으면
    if (index < start || index > end) {
        return;
    }
    // 2. 리프 노드에 도착한 경우
    if (start == end) {
        // tree와 arr 변경
        tree[node] = arr[start] = value;
        return;
    }
    // 3. 리프 노드가 아닌 경우
    // 3 - 1. 구간의 중간 지점 구하기
    int mid = start + (end - start) / 2;
    // 3 - 2. 왼쪽 또는 오른쪽 자식으로 이동
    if (index <= mid) {
        update(node * 2, start, mid, index, value);
    } else {
        update(node * 2 + 1, mid + 1, end, index, value);
    }
    // 3 - 3. 부모 노드의 합 다시 계산
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

업데이트를 하는 경우엔 build()와 달리 모든 자식 노드에 방문할 필요가 없다. 따라서 if문으로 내가 업데이트 하려는 index가 속한 자식으로만 내려가면 된다.

그 이외엔 우리가 타깃하는 index의 범위에 대해 예외처리를 하는 것 말고는 build()와 크게 다르지 않다.

query()

마지막으로 query() 함수에 대해 알아보자. 이 함수는 원본 배열에서 특정 구간의 합을 묻는 함수이며, 우리가 지금껏 만든 세그먼트 트리를 활용한다.

static long query(int node, int start, int end, int left, int right) {
    // 1. 현재 구간과 조회 구간이 전혀 겹치지 않으면
    if (left > end || right < start) {
        return 0;
    }
    // 2. 현재 구간이 조회 구간에 완전히 포함되면
    if (left <= start && right >= end) {
        return tree[node];
    }
    // 3. 일부만 겹치면 두 자식의 결과를 합산
    int mid = start + (end - start) / 2;
    return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right);
}

이건 앞의 두 함수들과 좀 다르다. 이 함수는 크게 세가지를 고려하면 된다.

먼저 우리가 조회하려는 구간의 맨 왼쪽을 left, 맨 오른쪽을 right라고 해보자. 이때 조회를 하기 위해 노드를 내려가면서 어떤 노드 입장에선 본인이 담당하는 start부터 end까지의 구역이

1. left부터 right까지의 구역과 전혀 겹치지 않을 경우
2. left부터 right까지의 구역과 일부만 겹칠 경우
3. left부터 right까지의 구역에 포함될 경우

가 있을 것이다.

그 세가지를 잘 고려해 주면, query()를 해결할 수 있다.

전체 코드는 아래와 같다. 테스트 코드까지 포함했으니 복사해서 실행해보면 되겠다.

public class SegmentTree {
    static int[] arr = {2, 1, 5, 3};
    static long[] tree = new long[arr.length * 4];
    static void build(int node, int start, int end) {
        // 1. 리프 노드에 도착했다면?
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        // 2. 구간의 중간 지점 구하기
        int mid = start + (end - start) / 2;
        // 3. 왼쪽과 오른쪽 자식 구축
        build(node * 2, start, mid);
        build(node * 2 + 1, mid + 1, end);
        // 4. 자식의 결과를 합쳐 부모 노드 계산
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    static void update(int node, int start, int end, int index, int value) {
        // 1. 현재 구간이 index를 포함하지 않으면
        if (index < start || index > end) {
            return;
        }
        // 2. 리프 노드에 도착했다면
        if (start == end) {
            // tree와 arr 변경
            tree[node] = arr[start] = value;
            return;
        }
        int mid = start + (end - start) / 2;
        // 3. 왼쪽 또는 오른쪽 자식으로 이동
        if (index <= mid) {
            update(node * 2, start, mid, index, value);
        } else {
            update(node * 2 + 1, mid + 1, end, index, value);
        }
        // 4. 부모 노드의 합 다시 계산
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    static long query(int node, int start, int end, int left, int right) {
        
        // 1. 현재 구간과 조회 구간이 전혀 겹치지 않으면
        if (left > end || right < start) {
            return 0;
        }
        // 2. 현재 구간이 조회 구간에 완전히 포함되면
        if (left <= start && right >= end) {
            return tree[node];
        }
        // 3. 일부만 겹치면 두 자식의 결과를 합산
        int mid = start + (end - start) / 2;
        return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right);
    }
    public static void main(String[] args) {
        build(1, 0, arr.length - 1);
        
        System.out.println(query(1, 0, 3, 1, 2)); // 6
        update(1, 0, 3, 1, 10)
;
        System.out.println(query(1, 0, 3, 1, 2)); // 15
        System.out.println(query(1, 0, 3, 0, 3)); // 20
    }
}

이제 세그먼트 트리에 대해 알아보았으니, 관련 문제를 풀어보자.

만약 조건이 0-based 인덱스, 1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000, 원소의 절댓값 ≤ 1,000,000,000이며

처음에 정수 배열 길이 N, Q개의 쿼리가 들어오고,

1 i x의 경우 인덱스 i의 값을 x로 변경,

2 l r의 경우 인덱스 l부터 r까지 합 출력을 하라는 의미인 경우,

5 5
2 1 5 3 4
2 1 3
1 2 10
2 1 3
2 0 4
2 2 2

와 같은 input이 들어오고

출력이

9
14
20
10

로 나와야 할 때, 아래와 같이 코드를 작성하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class SegmentTree {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer st;
	
	static int [] arr;
	static long [] tree;
	
	static int N, Q;
	
	static void build(int node, int start, int end) {
		
		if (start == end) {
			tree[node] = arr[start];
			return;
		}
		
		int mid = start + (end - start) / 2;
		
		build(node * 2, start, mid);
		build(node * 2 + 1, mid + 1, end);
		
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
	
	static void update(int node, int start, int end, int index, int value) {
		
		if (index < start || index > end) {
			return;
		}
		
		if (start == end) {
			tree[node] = arr[start] = value;
			return;
		}
		
		int mid = start + (end - start) / 2;
		
		if (index <= mid) {
			update(node * 2, start, mid, index, value);
		} else {
			update(node * 2 + 1, mid + 1, end, index, value);
		}
		
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
	
	static long query(int node, int start, int end, int left, int right) {
		
		if (left > end || right < start) {
			return 0;
		}
		
		if (left <= start && right >= end) {
			return tree[node];
		}
		
		int mid = start + (end - start) / 2;
		
		return query(node * 2, start, mid, left, right) + query(node * 2 + 1, mid + 1, end, left, right);
	}
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		tree = new long[N * 4];
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		build(1, 0, N - 1);
		
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine());
			if(Integer.parseInt(st.nextToken()) == 1) {
				update(1, 0, N - 1, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			} else {
				output.append(query(1, 0, N - 1, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()))).append('\n');
			}
		}
		
		System.out.println(output);
	}
}

만약 이 구간합 세그먼트 트리에서 구간 최솟값 세그먼트 트리로 바꾸려면, 다음의 부분을 바꾸면 된다.

세그먼트가 더 응용될 때는,

• 병합 연산(Merge): 두 자식 노드의 정보를 어떻게 합칠 것인가?
• 항등원(Identity): 결과에 영향을 주지 않는 값은 무엇인가?

이 두가지를 유의하면서 하면 풀 수 있다.

세그먼트 트리의 응용에는 크게 두 가지가 있는데, 다음과 같다.

위의 표에서 기존 구조의 변형에 해당하는 것들의 경우, 원리만 잘 학습한다면 바로바로 응용이 가능하다. 하지만 구조 자체의 확장은 따로 학습이 필요하다.

그래서 나중 포스트에서는, 구조 자체의 확장에 해당하는 Segment Tree 응용을 알아보겠다.

이 글은 정보처리기사 실기를 목전에 두고 있지만 아무런 준비가 되지 않은 전공자들을 위한 글이다. 비전공자나 기초가 없는 사람을 위한 단기 합격법은 아니다. 시험까지 시간이 거의 없는 분들에게, 내가 실제로 사용한 공부 순서와 우선순위를 제공할 것이다.

나와 같이 시험이 극도로 임박한 상황에서, 다음 사항에 해당하는 사람은 뒤로가기를 누를 것을 권한다. 욕심 부리지 말고 이번엔 가볍게 본 후 다음 실기를 노려보자!

• 전공자이지만 코딩과는 거리가 멀다
• 운영체제와 보안을 배우지 않았다.

이 방법은 다음 조건에 가까운 사람에게 적합하다.

• C, Java, Python 중 하나 이상의 코드를 읽고 실행 결과를 추적할 수 있다.
• SELECT, JOIN, GROUP BY 정도의 기본 SQL이 익숙하다.
• 운영체제·네트워크·보안 용어가 완전히 처음은 아니다.
• 기출문제를 풀었을 때 40~50점 안팎이 나온다.

나의 경우, 상황은 다음과 같았다.

• 학부(산업공학과) 전공 학점 4.25/4.5, 졸업한 지 반 년
• 학부 전공에서는 컴퓨터시스템, 운영체제, 네트워크, 정보보안, 알고리즘, 프로그래밍 과목을 이수.
• 초·중·고등학생 대상 코딩 강사로 1년간 일한 경험
• SSAFY 16기에 막 입과한 상태
• 정보처리기사 실기의 운영 방식을 모름
• 정보처리기사 실기의 시험범위를 모름

정보처리기사 필기시험은 작년 2025년 9월 쯤에 합격을 한 상태였다. 그러나 그 이후로 실기시험의 원서접수일이 닥칠 때마다 알림을 설정하지 않아 까먹고 놓치기 일쑤였다. 그러다가 올해 2026년 6월, 드디어 실기 원서접수에 성공을 하였고, 7월 19일(일) 오전 9시에 시험을 보게 되었다. 26년 2회에 해당하는 시험이다.

사실 최근에 SSAFY 16기에 입과한 이후로, 한 달 전 신청했던 정보처리기사 실기 준비를 좀처럼 시작하지 못했다. 일과가 끝나고 나면 피곤해서 집에 가면 바로 잠에 들었고, 주말에는 앞서 말한 학원에 강사 프리랜서 일을 나갔기 때문이다. 그러다가 시험 이틀 전인 금요일이 되고, 이제는 정말 시작해야겠다는 생각이 들었다.

이틀 동안의 공부 순서

<1일차(금요일) 오후>

제헌절이라 SSAFY가 휴일이어서 오후 3시쯤부터 스터디 카페에 가서 공부를 시작하였다. 나는 일단 정보처리기사 실기가 어떻게 진행되는지도 몰랐기에, 그것을 먼저 검색을 했다.

정보처리기사 실기는 2시간 30분 동안 20문제(각 5점, 100점 만점)로 진행되며,
CBT 방식이 아닌, 수기로 진행된다.
따라서 준비물은 검은 볼펜(답안 작성용)과 신분증, 그리고 필요하다면 샤프 및 지우개(계산, 메모 등) 뿐이다.
시험 시작 30분 전에 도착해 있는 것을 추천한다.

참고로 시간은 2시간 30분이지만 시간이 부족할 걱정은 하지 않아도 좋다. 개인적으로, 빨리 풀면 20분 만에 끝나고 오래 걸려도 기껏해야 한 시간이었다. 더 오래 걸린다면 확실히 정답인 문제로 확신을 하겠다는 목적의 검산 때문에 오래 걸리는 것이다. (실제로 나는 연습 때는 20분 ~ 45분 정도 걸렸으며, 실전에서는 확신을 위해 1시간 50분을 사용했다.) 모르는 게 나왔다고 하더라도 시간을 더 준다고 해서 기억나는 것도 아니고 말이다.

나는 작년에 사놓은 <정보처리기사 실기 단기완성(2025)>(시나공) 교재가 이미 있었다. 그러나 나는 시간이 없었기에 개념 설명 부분은 과감히 집어치우고, 뒷부분에 있는 ‘기출문제집’만 집어든 후 바로 2024년 1회 기출을 풀었다.

시험범위도 모르는 상태에서 처음 풀어본 기출은 45분이 걸렸으며, 50점이 나왔다.

나는 채점에서 끝나지 않고, 바로 해당 기출에서

1. 틀렸거나,
2. 맞았지만 몰랐거나 헷갈렸던 문제나,
3. 헷갈리지도 않았지만 정보처리기사 시험에서 관련 개념이 더 나올 것 같은, 자신 없는 주제

가 있으면 전부 오답노트에 수기로 적었다.

주의할 점은 ‘해당 문제의 문제와 답’을 적은 것이 아니라, 해당 문제가 갖고 있는 ‘개념들’을 적어야 한다는 것이다.

어차피 초단기 시험 준비라서 한 번 본 문제는 이미 눈에 들어와서 뭐가 정답인지는 알고, 해당 문제가 향후 그대로 나오기보다는 그 개념 세트에서 다르게 나올 확률이 높기 때문에 해당 개념이 익숙하지 않다면 무조건 알고 가는 게 좋다.

나는 이를 위해 두가지 방법을 사용했다.

1. 해당 문제의 우측 위쪽에 있는, 시나공에서 제공하는 문제 해설 강의
2. Gemini를 활용한 해당 문제의 주변 개념 정리

문제 해설 영상에서는 해당 문제의 풀이 방법만 알려주는 게 아니다. 많은 경우 해당 문제와 관련된 개념들을 전부 알려준다. 굉장히 큰 도움이 되니 개념서를 한번도 펼쳐보지 않은 사람은 QR코드를 꼭 찍어보길 바란다.

그리고 영상만 보고 필기하기보다는 생성형 AI도 이용하는 것이 좋다. 나의 경우 Gemini가 즉답에 편해서 활용을 하였는데, 해당 문제를 찍고 궁금한 점을 물어보면 개인 과외선생님이 된다. 거기다가 ‘정보처리기사 실기’가 목적이라고 하면 외워야 할 것과 무시해도 될 것까지 알려준다.

이런 식으로 오답노트를 적다 보면, 처음에는 물론 시간이 오래 걸린다.

하지만 기출이라는 것은 문제은행이 아니어도 비슷한 유형과 개념들이 계속해서 나오기 때문에, 오답노트를 적는 빈도는 점점 줄어든다.

그렇게 나는 첫째 날은 2024년 1회 실기 (50점), 2023년 3회 실기(55점) 기출만 풀고 잠에 들었다.

<2일차(토요일) 오후>

토요일은 낮에 학원에서 수업을 해야 했기 때문에, 제대로 된 공부는 오후 6시부터 시작했다. 어제에 이어서 기출을 풀고, 오답노트를 작성하는 방식을 2023년 2회, 2023년 1회에도 적용하였다.

2023년 1회에서는 처음으로 60점을 얻었다. 오후 9시였다. 12시간 뒤면 시험 시작인 상황.

NotebookLM의 활용

학원에서 퇴근하기 전 내가 노트에 작성했던 오답정리의 흔적들(사실상 나만의 개념서)을 사진을 찍어서 해당 이미지를 Gemini에게 보낸 후, ‘읽은 다음 .md 형식으로 그대로 정리해달라’고 했다. 그리고 그걸 옵시디언에 옮겨 모든 페이지를 하나의 Markdown 파일로 만든 후, Google의 NotebookLM(현재는 Gemini Notebook으로 이름이 변경되었다)에게 소스로 던져줬다.

이후 할 일은 간단하다.

1. Audio Overview를 만드는 것
2. Quiz를 만드는 것

이후 나는 학원에서 집으로 퇴근하는 1시간 반 동안 내가 정리한 개념서를 팟캐스트로 듣고, 퀴즈도 풀면서 단시간에 머리에 각인했다.

집에 도착한 이후에는, 2026년 1회 실기를 검색하여 스마트폰 상에서 풀었고(여전히 55점이라 불안한 점수였다.), 이후 잠에 들었다.

<당일>

오전 9시 시험이라 6시 반에 일어나서 낫또로 아침을 먹고, 시험장에 가는 길에 눈으로 2025년 3회 실기를 풀었다. 65점의 점수였다. 시험은 그렇게 어렵게 느껴지지 않았다.

실전 시험은 ‘확실하다’고 생각되는 문제 11문제, ‘애매하다’고 생각되는 문제 6문제, ‘모르겠다’고 생각되는 문제가 3문제였는데, 집에 돌아와서 복기 및 가채점을 한 결과, ‘애매하다’고 생각한 문제는 전부 정답이었다. 가채점대로라면, 85점으로 합격기준인 60점보다 넉넉한 점수이다.

(발표된 최종 확인 결과, 82점으로 최종 합격을 받았다!)

최종 요약

나의 경험으로 미루어 보아,

전공자가 이틀만 남겨둔 상황이라면 다음 순서가 현실적이었다.

1. 기출문제로 현재 수준 확인
2. 기출문제 풀기 -> 채점 -> 오답노트(개념정리)의 반복
3. 시나공 교재의 문제해설, Gemini의 문제해설 활용
4. NotebookLM(Gemini Notebook) 활용

결국 답은 기출뿐이다.

이 글을 보는 모두 합격하기를 기원한다!