공부 기록

세그먼트 트리는 구간의 최솟값을 구하는데 가장 효율적인 자료구조이다.

• 각 노드에 저장되는 값은 3가지이다 --> 저장되는 칸의 번호, 구간 시작, 구간 끝 (구간시작==구간끝: 리프 노드)
• 예를 들어 3~5 노드는 구간 3~5에서 최솟값을  저장하고 있다.
• 배열을 이용해서 구할 수 있다. --> x의 왼쪽 자식은 2x, 오른쪽 자식은 2x+1 이런 식으로,,,
• 모든 노드는 자식이 무조건 0개 또는 2개이다.
• 리프 노드가 n개인 full binary tree가 필요한 노드의 개수: 높이 h=lgn일 때 2^(h+1)

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();

		int arr[] = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			arr[i] = in.nextInt();
		}

		int h = (int) Math.ceil(Math.log(n) / Math.log(2));
		int maxTree[] = new int[1 << (h + 1)];
		int minTree[] = new int[1 << (h + 1)];

		initTree(true, arr, maxTree, 1, 1, n);
		initTree(false, arr, minTree, 1, 1, n);

		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();

			System.out.print(findSegment(false, minTree, 1, 1, n, start, end) + " ");
			System.out.println(findSegment(true, maxTree, 1, 1, n, start, end));
		}
	}

	public static int initTree(boolean isMaxTree, int[] arr, int[] tree, int index, int start, int end) {
		if (start == end) {
			tree[index] = arr[start];
			return tree[index];
		}

		int mid = (start + end) / 2;

		if (isMaxTree) {
			tree[index] = Math.max(initTree(isMaxTree, arr, tree, index * 2, start, mid),
					initTree(isMaxTree, arr, tree, index * 2 + 1, mid + 1, end));

			return tree[index];
		} else {
			tree[index] = Math.min(initTree(isMaxTree, arr, tree, index * 2, start, mid),
					initTree(isMaxTree, arr, tree, index * 2 + 1, mid + 1, end));

			return tree[index];
		}
	}

	public static int findSegment(boolean isFindMax, int[] tree, int index, int start, int end, int left, int right) {

		if (left > end || right < start) {
			// 범위와 관계 없어서 볼 필요가 없을 때
			return -1;
		}

		if (left <= start && right >= end) {
			// 범위에 구간이 포함되는 경우, left - start - end - right
			return tree[index];
		}

		// 범위에 구간이 일부 포함되는 경우
		// left - start - right - end 또는
		// start - left - right - end
		int mid = (start + end) / 2;
		if (isFindMax) {
			return Math.max(findSegment(isFindMax, tree, index * 2, start, mid, left, right),
					findSegment(isFindMax, tree, index * 2 + 1, mid + 1, end, left, right));
		} else {
			int segmentLeft = findSegment(isFindMax, tree, index * 2, start, mid, left, right);
			int segmentRight = findSegment(isFindMax, tree, index * 2 + 1, mid + 1, end, left, right);

			if (segmentLeft == -1) {
				return segmentRight;
			} else if (segmentRight == -1) {
				return segmentLeft;
			} else {
				return Math.min(segmentLeft, segmentRight);
			}
		}
	}
}

누적합은 앞에서부터 누적해서 더한 값을 뜻한다.

s[i] = a[i]+a[2]+...+a[i]

이 문제는 (a[i]+...+a[j])%m인 (i, j) 쌍의 갯수를 구하는 문제이다.

누적합을 구해두고 for문으로 (a[i]+...+a[j])를 구하면 O(N^2)만에 풀 수 있지만,

n<=10^6이고 시간 제한이 1초이므로 다른 방법을 생각해야 한다.

 (a[i]+...+a[j])%m == 0

<=> (s[j]-s[i-1])%m == 0

<=> s[j]%m == s[i-1]%m 와 같으므로

mod[k]: s[i]%m == k인 i의 갯수를 저장한다면

mode[k]C2를 모두 더하면 된다.

