세그먼트 트리 연습

류한선·2025년 6월 26일

실기연습-2

목록 보기

43/95

맞아요! 💡 정보처리기사 실기 시험 형태에 맞춰서, 코드를 아예 미리 주고 출력값만 채우도록 연습하는 스타일로 준비해 드릴게요.

아래에 **세그먼트 트리 풀이 코드(자바)**를 드릴 테니,
여러분은 최종 출력값만 맞히면 됩니다.
그리고, 각 줄 한 줄 한 줄 디버깅하면서 주석 형태의 해설도 추가해 드릴 수 있어요.

✅ 정답을 채우면 되는 문제

📜 문제

다음 코드를 보고 출력값을 쓰시오.

🧪 입력

🎯 출력 (여기만 채우기)

____
____

📝 제공되는 Java 코드

아래 코드를 정리된 상태로 드릴게요.
(실기에서 보통 이 정도 길이의 코드를 주고 출력을 채우도록 합니다.)

import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static long[] arr;
    static long[] tree;

    static long init(int node, int start, int end) {
        if (start == end) return tree[node] = arr[start];
        int mid = (start + end) / 2;
        return tree[node] = init(node*2, start, mid) + init(node*2+1, mid+1, end);
    }

    static long sum(int node, int start, int end, int left, int right) {
        if (right < start || end < left) return 0;
        if (left <= start && end <= right) return tree[node];
        int mid = (start + end) / 2;
        return sum(node*2, start, mid, left, right) + sum(node*2+1, mid+1, end, left, right);
    }

    static void update(int node, int start, int end, int index, long diff) {
        if (index < start || index > end) return;
        tree[node] += diff;
        if (start != end) {
            int mid = (start + end) / 2;
            update(node*2, start, mid, index, diff);
            update(node*2+1, mid+1, end, index, diff);
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new long[N+1];
        tree = new long[N*4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) arr[i] = Long.parseLong(st.nextToken());
        init(1, 1, N);

        int Q = Integer.parseInt(br.readLine());
        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            if (cmd == 1) {
                int index = Integer.parseInt(st.nextToken());
                long val = Long.parseLong(st.nextToken());
                long diff = val - arr[index];
                arr[index] = val;
                update(1, 1, N, index, diff);
            } else {
                int left = Integer.parseInt(st.nextToken());
                int right = Integer.parseInt(st.nextToken());
                System.out.println(sum(1, 1, N, left, right));
            }
        }
    }
}

🎯 예상 출력

이제 위의 입력을 이용해 트리 연산을 하나씩 따라가며 출력값을 채우면 됩니다.

🧠 정답:

6
16

좋아요! 🧠
이제 init() 메서드가 호출되며 세그먼트 트리를 만드는 과정을,
입력 수열 [1,2,3,4,5] 기준으로 아주 자세히 디버깅해 드릴게요.

💡 미리 알아둘 것

init(node, start, end) 함수는 tree[node]가 수열 arr[start~end]의 합이 되도록 채우는 함수입니다.

트리의 루트 node는 node=1, 범위 start=1, end=N(=5)에서 시작합니다.

🔍 수열

index: 1 2 3 4 5
값:    1 2 3 4 5

🧠 트리 초기화 단계-by-단계

1️⃣ 최초 호출

init(1, 1, 5); // node=1, start=1, end=5

start != end이므로 리프가 아님 → mid 계산:
```
mid = (1+5)/2 = 3
```
왼쪽 자식 호출: init(2,1,3)
오른쪽 자식 호출: init(3,4,5)

🧬 트리 구조 (지금까지의 호출 트리)

1(1~5)
├─2(1~3)
└─3(4~5)

2️⃣ `init(2,1,3)` 호출

mid = (1+3)/2 = 2
왼쪽 호출: init(4,1,2)
오른쪽 호출: init(5,3,3)

🧬 트리 구조 확장

1(1~5)
├─2(1~3)
│  ├─4(1~2)
│  └─5(3~3)
└─3(4~5)

3️⃣ `init(4,1,2)` 호출

mid = (1+2)/2 = 1
왼쪽 호출: init(8,1,1)
오른쪽 호출: init(9,2,2)

🧬 트리 구조 확장

1(1~5)
├─2(1~3)
│  ├─4(1~2)
│  │  ├─8(1~1)
│  │  └─9(2~2)
│  └5(3~3)
└─3(4~5)

4️⃣ `init(8,1,1)` 호출

start == end == 1 → 리프 도달!
tree[8] = arr[1] = 1 반환
이제 호출 종료 후 상위 호출(init(4,1,2))로 돌아감

