문제 : https://www.acmicpc.net/problem/16993

 

[ 문제 요약 ]

  • 배열의 초깃값이 주어지고, 범위가 주어질 때, 그 범위 사이에서 가장 큰 부분합을 구하는 문제입니다.

 

[ 테스트 케이스 설명 ]

10									// 수열의 크기 N(1<=100,000)
10 -4 3 1 5 6 -35 12 21 -1			// 수열 ((절대값) |Ai| <= 1,000)
10									// 쿼리개수 M(1<=100,000)
1 1
3 4
1 6
2 6
6 6
7 7
8 9
8 10
1 10
5 8
// M개 줄에 쿼리 요청에 대한 출력을 한 줄에 하나씩 순서대로 출력
10
4
21
15
6
-35
33
33
33
12

 

 

[ 문제 해설 ]

 

이 문제는 별도의 자료구조를 만들어 풀 수 있습니다.

class Node{
	int left, right, sum, max;
	Node(int l, int r, int s, int m){
		left = l;
		right = r;
		sum = s;
		max = m;
	}
}

 

위 와 같이 트리의 노드 하나당 left, right, sum, max 값을 갖도록 만듭니다.

 

각각의 원소 의미는 아래와 같습니다.

 

  • left : 해당 객체가 표현하는 구간에서 접두사(왼쪽 끝)부터 시작해서 얻을 수 있는 최대 연속합, 예를 들어 구간 값이 [3, -2, 5] 이면, 접두사로는 [3], [3, -2], [3, -2,5] 일 때 최댓값은 6임
  • right : 해당 객체가 표현하는 구간에서 접미사(오른쪽 끝)부터 시작해서 얻을 수 있는 최대 합, 예를 들어 값이 [3, -2, 5] 라면, [5], [5, -2], [5, -2, 3] 임, 최대는 6이 됨
  • sum : 구간 전체 합, 해당 구간에 속한 모든 원소를 더한 값( 다른 연산시 필요함 )
  • max : 구간 내부 최대 연속합으로, 구간 내 어디서든 시작, 끝날 수 있는 연속 부분합 중 가장 큰 값

그러면 위 내용을 갖는 객체를 통해 어떤 식으로 계산해야 하는지를 알아야 합니다.

 

세그먼트 트리 생성 방식이 후위 순회이기 때문에, 왼쪽, 오른쪽 자식 노드를 만든 후 자기 자신(부모)를 생성합니다.

 

그래서 리프 노드 같은 경우 모든 값을 자기 자신으로 초기화하고, 자식 노드를 2개 갖는 부모 노드는 별도의 식을 활용해 생성합니다.

 

	public static Node init(int treeNode, int s, int e) {
		if(s == e)
			return tree[treeNode] = new Node(arr[s], arr[s], arr[s], arr[s]);

		int mid = (s + e) >> 1;
		
		Node l = init(treeNode << 1, s, mid);
		Node r = init(treeNode << 1 | 1, mid + 1, e);
		
		return tree[treeNode] = makeNode(l, r);
	}

 

위 코드에서 보듯이 리프 노드는 new Node(arr[s], arr[s], arr[s], arr[s]); 와 같이 자기 자신으로 모두 초기화하고,

 

왼쪽 자식 노드 'l'과 오른쪽 자식 노드 'r'을 구해온 뒤, makeNode라는 함수에 전달하여 자기 자신을 생성하고 반환합니다.

 

	public static Node makeNode(Node l, Node r) {
		return new Node(
					Math.max(l.left, l.sum + r.left),
					Math.max(r.right, r.sum + l.right),
					l.sum + r.sum,
					Math.max(l.right + r.left, Math.max(l.max, r.max))
				);
	}

 

왼쪽 자식 노드와 오른쪽 자식 노드를 통해 자기 자신을 생성하는 방법은 간단합니다.

 

left : 왼쪽 자식 노드의 왼쪽 값(범위의 접두사 중 가장 큰 값) , 왼쪽 자식 노드의 총합 + 오른쪽 자식 노드의 왼쪽 값

