kyjdummy 님의 블로그

문제 : 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);		
	}
}

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

[ 문제 요약 ]

• A가 B보다 3가지 성적이 모두 좋다면 A는 대단한 것이고, 이 A보다 대단한 학생이 없으면 A를 굉장하다고 합니다. 여기서 굉장한 학생의 수를 구하는 것입니다.

[ 테스트 케이스 설명 ]

10 // 학생 수 1<=500,000
2 5 3 8 10 7 1 6 9 4 // 각 랭크별 학생 번호 
1 2 3 4 5 6 7 8 9 10 // 각 랭크별 학생 번호 
3 8 7 10 5 4 1 2 6 9 // 각 랭크별 학생 번호

[ 문제 해설 ]

문제를 간단하게 말해서 3개 과목 모두 나보다 순위가 작은 사람이 없으면 나는 굉장한 학생이 되는 것입니다.

그래서 입력이 3줄로 들어올 때, 한 학생의 3가지 과목 순위를 담을 객체를 만들어, 각 학생마다 순위들을 몰아서 하나의 객체에 저장해 놓습니다.

그럼 하나의 객체에는 과목(1), 과목(2), 과목(3)의 순위가 각각 들어가 있을 텐데, 이를 과목(1)의 순위 기준으로 오름차순 정렬합니다.

정렬한 후 첫 번째 객체는 무조건 굉장한 학생일 것입니다. 그 이유는 내 첫 번째 과목의 순위가 1등이기 때문에 당연히 나보다 3과목의 순위가 모두 작은 학생이 없을 것이기 때문입니다.

정렬된 배열의 두 번째 객체부터는 확인을 해봐야 합니다.

두 번째 객체는 과목(1)의 순위가 두 번째이기 때문에, 과목(2)와 과목(3)의 순위가 어떤지 파악해야 합니다. 파악을 하는 기준은,

내 왼편에 있는, 즉 이미 탐색한 객체들의 과목(2), 과목(3)의 순위들만 확인하면 됩니다.

이미 과목(1) 기준으로 정렬했기 때문에 내 왼편의 객체들은 과목(1)이 나보다 작다는 것이 확인되었으니,

그들의 과목(2)와 과목(3)의 순위가 내 과목(2)와 내 과목(3)보다 모두 작은 게 있다면 나는 굉장한 학생이 아닐 것입니다.

모두 작은 게 없다면 나는 굉장한 학생이 됩니다.

그럼 내 왼편의 객체들의 과목(2)와 과목(3)의 순위를 어떻게 빠르게 탐색할 수 있을까요?

방법은 세그먼트 트리를 이용하며, 세그먼트 트리의 index는 과목(2)의 값을,

인덱스의 저장하는 value는 과목(3)의 값으로 하고, 최솟값을 구하는 세그먼트 트리를 만들어 해결할 수 있습니다.

[ 정답 코드 ]

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

class Main{
	
	static final int MAX = 1<<30;
	static int[] tree;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N		= Integer.parseInt(br.readLine());	// 1 ≤ N ≤ 500,000
		Node[] node = new Node[N];
		tree		= new int[N * 4];
		
		for(int i=0; i<N; i++)
			node[i] = new Node(0,0,0);
		
		for(int i=0; i<3; i++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int rnk=1; rnk<=N; rnk++)
			{
				int index = Integer.parseInt(st.nextToken()) - 1;// 해당 학생의 번호

				if(i == 0)
					node[index].rank1 = rnk;
				else if(i == 1)
					node[index].rank2 = rnk;
				else
					node[index].rank3 = rnk;
			}
		}
		
		Arrays.fill(tree, MAX);
		Arrays.sort(node);
		
		int ans = 0;
		
		for(Node now : node)
		{
			int min = query( 1, 1, N, 1, now.rank2 );
			
			if(min > now.rank3)
				++ans;
			
			update( 1, 1, N, now.rank2, now.rank3 );
		}
		
		System.out.print(ans);
	}
	public static void update(int treeNode, int s, int e, int targetIdx, int value) {
		if(e < targetIdx || targetIdx < s)
			return;
		
		if(s == e)
		{
			tree[treeNode] = value;
			return;
		}
		
		int mid = (s + e) >> 1;
		
		update(treeNode << 1, s, mid, targetIdx, value);
		update(treeNode << 1 | 1, mid + 1, e, targetIdx, value);
		
		tree[treeNode] = Math.min(tree[treeNode << 1], tree[treeNode << 1 | 1]);
	}
	public static int query(int treeNode, int s, int e, int left, int right) {
		if(e < left || right < s)
			return MAX;
		
		if(left<=s && e<=right)
			return tree[treeNode];
		
		int mid = (s + e) >> 1;
		int l	= query(treeNode << 1, s, mid, left, right);
		int r	= query(treeNode << 1 | 1, mid + 1, e, left, right);
		
		return Math.min(l, r);
	}
}

class Node implements Comparable<Node>{
	int rank1, rank2, rank3;
	Node(int r1, int r2, int r3){
		rank1 = r1;
		rank2 = r2;
		rank3 = r3;
	}
	@Override
	public int compareTo(Node o) {
		return rank1 - o.rank1;
	}
}