uk's study

# 유형 : 벨만포드

# 벨만포드 알고리즘을 알고 있다면 쉽게 해결이 가능하다. 중복되는 글이지만 https://ukyonge.tistory.com/26를 읽어 보는것도 추천한다.

# 주석 달아놓았음

벨만 포드 알고리즘은, 다익스트라에서 할 수 없었던 음의 가중치도 계산 할 수 있도록 한 방식이다. 하지만 모든 정점에서 모든 간선을 다 봐야하기 때문에 시간 복잡도가 더 높다. 필요에 맞게 잘 사용하는 것이 중요.

벨만 포드 알고리즘에 대한 전제 조건

•  최단 경로는 사이클을 포함할 수 없다. 따라서 최대 |V|-1개의 간선만 사용할 수 있다. 
• 최단 거리가 업데이트 되는 노드가 없어질 때 까지 계속해서 반복하여 구해준다. 이때 만약 음의 값을 가지고 있는 간선으로 인해 업데이트를 무한히 하게 되는 경우 탈출 시켜주어야 한다.(무한히 반복할 때는 최단거리가 없다고 한다.) 

이를 위해 백준에 있는 https://www.acmicpc.net/problem/11657 문제를 풀어 보는 것이 좋다. 꼭 풀어 보는 것을 추천한다.

처음 반복문을 돌려 최소 거리를 구하여 dist 배열을 갱신한다. 그 후에는 음의 값을 가지고 있는 간선으로 인해 싸이클이 형성되는 케이스를 체크해주어 해결하면 된다.

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

public class bellmanford {
	static int INF = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		Edge e[] = new Edge[M];
		
		int dist[] = new int[N+1];
		for(int i=1; i<=N; i++)
			dist[i] = INF;
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int val = Integer.parseInt(st.nextToken());
			
			e[i] = new Edge(u,v,val);
		}
		
		dist[1] = 0;
		
		for(int i=0; i<N-1; i++) {
			for(int j=0; j<M; j++) {
				if(dist[e[j].u] == INF) 
					continue;
				if(dist[e[j].v] > (dist[e[j].u] + e[j].val)) {
					dist[e[j].v] = dist[e[j].u] + e[j].val;
				}
			}
		}
		
		boolean check = false;
		
		for(int i=0; i<M; i++) {
			if(dist[e[i].u] == INF)
				continue;
			if(dist[e[i].v] > dist[e[i].u] + e[i].val) {
				check = true;
				break;
			}
		}
		
		if(check)
			System.out.println(-1);
		else {
			for(int i=2; i<=N; i++) {
				if(dist[i] == INF)
					System.out.println("-1");
				else
					System.out.println(dist[i]);
			}
		}
		
	}
	
	public static class Edge{
		int u;
		int v;
		int val;
		public Edge(int u,int v, int val) {
			this.u = u;
			this.v = v;
			this.val = val;
		}
	}
}

# 분류 : 이진 탐색

# 최대 랜선 길이를 찾는 것이므로, count가 조건과 같다고 return 하여 문제를 접근하였으나 틀렸고 Count를 맞춰도 최대 길이를 찾아야 하기 때문에 추가적으로 left = Middle + 1 로 주어 진행하여야 한다. 단위가 크므로 long 타입을 쓰지 않으면 틀림

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int K = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		
		int arr[] = new int[K];
		
		
		for(int i=0; i<K; i++)
			arr[i] = Integer.parseInt(br.readLine());
		
		Arrays.sort(arr);
		
		long left = 1;
		long right = arr[K-1];
		long middle=0;
		
		while(left<=right) {
			
			long cnt=0;
			
			middle = (left+right)/2;
			
			for(int i=0; i<K; i++) {
				cnt+= arr[i]/middle;
			}
			
			if(cnt < N) {
				right = middle-1;
			}else if(cnt >= N) {
				left = middle+1;
			}
		}
		System.out.println(right);
		
	}
}

# 분류 : 이진 탐색

# 정답률이 낮은데에 비해 쉽게 해결할 수 있던 문제, 어떠한 길이로 나무를 자를 때 음수가 되는 것만 주의하면 쉽게 해결

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		long M = Long.parseLong(st.nextToken());
		
		long arr[] = new long[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Long.parseLong(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		long left = 0;
		long right = 2000000000;
		
		while(left<=right) {
			long middle = (left+right)/2;
			
			long sum=0;
			for(int i=0; i<N; i++) {
				if((arr[i]-middle)<0) {
					sum+=0;
				}else
					sum+=arr[i]-middle;
			}
			if(sum < M) {
				right = middle-1;
			}else if(sum>=M)
				left = middle+1;
		}
		System.out.println(right);
	}
}

# https://ukyonge.tistory.com/21 문제와 같이 분할 정복 문제로써 행렬을 나누어 진행하면 됨 

https://ukyonge.tistory.com/21에서는 9개로 분할하였지만, 이 문제에서는 4개로 분할하여 해결

package bj;

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

public class p1992 {
	static int arr[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		arr = new int[N][N];
		
		StringTokenizer st;
		for(int i=0; i<N; i++) {
			String str = br.readLine();
			for(int j=0; j<N; j++) {
				arr[i][j] = (str.charAt(j)-'0');
			}
		}
		solve(N,0,0);
		
		
	}
	
