공부 기록

이 문제는 2차원에서의 누적 합을 구하는 문제이다.

sum[i][j]: (1, 1) ~ (i, j)까지의 합이라고 할 때,

sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j]와 같다

마지막으로 (x1, y1) ~ (x2, y2)의 값은 s[x2][y2] - s[x2][y-1] - s[x1-1][y2] + s[x1-1][y1-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][n + 1];
		int sum[][] = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				arr[i][j] = in.nextInt();
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
			}
		}

		for (int i = 0; i < m; i++) {
			int x1 = in.nextInt();
			int y1 = in.nextInt();
			int x2 = in.nextInt();
			int y2 = in.nextInt();

			int ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
			System.out.println(ans);
		}
	}
}

스패닝 트리: 그래프에서 일부 간선을 선택해서 만든 트리

최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치 합이 최소인 트리

스패닝 트리를 구하는 알고리즘

• Prim: 정점을 점점 확장해 나가는 방식 (힙을 써서 구현 - 정점번호, 가중치 저장) --> 최소값을 우선 순위 큐를 이용하면 최소 값을 logE만에 찾을 수 있다. 이 경우 시간복잡도는 O(ElogE)가 된다. 모든 간선이 힙에 한번 씩 들어갔다가 나오기 때문
  1. 그래프에서 아무 정점이나 선택한다.
  2. 선택한 정점과 선택하지 않은 정점을 연결하는 간선 중에 최소값을 고른다. 이 간선을 (u, v)라고 한다.
  3. 선택한 간선을 최소 스패닝 트리에 추가하고, 선택하지 않았던 정점 v를 선택한다.
  4. 2번으로 돌아간다

• Kruskal: 간선을 점점 확장해 나가는 방법
  1. 가중치가 작은 edge부터 살펴본다 --> 간선의 길이 순으로 먼저 정렬해야 한다. O(ElogE)
  2. edge e가 (u, v, c)일 때,  u와 v가 서로 다른 집합이면 e를 최소 스패닝 트리에 추가한다. O(E) - union/find 연산

Prim 알고리즘 풀이

import java.util.*;

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

		LinkedList<Edge>[] pair = new LinkedList[v + 1];
		HashSet<Integer> vSet = new HashSet<Integer>();
		for (int i = 1; i <= v; i++) {
			pair[i] = new LinkedList<Edge>();
			vSet.add(i);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long cost = in.nextLong();

			pair[start].add(new Edge(end, cost));
			pair[end].add(new Edge(start, cost));
		}

		int currentNode = 1;
		long ans = 0;
		vSet.remove(1);

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		pq.addAll(pair[currentNode]);

		while (!vSet.isEmpty()) {
			Edge minEdge = pq.poll();

			if (vSet.contains(minEdge.v)) {
				ans += minEdge.cost;
				currentNode = minEdge.v;
				vSet.remove(currentNode);
				pq.addAll(pair[currentNode]);
			}
		}
		System.out.println(ans);
	}
}

class Edge implements Comparable<Edge> {
	int v;
	long cost;

	public Edge(int v, long cost) {
		this.v = v;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

Kruskal 알고리즘 풀이

import java.util.*;

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

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		int vSet[] = new int[v + 1];

		for (int i = 1; i <= v; i++) {
			vSet[i] = i;
		}

		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long cost = in.nextLong();

			pq.add(new Edge(start, end, cost));
		}

		long ans = 0;
		if (!pq.isEmpty()) {
			Edge firstEdge = pq.poll();
			ans += firstEdge.cost;
			union(firstEdge.v1, firstEdge.v2, vSet);
		}

		while (!isFinished(vSet) && !pq.isEmpty()) {
			Edge minEdge = pq.poll();

			int v1Contains = find(minEdge.v1, vSet);
			int v2Contains = find(minEdge.v2, vSet);

			if (v1Contains != v2Contains) {
				ans += minEdge.cost;
				union(minEdge.v1, minEdge.v2, vSet);
			}
		}
		System.out.println(ans);
	}

	public static void union(int x, int y, int[] vSet) {
		int ux = find(x, vSet);
		int uy = find(y, vSet);

		vSet[uy] = ux;
	}

	public static int find(int x, int[] vSet) {
		if (vSet[x] == x) {
			return x;
		}

		vSet[x] = find(vSet[x], vSet);
		return vSet[x];
	}

	public static boolean isFinished(int[] vSet) {
		int now = vSet[1];
		for (int i = 1; i < vSet.length; i++) {
			if (vSet[i] != now) {
				return false;
			}
		}
		return true;
	}
}

class Edge implements Comparable<Edge> {
	int v1, v2;
	long cost;

	public Edge(int v1, int v2, long cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

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

• 각 노드에 저장되는 값은 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);
	}
	
}