📍현재 트리 상태

tree[8] = 1

5️⃣ `init(9,2,2)` 호출

리프 도달
tree[9] = arr[2] = 2 반환
돌아가서 init(4,1,2)의 남은 계산

6️⃣ `init(4,1,2)`의 계산

이미 left(8) = 1 반환, right(9) = 2 반환 받았음
tree[4] = 1+2 = 3 반환

📍현재 트리 상태

tree[8]=1 (1번째 값)
tree[9]=2 (2번째 값)
tree[4]=3 (1~2 합)

7️⃣ `init(5,3,3)` 호출

리프 도달
tree[5] = arr[3] = 3 반환
이제 init(2,1,3)의 남은 계산

8️⃣ `init(2,1,3)`의 계산

left(4) = 3, right(5) = 3
tree[2] = 3+3 = 6

📍현재 트리 상태

tree[2]=6 (1~3 합)

9️⃣ `init(3,4,5)` 호출

mid = (4+5)/2 = 4
왼쪽 호출: init(6,4,4)
오른쪽 호출: init(7,5,5)

🔟 `init(6,4,4)` 호출

리프 도달
tree[6] = arr[4] = 4

1️⃣1️⃣ `init(7,5,5)` 호출

리프 도달
tree[7] = arr[5] = 5

1️⃣2️⃣ `init(3,4,5)` 계산

left(6) = 4, right(7) = 5
tree[3] = 4+5 = 9

1️⃣3️⃣ 최상단 `init(1,1,5)` 계산

left(2) = 6, right(3) = 9
tree[1] = 6+9 = 15

✅ 최종 트리 상태 정리

tree[1] = 15 (1~5 합)
tree[2] = 6  (1~3 합)
tree[3] = 9  (4~5 합)
tree[4] = 3  (1~2 합)
tree[5] = 3  (3~3 합)
tree[6] = 4  (4~4 합)
tree[7] = 5  (5~5 합)
tree[8] = 1  (1~1 합)
tree[9] = 2  (2~2 합)

좋아요! 🎯
이 부분은 main() 함수에서 쿼리를 처리하는 부분이에요.
지금 우리가 디버깅할 부분을 한 줄씩 뜯어서, 실제 입력값을 예로 들어가며 어떤 일이 벌어지는지 자세히 설명할게요.

🧠 상황 정리

우리가 위에서 만든 트리는 초기 상태:

arr = [-, 1,2,3,4,5]  // 1부터 시작
tree = ... (이미 계산됨)

그리고 프로그램의 입력 중 쿼리 부분은 아래와 같습니다:

2     <- 쿼리 수(Q)
2 1 3 <- 쿼리1
1 3 10 <- 쿼리2
2 2 4 <- 쿼리3

여기서 Q=2라고 되어 있지만, 실제 위 예제 입력에는 쿼리 수가 3이어야 합니다.
(입출력 예제를 기준으로 하면 Q=3 이었죠. 여기선 수정해서 Q=3라고 생각하고 디버깅할게요.)

🔍 `main()`의 쿼리 부분 디버깅

✅ `int Q = Integer.parseInt(br.readLine());`

br.readLine() → "3"
Integer.parseInt("3") → Q = 3

이제 while (Q-- > 0)에서 총 3번 반복합니다.

🔄 1번째 루프 (`Q-- > 0`)

Q-- → 현재 Q=3, 비교 후 Q=2가 됩니다.

1️⃣ `st = new StringTokenizer(br.readLine());`

br.readLine() → "2 1 3"
st = new StringTokenizer("2 1 3")

2️⃣ `int cmd = Integer.parseInt(st.nextToken());`

st.nextToken() → "2"
cmd = 2

🧠 `if (cmd == 1)`? 아니니까 `else` 부분으로 갑니다.

→ 쿼리 타입 2 l r, 부분합을 계산하는 쿼리!

🔄 2번째 루프 (`Q-- > 0`)

Q-- → 현재 Q=2, 비교 후 Q=1이 됩니다.

1️⃣ `st = new StringTokenizer(br.readLine());`

br.readLine() → "1 3 10"
st = new StringTokenizer("1 3 10")

2️⃣ `int cmd = Integer.parseInt(st.nextToken());`

st.nextToken() → "1"
cmd = 1

🧠 `if (cmd == 1)` 조건 참! → 이 부분을 실행:

int index = Integer.parseInt(st.nextToken()); // index=3
long val = Long.parseLong(st.nextToken());    // val=10
long diff = val - arr[index];                 // diff = 10 - arr[3]