주의할 점은 s[i]%m==0인 i는 그 자체로 답이 되므로 바로 ans++해준다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int m=in.nextInt();
		
		int sum=0;
		long mod[]=new long[m];
		long ans=0;
		
		for(int i=0;i<n;i++) {
			int input=in.nextInt();
			sum+=input;
			sum%=m;
			mod[sum]++;
			
			if(sum==0) {
				ans++;
			}
		}
		
		for(int i=0;i<m;i++) {
			long value = mod[i];
			long combination = value*(value-1)/Long.valueOf(2);
			ans+=combination;
		}
		System.out.println(ans);
	}
}

구하려고 하는 구간의 크기가 L로 결정되어 있을 때, 

모든 크기 L인 구간의 최솟값을 구하는 것이 sliding window 문제이다.

(세그먼트 트리나 다이나믹 프로그래밍 등으로도 풀 수 있다)

이 문제를 풀기 위해서는 덱을 이용해서 푸는데, 덱에 값과 인덱스를 저장한다.

덱에는 최대 L개의 값을 저장하고, 덱에 들어있는 값은 항상 증가하는 순서대로 저장한다.

• 덱은 값이 증가하는 순서로 저장되어 있다 --> 가장 처음 값이 최소값이다.
• 가장 처음 값의 인덱스와 현재 값의 인덱스의 차이가 L보다 큰지 작은지 검사한다.
• 가장 마지막 값이 현재 값보다 큰지 작은지 검사한다.
  • 덱의 마지막 값이 현재 값보다 크면 덱에서 제거하고 현재 값을 넣는다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int l=Integer.parseInt(st.nextToken());
		int arr[]=new int[n];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		Deque<Node> deque=new ArrayDeque<Node>();
		for(int i=0;i<n;i++) {
			int currentValue=arr[i];
			
			if(!deque.isEmpty() && deque.getFirst().index <=i-l) {
				// 최솟값이 될 수 없는 경우: 인덱스 차이가 넘 크다
				deque.pollFirst();
			}
			
			while(!deque.isEmpty() && deque.getLast().value>currentValue) {
				// 최솟값이 될 수 없는 경우: 값이 넘 크다
				deque.pollLast();
			}
			
			deque.offer(new Node(currentValue, i));
			arr[i] = deque.getFirst().value;
		}
		
		for(int i=0;i<n;i++) {
			bw.write(arr[i] + " ");
		}
		
		bw.flush();
		bw.close();
	}
}
class Node{
	int value;
	int index;
	
	public Node(int value, int index) {
		this.value=value;
		this.index=index;
	}
}

2020/07/15 - [알고리즘 공부] - boj 11437: LCA

두 정점간의 거리는 LCA를 사용해서 구할 수 있다.

먼저 LCA를 구한 뒤, LCA까지의 거리를 모두 더하면 된다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		int[] depth = new int[n + 1];
		int[] parentNode = new int[n + 1];
		int[] distances = new int[n + 1];
		boolean[] isVisited = new boolean[n + 1];
		LinkedList<Node> pair[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			pair[i] = new LinkedList<Node>();
		}

		for (int i = 1; i < n; i++) {
			int node1 = in.nextInt();
			int node2 = in.nextInt();
			int distance = in.nextInt();
			pair[node1].add(new Node(node2, distance));
			pair[node2].add(new Node(node1, distance));
		}

		depth = calculateNodeDepth(pair, parentNode, distances, n);

		int test = in.nextInt();

		for (int t = 0; t < test; t++) {

			int node1 = in.nextInt();
			int node2 = in.nextInt();

			int depth1 = depth[node1];
			int depth2 = depth[node2];
			int distance = 0;

			if (depth1 < depth2) {
				int tmp = node1;
				node1 = node2;
				node2 = tmp;

				depth1 = depth[node1];
				depth2 = depth[node2];
			}

			distance = calculateLCA(parentNode, depth, distances, node1, node2);
			System.out.println(distance);
		}
	}

	public static int calculateLCA(int parent[], int depth[], int distance[], int node1, int node2) {

		int depth1 = depth[node1];
		int depth2 = depth[node2];
		int ans = 0;

		while (depth1 > depth2) {
			ans += distance[node1];
			node1 = parent[node1];
			depth1 = depth[node1];
		}

		while (node1 != node2) {
			ans += distance[node1];
			ans += distance[node2];
			node1 = parent[node1];
			node2 = parent[node2];
		}
		
		return ans;
	}

	public static int[] calculateNodeDepth(LinkedList<Node> pair[], int parent[], int distance[], int n) {
		Queue<Node> queue = new LinkedList<Node>();
		int depth[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];

		queue.add(new Node(1, 0));
		depth[1] = 0;
		isVisited[1] = true;

		while (!queue.isEmpty()) {

			Node node = queue.poll();

			for (Node i : pair[node.name]) {
				if (!isVisited[i.name]) {
					queue.add(i);
					depth[i.name] = depth[node.name] + 1;
					parent[i.name] = node.name;
					distance[i.name] = i.distance;
					isVisited[i.name] = true;
				}
			}
		}
		return depth;
	}
}

