알고리즘 스터디 - 2주차

'22. 2. 4. 알고리즘 스터디 내용 및 회고

주제

1. Union-Find
2. Segment Tree

Union Find (백준 1939번 : https://www.acmicpc.net/problem/1939)

저번 알고리즘 스터디 1주차를 진행하면서 Union find에 대한 문제를 추천받았다. 문제 파악을 했을 때, 두 가지 풀이법이 있었음.

1. 이분 탐색을 활용하여 이를 BFS를 통해 알아내는 방법

-> 보통 10억이라는 숫자가 문제에서 주어지면 이분탐색이며, 이분 탐색($log_2(1,000,000,000)$)을 이용하여 해결법을 찾은 뒤 BFS($log(|N + M|)$)로 해결가능.
-> 이 때 메모리 초과를 해결하기 위해 인접리스트 방식을 사용해야 함.(참고 https://gwanhyeon.github.io/Algorithm-20201021-Algorithm-graph-summary/)

2. Greedy 기법을 활용한 Union-find를 사용하여 알아내는 방법

총 두 가지가 있음을 파악하였음.(사실 2번 방법은 Union-find 문제라고 이미 스포를 당해서 알아냈음..)
-> 출발점에서 도착점까지 얼마나 큰 짐을 옮길 수 있는지를 알아보는 것이므로 먼저 간선을 w 기준 내림차순으로 정렬한다.
-> 간선을 하나씩 추가한 뒤, union-find를 통해 출발점과 도착점이 연결되었는지 확인한다.
-> 연결 되었을 경우, 저장된 w를 리턴.

코드

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

public class Main {
	public static int stoi(String s) {return Integer.parseInt(s);}
	public static class Edge implements Comparable<Edge>{
		int s, e, v;

		Edge(int s, int e, int v) {
			this.s = s;
			this.e = e;
			this.v = v;
		}

		@Override
		public int compareTo(Edge o) {
			return o.v - this.v;
		}
	}
	public static int[] parent;
	public static final int INF = 1_000_000_000;
	public static int answer = INF;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = stoi(st.nextToken());
		int M = stoi(st.nextToken());
		Edge[] edge = new Edge[M];
		parent = new int[N + 1];

		for(int i = 0; i <= N; i++) parent[i] = i; 

		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
	
			int s = stoi(st.nextToken());
			int e = stoi(st.nextToken());
			int v = stoi(st.nextToken());
	
			edge[i] = new Edge(s, e, v);
		}

		Arrays.sort(edge);
		st = new StringTokenizer(br.readLine());
		int s = stoi(st.nextToken());
		int e = stoi(st.nextToken());

		for(int i = 0; i < M; i++) {
			answer = edge[i].v;
			union(edge[i].s, edge[i].e);
	
			if(find(s) == find(e)) break;
		}

		System.out.println(answer);
	}

	public static void union(int a, int b) {
		a = find(a);
		b = find(b);

		if(a > b) {
			parent[a] = b;
		}
		else {
			parent[b] = a;
		}
	}

	public static int find(int n) {
		if(n == parent[n]) return n;
		else return parent[n] = find(parent[n]);
	}
}

Segment Tree(참고 : https://hyeonseong.tistory.com/3)

Segment tree 구조를 자바로 구현하였음.

코드

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

public class Main {
	public static int stoi(String s) {return Integer.parseInt(s);}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = stoi(br.readLine());
		int[] arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < arr.length; i++) {
			arr[i] = stoi(st.nextToken());
		}
		
		Tree tree = new Tree(n, arr);
		
		System.out.println(tree.sum(0, n - 1, 1, 2, 4));
	}
	
	public static class Tree {
		int arr[];
		int tree[];
		
		public Tree(int n, int[] arr) {
			this.arr = new int[n];
			tree = new int[n * 4];
			
			for(int i = 0; i < arr.length; i++) {
				this.arr[i] = arr[i];
			}
			init(0, n - 1, 1);
		}
		
		public int init(int start, int end, int node) {
			if(start == end) return tree[node] = arr[start];
			
			int mid = (start + end) / 2;
			return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
		}
		
		public int sum(int start, int end, int node, int left, int right) {
			if(left > end || right < start) {
				return 0;
			}
			if(left <= start && end <= right) {
				return tree[node];
			}
			
			int mid = (start + end) / 2;
			return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
		}
		
		public void update(int start, int end, int node, int index, int dif) {
			if(index < start || index > end) return;
			
			tree[node] += dif;
			if(start == end) return;
			
			int mid = (start + end) / 2;
			
			update(start, mid, node * 2, index, dif);
			update(mid + 1, end, node * 2 + 1, index, dif);
		}
		
		public void print() {
			for(int i = 0; i < tree.length; i++) {
				System.out.println(i + " : " + tree[i]);
			}
		}
	}
}