arr[index] = val;
update(1,1,N,index,diff);

🔍 여기서 한 줄씩 디버깅:

✅ index = Integer.parseInt(st.nextToken());

st.nextToken() → "3"
index = 3

✅ long val = Long.parseLong(st.nextToken());

st.nextToken() → "10"
val = 10

✅ long diff = val - arr[index];

현재 arr[3] = 3 (원래 수열값)
diff = 10 - 3 = 7

✅ arr[index] = val;

arr[3] = 10 으로 갱신

✅ update(1,1,N,index,diff);

트리에서 index=3의 값만 7만큼 증가

🔄 3번째 루프 (`Q-- > 0`)

Q-- → 현재 Q=1, 비교 후 Q=0

1️⃣ `st = new StringTokenizer(br.readLine());`

br.readLine() → "2 2 4"
st = new StringTokenizer("2 2 4")

2️⃣ `int cmd = Integer.parseInt(st.nextToken());`

st.nextToken() → "2"
cmd = 2

→ 부분합 쿼리(sum() 호출)

🎯 이렇게 main()의 쿼리 부분 한 줄 한 줄 디버깅을 끝냈습니다.

좋아요! 🔥
이번에는 update() 메서드를 실제 호출 상황을 바탕으로 한 줄 한 줄 디버깅해 드릴게요.

📍 상황 정리

우리가 위에서 디버깅한 부분 중:

int index = 3;
long diff = 7; // 10(새 값) - 3(기존 값)
update(1, 1, N, index, diff); // N = 5

여기서 update() 호출의 트리 구조를 한 줄 한 줄 따라가 보겠습니다.

🧠 트리 상태(업데이트 전)

이전에 init()에서 트리의 주요 노드 값:

tree[1] = 15 (1~5)
tree[2] = 6  (1~3)
tree[3] = 9  (4~5)
tree[4] = 3  (1~2)
tree[5] = 3  (3~3)
tree[6] = 4  (4~4)
tree[7] = 5  (5~5)
tree[8] = 1  (1~1)
tree[9] = 2  (2~2)

그리고 arr = [1,2,3,4,5] → arr[3] = 3이었는데, 이제 arr[3]=10으로 바꿀 겁니다.

🧬 `update(1,1,5,3,7)` 호출

🔍 `update()` 메서드 정의

static void update(int node, int start, int end, int index, long diff) {
    if (index < start || index > end) return;     // 범위 밖이면 return
    tree[node] += diff;                           // 트리 현재 node 값 갱신
    if (start != end) {                            // 리프가 아니면
        int mid = (start+end)/2;
        update(node*2, start, mid, index, diff);  // 왼쪽 자식
        update(node*2+1, mid+1, end, index, diff);// 오른쪽 자식
    }
}

🧠 호출 트리 따라가기

📝 `update(1,1,5,3,7)`

현재 index=3, 범위 [1,5] → 포함됨
tree[1] += 7 → tree[1]=15+7=22
🔄 (루트의 합 갱신)
mid = (1+5)/2 = 3
리프 아님 → 왼쪽 자식 호출 & 오른쪽 자식 호출

📝 `update(2,1,3,3,7)`

index=3, 범위 [1,3] → 포함됨
tree[2] += 7 → tree[2]=6+7=13
mid = (1+3)/2 = 2
리프 아님 → 왼쪽 & 오른쪽 호출

📝 `update(4,1,2,3,7)`

index=3, 범위 [1,2] → 포함 안됨
return; (중단)

📝 `update(5,3,3,3,7)`

index=3, 범위 [3,3] → 포함됨
tree[5] += 7 → tree[5]=3+7=10
start==end==3 (리프이므로 하위 호출 없음)

📝 `update(3,4,5,3,7)` (오른쪽 자식 호출)

index=3, 범위 [4,5] → 포함 안됨
return;

✅ 호출 종료 후 트리 상태

이제 트리의 바뀐 부분을 정리:

tree[1] = 22  // 1~5 합 (기존 15 → +7)
tree[2] = 13  // 1~3 합 (기존 6 → +7)
tree[5] = 10  // 3~3 합 (기존 3 → +7)

좋아요! 이번엔 else 부분(sum() 호출 부분)과 while(Q-- > 0) 부분을 정말 디버깅하듯 한 줄 한 줄 아주 구체적으로 설명해 드릴게요.

지금까지 정리된 상황을 떠올리며 시작해봅시다.

🔍 `main()`에서 쿼리 처리 부분

코드를 다시 보면:

int Q = Integer.parseInt(br.readLine());  // 쿼리 수 읽기
while (Q-- > 0) {
    st = new StringTokenizer(br.readLine()); // 한 쿼리 줄 읽고
    int cmd = Integer.parseInt(st.nextToken()); // 쿼리 종류 (1 또는 2)

    if (cmd == 1) {
        int index = Integer.parseInt(st.nextToken());
        long val = Long.parseLong(st.nextToken());
        long diff = val - arr[index]; 
        arr[index] = val;
        update(1, 1, N, index, diff); 
    } else {
        int left = Integer.parseInt(st.nextToken());
        int right = Integer.parseInt(st.nextToken());
        System.out.println(sum(1, 1, N, left, right));
    }
}

이 부분을 입출력 예제를 기준으로 세세하게 디버깅해 보겠습니다.

🧠 우리가 사용하는 입력 예제

5
1 2 3 4 5
3         <- Q 쿼리 수
2 1 3     <- sum(1~3)
1 3 10    <- arr[3] = 10
2 2 4     <- sum(2~4)

🎯 `Q = Integer.parseInt(br.readLine())`

br.readLine() → "3"
Q = 3

지금부터 while (Q-- > 0) 루프를 돌아요.

🔄 첫 번째 반복 (`Q-- > 0`)

현재 Q = 3 → Q-- 하면서 검사 → 조건 참 → 내부 Q 값 2로 감소
st = new StringTokenizer(br.readLine())
- br.readLine() → "2 1 3"
- st.nextToken() → "2"
- cmd = 2 (sum 쿼리)

🧠 sum 쿼리

→ else 블록 수행:

int left = Integer.parseInt(st.nextToken());  // left = 1
int right = Integer.parseInt(st.nextToken()); // right = 3

이제 sum(1,1,N,left,right) 호출 → sum(1,1,5,1,3) 호출
트리에서 1~3 부분합을 계산
반환값 출력 → System.out.println(6)

🔄 두 번째 반복 (`Q-- > 0`)

현재 Q = 2 → 검사 후 Q = 1
st = new StringTokenizer(br.readLine())
- br.readLine() → "1 3 10"
- cmd = 1

🧠 update 쿼리

→ if (cmd == 1) 블록 실행:

int index = Integer.parseInt(st.nextToken()); // index=3
long val = Long.parseLong(st.nextToken());    // val=10
long diff = val - arr[index];                 // diff = 10 - arr[3]

현재 arr[3] 은 업데이트 전 값 = 3
따라서 diff = 10-3 = 7
arr[index] = val; → arr[3]=10 으로 변경
update(1,1,N,index,diff); 호출
→ 트리 내부의 index=3 부분을 7만큼 증가시킴 (이전에 디버깅한 부분)

🔄 세 번째 반복 (`Q-- > 0`)

현재 Q = 1 → 검사 후 Q = 0
st = new StringTokenizer(br.readLine())
- br.readLine() → "2 2 4"
- cmd = 2

🧠 sum 쿼리

→ else 블록:

int left = Integer.parseInt(st.nextToken());  // left = 2
int right = Integer.parseInt(st.nextToken()); // right = 4
System.out.println(sum(1,1,N,2,4));

이제 트리는 arr = [1,2,10,4,5] 상태 반영 중
트리의 sum 호출 → sum(1,1,5,2,4) 호출
부분합 계산 → 반환값 출력 → 16

✏️ 정리

실행 순서를 한 줄 한 줄 추적하면서:

cmd == 1 일 때 수열 값 갱신, 트리 update()
cmd == 2 일 때 트리 sum() 호출 → 출력
Q-- > 0는 한 쿼리당 Q를 1씩 줄이면서 종료조건 검사

이해가 잘 되도록 실제 수열 상태와 트리 상태를 중간중간 챙기며 디버깅하는 것이 중요해요.

류한선

good

이전 포스트

각종 트릭2(일단 패스)

다음 포스트

세그먼트 트리 연습

실기연습-2

✅ 정답을 채우면 되는 문제

📜 문제

🧪 입력

🎯 출력 (여기만 채우기)

📝 제공되는 Java 코드

🎯 예상 출력

🧠 정답:

🔍 수열

🧠 트리 초기화 단계-by-단계

1️⃣ 최초 호출

🧬 트리 구조 (지금까지의 호출 트리)

2️⃣ init(2,1,3) 호출

🧬 트리 구조 확장

3️⃣ init(4,1,2) 호출

🧬 트리 구조 확장

4️⃣ init(8,1,1) 호출

📍현재 트리 상태

5️⃣ init(9,2,2) 호출