class Node {
	int name;
	int distance;

	public Node(int name, int distance) {
		this.name = name;
		this.distance = distance;
	}
}

LCA: Lowest common Ancestor

두 노드의 가장 가까운 공통 조상을 찾는 문제이다.

LCA를 찾기 위해서는 두 노드의 level과 부모를 알아야한다.

따라서

• 두 노드의 레벨이 다르면, 레벨이 같을 때까지 레벨이 큰 것을 한 칸씩 위로 올린다.
• 두 노드의 레벨이 같아지면, 같은 노드가 될 때까지 한 칸씩 위로 올린다.

인접 행렬을 사용하면 메모리 초과가 생기고,

Queue에 pair을 저장하면 나중에 bfs를 돌 때 시간 초과가 생기므로

LinkedList의 배열에  pair을 저장하고 바로 꺼내 쓸 수 있도록 한다.

이 문제의 주의할 점은 입력 시 어떤 노드가 parent이고 어떤 노드가 child인지 알 수 없으므로

bfs을 돌 때 parent와 child를 정의할 수 있다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		int[] depth = new int[n + 1];
		int[] parentNode = new int[n + 1];
		boolean[] isVisited = new boolean[n + 1];
		LinkedList<Integer> pair[] = new LinkedList[n + 1];
		for (int i = 1; i <= n; i++) {
			pair[i] = new LinkedList<Integer>();
		}

		for (int i = 1; i < n; i++) {
			int node1 = in.nextInt();
			int node2 = in.nextInt();
			pair[node1].add(node2);
			pair[node2].add(node1);
		}

		depth = calculateNodeDepth(pair, parentNode, n);

		int test = in.nextInt();
		int ans = 1;
		for (int t = 0; t < test; t++) {

			int node1 = in.nextInt();
			int node2 = in.nextInt();

			int depth1 = depth[node1];
			int depth2 = depth[node2];

			if (depth1 < depth2) {
				ans = calculateLCA(parentNode, depth, node2, node1);
			} else{
            	ans = calculateLCA(parentNode, depth, node1, node2);
            }
			System.out.println(ans);
		}
	}

	public static int calculateLCA(int parent[], int depth[], int node1, int node2) {

		int depth1 = depth[node1];
		int depth2 = depth[node2];
		int ans = 1;

		while (depth1 > depth2) {
			node1 = parent[node1];
			depth1 = depth[node1];
		}

		while (node1 != node2) {
			node1 = parent[node1];
			node2 = parent[node2];
		}

		ans = node1;
		return ans;
	}

	public static int[] calculateNodeDepth(LinkedList<Integer> pair[], int parent[], int n) {
		Queue<Integer> queue = new LinkedList<Integer>();
		int depth[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];

		queue.add(1);
		depth[1] = 0;
		isVisited[1] = true;

		while (!queue.isEmpty()) {

			int node = queue.poll();

			for (int i : pair[node]) {
				if (!isVisited[i]) {
					queue.add(i);
					depth[i] = depth[node] + 1;
					parent[i] = node;
					isVisited[i] = true;
				}
			}
		}
		return depth;
	}
}

2020/07/13 - [알고리즘 공부] - boj 1208: 부분집합의 합2