	public static void solve(int n, int x, int y) {
		if(n==1) {
			System.out.print(arr[y][x]);
			return;
		}
		
		if(check(n, x, y)) {
			System.out.print(arr[y][x]);
		}else {
			int div = n/2;
			System.out.print('(');
			solve(div, x, y);
			solve(div, x+div, y);
			solve(div, x, y+div);
			solve(div, x+div, y+div);
			System.out.print(')');
		}
	}
	
	public static boolean check(int n, int x, int y) {
		
		int val = arr[y][x];
		
		boolean rs=true;
		
		for(int i=y; i<y+n; i++) {
			for(int j=x; j<x+n; j++) {
				if(val != arr[i][j]) {
					rs = false;
					return rs;
				}
			}
		}
		
		return rs;
	}
}

# 하노이탑 알고리즘만 알면 바로 풀 수 있던 문제. 그러나 출력문이 많아 System.out.print를 사용하면 시간 초과 발생하니 유의할것

package bj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class p11729 {
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		System.out.println((int)Math.pow(2, N)-1);
		hanoi(N,1,2,3);
		bw.close();
	}
	
	public static void hanoi(int N, int a, int b, int c) throws IOException {
		if(N>0) {
			hanoi(N-1, a, c, b);
			bw.write(a+" "+c+"\n");
			hanoi(N-1, b, a, c);
		}
	}
}

# 행렬을 분할하여 함수를 짜면 쉽게 해결할 수 있는 문제, 편리하게 진행하기 위해 check 함수로 분할 여부 체크

package bj;

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

public class p1780 {
	static int arr[][];
	static int result[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		result = new int[3];
		StringTokenizer st;
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		//종이가 모두 같은 수로 되어 있는지 체크
		solve(N,0,0);
		for(int i:result)
			System.out.println(i);
	}
	
	public static void solve(int n,int x, int y) {
		if(n==1) {
			int val = arr[y][x]+1;
			result[val]++;
			return;
		}
		
		if(check(n, x ,y)) {
			int val = arr[y][x]+1;
			result[val]++;
		}else {
			int next = n/3;
			
			solve(next, x, y);
			solve(next, x + next, y);
			solve(next, x + 2*next, y);
			
			solve(next, x, y + next);
			solve(next, x + next, y+next);
			solve(next, x + 2*next, y+next);
			
			solve(next, x, y + 2 * next);
			solve(next, x + next, y + 2 * next);
			solve(next, x + 2 * next, y + 2 * next);
			
		}
	}
	
	public static boolean check(int n, int x, int y) {
		int val = arr[y][x];
		boolean rs = true;
		for(int i=y; i<y+n; i++) {
			for(int j=x; j<x+n; j++) {
				if(val != arr[i][j]) {
					rs = false;
					return rs;
				}
			}
		}
		return rs;
	}
}

# 처음에는 병합 정렬로 접근하였음. 출력에 있어 System.out.print는 당연히 시간 초과, Stringbuilder, BufferWriter를 사용했는데도 시간 초과가 떠서 그냥 PriorityQueue를 사용하여 해결하였다.

질문 검색에 들어가서 확인도 해봤는데 자바에는 시간리미트를 수정해줘야 할거 같다. 어디에서 봤는데 Arrays.Sort로도 성공한 사람이 있다고 하였음.

< 정답 코드 >

package bj;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class p11728 {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		PriorityQueue pq = new PriorityQueue<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens())
			pq.offer(Integer.parseInt(st.nextToken()));
		
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens())
			pq.offer(Integer.parseInt(st.nextToken()));
		
		while(!pq.isEmpty())
			bw.write(pq.poll()+" ");
		
		bw.close();
	}
}

병합 정렬 코드도 첨부는 하지만, 통과는 못한 코드입니다. 틀린게 보이신다면 조언 부탁드립니다.

package bj;

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

public class p11728_timeout {
	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 = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int arr[] = new int[N+M];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=N; i<M+N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		mergeSort(arr, 0, M+N-1);
//		StringBuilder sb = new StringBuilder();
		for(int i=0; i<M+N; i++) {
			bw.write(arr[i]+" ");
//			sb.append(arr[i]+" ");
		}
		bw.flush();
		
	}
	public static void mergeSort(int arr[], int m ,int n) {
		if(m<n) {
			int middle = (m+n)/2;
			mergeSort(arr, m, middle);
			mergeSort(arr, middle+1, n);
			merge(arr,m, middle, n);
		}
	}
	
	public static void merge(int arr[], int m, int middle, int n) {
		int i = m;
		int j = middle+1;
		int t=1;
		int tmp[] = new int[arr.length+1];
		
		while(i<=middle && j<=n) {
			if(arr[i] < arr[j]) {
				tmp[t++] = arr[i++];
			}else {
				tmp[t++] = arr[j++];
			}
		}
		
		while(i<=middle) {
			tmp[t++] = arr[i++];
		}
		while(j<=n)
			tmp[t++] = arr[j++];
		
		i = m;
		t = 1;
		
		while(i <= n)
			arr[i++] = tmp[t++];
	}
}