6️⃣ init(4,1,2)의 계산

📍현재 트리 상태

7️⃣ init(5,3,3) 호출

8️⃣ init(2,1,3)의 계산

📍현재 트리 상태

9️⃣ init(3,4,5) 호출

🔟 init(6,4,4) 호출

1️⃣1️⃣ init(7,5,5) 호출

1️⃣2️⃣ init(3,4,5) 계산

1️⃣3️⃣ 최상단 init(1,1,5) 계산

✅ 최종 트리 상태 정리

🧠 상황 정리

🔍 main()의 쿼리 부분 디버깅

✅ int Q = Integer.parseInt(br.readLine());

🔄 1번째 루프 (Q-- > 0)

1️⃣ st = new StringTokenizer(br.readLine());

2️⃣ int cmd = Integer.parseInt(st.nextToken());

🧠 if (cmd == 1)? 아니니까 else 부분으로 갑니다.

🔄 2번째 루프 (Q-- > 0)

1️⃣ st = new StringTokenizer(br.readLine());

2️⃣ int cmd = Integer.parseInt(st.nextToken());

🧠 if (cmd == 1) 조건 참! → 이 부분을 실행:

🔍 여기서 한 줄씩 디버깅:

🔄 3번째 루프 (Q-- > 0)

1️⃣ st = new StringTokenizer(br.readLine());

2️⃣ int cmd = Integer.parseInt(st.nextToken());

📍 상황 정리

🧠 트리 상태(업데이트 전)

🧬 update(1,1,5,3,7) 호출

🔍 update() 메서드 정의

🧠 호출 트리 따라가기

📝 update(1,1,5,3,7)

📝 update(2,1,3,3,7)

📝 update(4,1,2,3,7)

📝 update(5,3,3,3,7)

📝 update(3,4,5,3,7) (오른쪽 자식 호출)

✅ 호출 종료 후 트리 상태

🔍 main()에서 쿼리 처리 부분

🧠 우리가 사용하는 입력 예제

🎯 Q = Integer.parseInt(br.readLine())

🔄 첫 번째 반복 (Q-- > 0)

🧠 sum 쿼리

🔄 두 번째 반복 (Q-- > 0)

🧠 update 쿼리

🔄 세 번째 반복 (Q-- > 0)

🧠 sum 쿼리

✏️ 정리

각종 트릭2(일단 패스)

상속2

0개의 댓글

2️⃣ `init(2,1,3)` 호출

3️⃣ `init(4,1,2)` 호출

4️⃣ `init(8,1,1)` 호출

5️⃣ `init(9,2,2)` 호출

6️⃣ `init(4,1,2)`의 계산

7️⃣ `init(5,3,3)` 호출

8️⃣ `init(2,1,3)`의 계산

9️⃣ `init(3,4,5)` 호출

🔟 `init(6,4,4)` 호출

1️⃣1️⃣ `init(7,5,5)` 호출

1️⃣2️⃣ `init(3,4,5)` 계산

1️⃣3️⃣ 최상단 `init(1,1,5)` 계산

🔍 `main()`의 쿼리 부분 디버깅

✅ `int Q = Integer.parseInt(br.readLine());`

🔄 1번째 루프 (`Q-- > 0`)

1️⃣ `st = new StringTokenizer(br.readLine());`

2️⃣ `int cmd = Integer.parseInt(st.nextToken());`

🧠 `if (cmd == 1)`? 아니니까 `else` 부분으로 갑니다.

🔄 2번째 루프 (`Q-- > 0`)

1️⃣ `st = new StringTokenizer(br.readLine());`

2️⃣ `int cmd = Integer.parseInt(st.nextToken());`

🧠 `if (cmd == 1)` 조건 참! → 이 부분을 실행:

🔄 3번째 루프 (`Q-- > 0`)

1️⃣ `st = new StringTokenizer(br.readLine());`

2️⃣ `int cmd = Integer.parseInt(st.nextToken());`

🧬 `update(1,1,5,3,7)` 호출

🔍 `update()` 메서드 정의

📝 `update(1,1,5,3,7)`

📝 `update(2,1,3,3,7)`

📝 `update(4,1,2,3,7)`

📝 `update(5,3,3,3,7)`

📝 `update(3,4,5,3,7)` (오른쪽 자식 호출)

🔍 `main()`에서 쿼리 처리 부분

🎯 `Q = Integer.parseInt(br.readLine())`

🔄 첫 번째 반복 (`Q-- > 0`)

🔄 두 번째 반복 (`Q-- > 0`)

🔄 세 번째 반복 (`Q-- > 0`)