위 문제와 완전 동일한 방법으로 풀면 됨

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int t=in.nextInt();
		int n=in.nextInt();
		int A[]=new int[n];
		for(int i=0;i<n;i++) {
			A[i]=in.nextInt();
		}
		int m=in.nextInt();
		int B[]=new int[m];
		for(int i=0;i<m;i++) {
			B[i]=in.nextInt();
		}
		
		
		ArrayList<Integer> left=new ArrayList<Integer>();
		for(int i=0;i<A.length;i++) {
			int sum=0;
			for(int j=i;j<A.length;j++) {
				sum+=A[j];
				left.add(sum);
			}
		}
		ArrayList<Integer> right=new ArrayList<Integer>();
		for(int i=0;i<B.length;i++) {
			int sum=0;
			for(int j=i;j<B.length;j++) {
				sum+=B[j];
				right.add(sum);
			}
		}
		
		long ans=0;
		Collections.sort(left);
		Collections.sort(right);
		int leftIndex = 0;
		int rightIndex = right.size() - 1;
		while (leftIndex < left.size() && rightIndex >= 0) {
			int leftSum = left.get(leftIndex);
			int rightSum = right.get(rightIndex);

			if (leftSum + rightSum == t) {
				long leftSame = 0;
				while (leftIndex < left.size() && left.get(leftIndex) == leftSum) {
					leftIndex++;
					leftSame++;
				}
				long rightSame = 0;
				while (rightIndex >= 0 && right.get(rightIndex) == rightSum) {
					rightIndex--;
					rightSame++;
				}
				ans += leftSame * rightSame;
			} else if (leftSum + rightSum < t) {
				leftIndex++;
			} else {
				rightIndex--;
			}
		}
		System.out.println(ans);
	}
	
}

앞선 글들과 마찬가지 방법으로 풀었는데 12%에서 시간 초과가 나서

아래와 같이 바이너리 서치 방법으로 풀었는데 75% 대에서 다시 시간초과가 났다.

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

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = in.nextInt();
		int m = in.nextInt();
		int n = in.nextInt();
		int A[] = new int[m];
		int B[] = new int[n];

		int aSum = 0;
		for (int i = 0; i < m; i++) {
			A[i] = in.nextInt();
			aSum += A[i];
		}
		int bSum = 0;
		for (int i = 0; i < n; i++) {
			B[i] = in.nextInt();
			bSum += B[i];
		}

		ArrayList<Integer> aPizza = new ArrayList<Integer>();
		ArrayList<Integer> bPizza = new ArrayList<Integer>();

		findAllSums(A, aPizza);
		findAllSums(B, bPizza);
		aPizza.add(aSum);
		bPizza.add(bSum);

		Collections.sort(aPizza);
		Collections.sort(bPizza);

		long ans = 0;
		for (int sum : aPizza) {
			int cnt = binarySearch(bPizza, size - sum);

			if (cnt != -1) {
				ans += cnt;
			}
		}

		System.out.println(ans);
	}

	public static int binarySearch(ArrayList<Integer> list, int target) {
		int left = 0;
		int right = list.size() - 1;
		int mid = (left + right) / 2;
		while (left <= right) {
			mid = (left + right) / 2;

			if (target == list.get(mid)) {
				break;
			} else if (target < list.get(mid)) {
				right = mid - 1;
			} else {
				left = mid + 1;
			}
		}

		if (target == list.get(mid)) {
			int ans = 1;
			int index = mid - 1;
			while (index >= 0) {
				if (target == list.get(index)) {
					ans++;
				} else {
					break;
				}
				index--;
			}
			index = mid + 1;
			while (index < list.size()) {
				if (target == list.get(index)) {
					ans++;
				} else {
					break;
				}
				index++;
			}
			return ans;
		}

		return -1;
	}

	public static void findAllSums(int arr[], ArrayList<Integer> list) {
		int length = arr.length;
		
		for (int i = 0; i < length; i++) {
			int sum = 0;
			int index = i;
			while (true) {
				sum += arr[index % length];
				list.add(sum);
				index++;

				if (index - i + 1 == length) {
					break;
				}
			}
		}
		list.add(0);

		return;
	}
}