right : 왼쪽과는 반대로 계산

sum : 왼쪽, 오른쪽 자식 노드의 sum을 합침

max : max( 왼쪽 자식 노드의 오른쪽 값 + 오른쪽 자식 노드의 왼쪽 값, max(왼쪽 자식 노드의 max, 오른쪽 자식 노드의 max) )

 

위 형태가 잘 이해되지 않을 수 있는데, 이해를 위해 가져야 할 기본 개념을 먼저 적립해야 합니다. 왼쪽 노드와 오른쪽 노드에 저장된 값들은 특정 범위 내의 값들입니다.

 

  • left (접두사 최대합)
    • 부모 구간의 왼쪽 끝(s)부터 어떤 연속합을 택할 때, 두 가지 선택지가 있습니다:
      • 왼쪽 자식 구간에서만 택한 경우 → l.left
      • 왼쪽 자식 구간 전체(l.sum)를 모두 택하고 이어서 오른쪽 자식 구간의 접두사(r.left)를 택한 경우 → l.sum + r.left
      • 그림으로 보면 아래와 같습니다. ( 왼쪽의 왼쪽만 선택하느냐, 왼쪽의 모든 것을 다 선택하고 오른쪽의 왼쪽만 선택하느냐입니다. )

 

 

  • right (접미사 최대합)
    • 부모 구간의 오른쪽 끝(e)에서 연속합을 택할 때:
      • 오른쪽 자식 구간에서만 택 → r.right
      • 오른쪽 자식 전체(r.sum) + 왼쪽 자식의 접미사(l.right) → r.sum + l.right

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	
	static class Node{
		int left, right, sum, max;
		Node(int l, int r, int s, int m){
			left = l;
			right = r;
			sum = s;
			max = m;
		}
	}
	
	static final int MIN = -100_000_005;
	static int[] arr;
	static Node[] tree;
	static Node dummy = new Node(MIN, MIN, 0, MIN);
	
	public static Node makeNode(Node l, Node r) {
		return new Node(
					Math.max(l.left, l.sum + r.left),
					Math.max(r.right, r.sum + l.right),
					l.sum + r.sum,
					Math.max(l.right + r.left, Math.max(l.max, r.max))
				);
	}
	
	public static Node init(int treeNode, int s, int e) {
		if(s == e)
			return tree[treeNode] = new Node(arr[s], arr[s], arr[s], arr[s]);

		int mid = (s + e) >> 1;
		
		Node l = init(treeNode << 1, s, mid);
		Node r = init(treeNode << 1 | 1, mid + 1, e);
		
		return tree[treeNode] = makeNode(l, r);
	}
	
	public static Node query(int treeNode, int s, int e, int left, int right) {
		if(e < left || right < s)
			return dummy;
		if(left<=s && e<= right)
			return tree[treeNode];
		
		int mid = (s + e) >> 1;
		
		Node l = query(treeNode << 1, s, mid, left, right);
		Node r = query(treeNode << 1 | 1, mid + 1, e, left, right);
		
		return makeNode(l, r);
	}
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N	= Integer.parseInt(br.readLine());//수열의 크기 N(1<=100,000)
		arr		= new int[N + 1];
		tree	= new Node[N * 4];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			arr[i] = Integer.parseInt(st.nextToken());// 수열 ((절대값) |Ai| <= 1,000)
		
		init(1 ,1, N);
		
		StringBuilder sb = new StringBuilder();
		
		int M = Integer.parseInt(br.readLine());
		
		while(M-->0)
		{
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());	// 1<=N
			int j = Integer.parseInt(st.nextToken());	// 1<=N
			
			// i,j 구간의 가장 큰 부분합 출력
			Node ans = query(1, 1, N, i, j);
			
			sb.append(ans.max).append('\n');
		}
		System.out.print(sb);		
	}
}

'알고리즘 > 세그먼트트리' 카테고리의 다른 글

세그먼트 트리의 활용 예시  (0) 2025.05.24
BOJ 백준 2336 굉장한 학생  (1) 2025.04.20

+ Recent posts