LinkedList에서의 데이터의 삽입, 삭제 시에는 ArrayList와 비교해 굉장히 빠른데,

LinkedList는 이전 노드와 다음 노드를 참조하는 상태만 변경하면 되기 때문이다.

삽입, 삭제가 일어날 때 O(1)의 시작 복잡도를 가진다.

반면 ArrayList의 경우 삽입, 삭제 이후 다른 데이터를 복사해야 하기 때문에 최악의 경우 O(N) 의 성능을 내게 된다.

그래서 LinkedList로 바꿨는데 그래도 시간초과는 똑같음

이진 탐색에서 시간이 걸리는 것 같아서 HashMap에 나올 수 있는 피자의 넓이를 넣어놓고 바로 가져올 수 있도록 바꿨다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = in.nextInt();
		int m = in.nextInt();
		int n = in.nextInt();
		int A[] = new int[m];
		int B[] = new int[n];

		int aSum = 0;
		for (int i = 0; i < m; i++) {
			A[i] = in.nextInt();
			aSum += A[i];
		}
		int bSum = 0;
		for (int i = 0; i < n; i++) {
			B[i] = in.nextInt();
			bSum += B[i];
		}

		HashMap<Integer, Integer> aPizza = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> bPizza = new HashMap<Integer, Integer>();

		findAllSums(A, aPizza);
		findAllSums(B, bPizza);

		aPizza.put(aSum, 1);
		bPizza.put(bSum, 1);
		aPizza.put(0, 1);
		bPizza.put(0, 1);

		long ans = 0;

		for (int sum : aPizza.keySet()) {
			int cnt = bPizza.getOrDefault(size - sum, -1);
			if (cnt != -1) {
				ans += cnt * aPizza.get(sum);
			}
		}

		System.out.println(ans);
	}

	public static void findAllSums(int arr[], HashMap<Integer, Integer> list) {
		int length = arr.length;

		for (int i = 0; i < length; i++) {
			int sum = 0;
			int index = i;
			while (true) {
				sum += arr[index % length];
				list.putIfAbsent(sum, 0);
				list.replace(sum, list.get(sum) + 1);
				index++;

				if (index - i + 1 >= length) {
					break;
				}
			}
		}
		return;
	}
}

2020/07/13 - [알고리즘 공부] - boj 1208: 부분집합의 합2

위 글과 마찬가지 방법으로 풀면 된다.

크기 N이 주어졌을 때, 배열 A, B, C, D가 주어지면

A[a]+B[b]+C[c]+D[d]==0인 a, b, c, d의 쌍을 구하는 문제이다.

4중 for문을 돌리면 O(N^4)만에 풀 수 있지만,

A[a]+B[b]와 C[c]+D[d]를 순차적으로 구한 뒤 합이 0인지 찾는다면 O(N^2)만에 풀 수 있다.

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

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		long A[] = new long[n];
		long B[] = new long[n];
		long C[] = new long[n];
		long D[] = new long[n];
		for (int i = 0; i < n; i++) {
			A[i] = in.nextLong();
			B[i] = in.nextLong();
			C[i] = in.nextLong();
			D[i] = in.nextLong();
		}

		long left[] = new long[n * n];
		long right[] = new long[n * n];
		int index = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				left[index] = A[i] + B[j];
				right[index] = C[i] + D[j];
				index++;
			}
		}

		Arrays.sort(left);
		Arrays.sort(right);

		long ans = 0;
		int leftIndex = 0;
		int rightIndex = n * n - 1;
		while (leftIndex < n * n && rightIndex >= 0) {
			long leftSum = left[leftIndex];
			long rightSum = right[rightIndex];
			if (leftSum + rightSum == 0) {
				long leftSame = 0;
				long rightSame = 0;
				while (leftIndex < n * n && leftSum == left[leftIndex]) {
					leftIndex++;
					leftSame++;
				}
				while (rightIndex >= 0 && rightSum == right[rightIndex]) {
					rightIndex--;
					rightSame++;
				}
				ans += leftSame * rightSame;
			} else if (leftSum + rightSum > 0) {
				rightIndex--;
			} else {
				leftIndex++;
			}
		}
		System.out.println(ans);
	}
}