본문 바로가기
공부기록/알고리즘

[알고리즘] 7-8일차

쇼파죠하 2024. 2. 22. 10:52

 

이것도 마찬가지로 일단 코드만 올려놨는데

 

내가 나중에 내 힘으로 어떠한 도움 없이 이 코드들을 다 쓸 수 있을 때 하나하나 정리해나가야지

 

 

package day08.P11049;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	final static int MAX = 1 << 31 - 1 ;
	static int N;
	static int[] r,c;
	static int[][] d; // d(i,j) : i~j 까지 행렬곱의 최소연산횟수
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(br.readLine());
		
		r = new int[N+1];
		c = new int[N+1];
		d = new int[N+1][N+1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			r[i] = Integer.parseInt(st.nextToken());
			c[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(mem(1,N));
		print(d);
	}
	
	
	static int mem(int i, int j) {
		int ret = 0;
		if(i==j) return 0;
		if(ret == 0) {
			ret = MAX;
			for (int k = i; k < j; k++) {
				ret = Math.min(mem(i,k) + mem(k+1, j) + r[i]*c[k]*c[j], ret);
			}
		}
		return d[i][j] = ret;
	}
	
	public static void print(int[][] mx) {
        System.out.println("### MATRIX ###");
        for (int i=0; i<mx.length; i++) {
            for (int j=0; j<mx[0].length; j++) {
                System.out.print(" "+mx[i][j]);
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
}

P1915 가장 큰 정사각형

 

package day08.P1915;

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

public class Main {
	static int N,M;
	static int[][] a;
	static int[][] d; // i,j까지 정사각형 최대크기(변의 길이)
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		a = new int[N+1][M+1];
		d = new int[N+1][M+1];
		
		int ans = 0;
		String[] s;
		for (int i = 1; i <= N; i++) {
			s = br.readLine().split("");
			for (int j = 1; j <= M; j++) {
				a[i][j] = Integer.parseInt(s[j-1]);
				if(i == 1 || j == 1) {
					d[i][j] = a[i][j];
				}
				else if (a[i][j] == 1) {
					d[i][j] = min(d[i-1][j-1], d[i-1][j], d[i][j-1]) + 1;
					ans = Math.max(ans, d[i][j]);
				}
			}
			
		}
		System.out.println(ans);
	}
	static int min(int a, int b, int c) {
		a = a<b?a:b;
		return a<c?a:c;
	}

}

 

 

P1256 사전

package day08.P1256;

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

public class Main {
	static int[][] d;
	static int N,M,K;
	static String s;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		d = new int[201][201];
		
		for (int i = 0; i <= 200; i++) {
			d[i][0] = 1;
			
		}
		for (int i = 1; i <= 200; i++) {
			for (int j = 1; j <= 200; j++) {
				d[i][j] = d[i-1][j] + d[i-1][j-1];
			}
		}
		s = "";
		
		int t = N+M;
		if(d[t][M] < K) {
			System.out.println("-1");
		} else {
			for (int i = 1; i <= t; i++) {
				if(d[t-i][M] < K) {
					K -= d[t-i][M];
					M--;
					s +="z";
				}else {
					s+="a";
				}
			}
		}
		System.out.println(s);
	}
	
//	static long combi(int n, int k) {
//		if(n==1) return 1;
//		if(k==n) return 1;
//		if(k==0) return 1;
//		if(k==n) return 1;
//		
//	}

}

 

 

p2579 계단 그 뛰는거 최대 총점 DP

 

package day07.P2579;

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

public class Main {
	static int N;
	static int[] a,dp; // i번째 계단까지 밟았을 때 최대 총점
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		a = new int[N+1];
		dp = new int[N+1];
		for (int i = 1; i <= N; i++) {
			a[i] = Integer.parseInt(br.readLine());
			/* 
			 * 점화식 부분 이해 잘 못하겠음
			 * 그리고 이거 직접 문제 만나면 내가 짜는 거 연습 많이 해야할듯
			 */
			if(i == 1) dp[1] = a[1];
			if(i == 2) dp[2] = a[1] + a[2];
			if(i >= 3) dp[i] = Math.max(dp[i-3]+a[i-1] + a[i], dp[i-2] + a[i]);
		}
		System.out.println(dp[N]);
		
		
	}
}

 

 

 

ㅔ1032 정수 삼각형

 

package day07.P1932;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 정수 삼각형
public class Main {

	static int N;
	static int[][] d, dp;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		d = new int[N+1][N+1];
		dp = new int[N+1][N+1];
		for (int i = 0; i <= N; i++) {
			dp[0][i] = 0;
			dp[i][0] = 0;
		}
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<= i; j++) {
				d[i][j] = Integer.parseInt(st.nextToken());	
			
				if (i == 1 && j ==1) {
					dp[1][1] = d[1][1];
				}else {
					if(dp[i-1][j-1] > dp[i-1][j]) {
						dp[i][j] = dp[i-1][j-1] + d[i][j];
					}else {
						dp[i][j] = dp[i-1][j] + d[i][j];
					}
					
				}
			}
			
			
		}
		int sum = dp[N][0];
		for(int i = 1; i<=N; i++) {
			if( sum <= dp[N][i]) {
				sum = dp[N][i];
			}
		}
		System.out.println(sum);
		
	}

}

 

 

P11660 구간합구하기 5

package day07.P11660;

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

// 구간 합 구하기 5
public class Main {

	static int N,M;
	static int[][] d, dp;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		d = new int[N+1][N+1];
		dp = new int[N+1][N+1];
		
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<= N; j++) {
				d[i][j] = Integer.parseInt(st.nextToken());	
			
				if (i == 1 && j ==1) {
					dp[1][1] = d[1][1];
				}else {
					dp[i][j] = dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] + d[i][j];
				}
			}
			
			
		}
		
		
		for (int K = 0; K < M; K++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			int sum = dp[c][d] - dp[c][b-1] -dp[a-1][d] + dp[a-1][b-1];
			System.out.println(sum);
			
		}
		
	}

}

 

 

p11659 구간합구하기4

package day07.P11659;
// 구간 합 구하기 4
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N,M;
	static int[] d, dp;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		d = new int[N+1];
		dp = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			d[i] = Integer.parseInt(st.nextToken());	
			if (i == 1) {
				dp[1] = d[1];
			}else {
				dp[i] = dp[i-1] + d[i];
			}
		}
		
		
		for (int K = 0; K < M; K++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int sum = dp[b] - dp[a-1];
			System.out.println(sum);
			
		}
		
	}

}

 

//////
//int [] d; // 1~i번째까지 누적합
//
//for(int i =1; i<=N; i++) {
//	a[i] = Integer.parseInt(st.nextToken());
//	
//}
//d[1] = a[i];
//for(int i = 2; i<= N; i++) {
//	d[i] = d[i-1] + a[i];
//}
//int ans = d[e] - d[s-1];

 

 

플로이드는 못들었고

 

P1753

 

package day06.P1753;

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

public class Main {
	
	static final int INF = Integer.MAX_VALUE; 
	static int N,M,K;
	
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(br.readLine());
		
		ArrayList<Edge> adj[] = new ArrayList[N+1];
		for (int i = 0; i <= N; i++) {
			adj[i] = new ArrayList<Edge>();
			
		}
		
		int s,e,c;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			adj[s].add(new Edge(e,c));
		}
		
		int dist[] = new int[N+1];
		Arrays.fill(dist, INF);
		
		dist[K] = 0;
		
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		pq.add(new Edge(K,0));
		
		Edge now, next;
		while(!pq.isEmpty()) {
			now = pq.poll();
			
			if(dist[now.e] < now.c) continue;
			
			for (int i = 0; i < adj[now.e].size(); i++) {
				next = adj[now.e].get(i);
				
				if(dist[next.e] > now.c + next.c) {
					dist[next.e] = now.c + next.c;
					pq.add(new Edge(next.e, now.c + next.c));
				}
			}
		}
	
	for(int i = 1; i < dist.length; i++) {
		if(K==i) {
			System.out.println("0");
		}else if (dist[i] == Integer.MAX_VALUE) {
			System.out.println("INF");
		}else {
			System.out.println(dist[i]);
		}
		
	}

	}
}

class Edge implements Comparable<Edge>{	
	int e,c;
	public Edge(int e, int c) {
		this.e = e;
		this.c = c;
	}
	
	@Override
	public int compareTo(Edge o) {
		return this.c < o.c ? -1:1;
	}

}

 

 

P11049

 

package day08.P11049;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	final static int MAX = 1 << 31 - 1 ;
	static int N;
	static int[] r,c;
	static int[][] d; // d(i,j) : i~j 까지 행렬곱의 최소연산횟수
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(br.readLine());
		
		r = new int[N+1];
		c = new int[N+1];
		d = new int[N+1][N+1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			r[i] = Integer.parseInt(st.nextToken());
			c[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(mem(1,N));
		print(d);
	}
	
	
	static int mem(int i, int j) {
		int ret = 0;
		if(i==j) return 0;
		if(ret == 0) {
			ret = MAX;
			for (int k = i; k < j; k++) {
				ret = Math.min(mem(i,k) + mem(k+1, j) + r[i]*c[k]*c[j], ret);
			}
		}
		return d[i][j] = ret;
	}
	
	public static void print(int[][] mx) {
        System.out.println("### MATRIX ###");
        for (int i=0; i<mx.length; i++) {
            for (int j=0; j<mx[0].length; j++) {
                System.out.print(" "+mx[i][j]);
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
}

 

 

package day08.P11049;

import java.util.Scanner;
public class Main_2 {
	final static int MAX = Integer.MAX_VALUE;
	static int N;
	static int[] r,c;
	static int[][] d; // d(i,j) : i~j 까지 행렬곱의 최소연산횟수
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		r = new int[N+1];
		c = new int[N+1];
		d = new int[N+1][N+1];

		for (int i = 1; i <= N; i++) {
			r[i] = sc.nextInt();
			c[i] = sc.nextInt();
		}
		int min;
		for(int i = 1; i<= N; i++) {
			for(int j=1;j< N;j++) {
				int s = j;
				int e = j+1;
				min = MAX;
				for(int k = s+1; k<=e; k++) {
					min = Math.min(min, d[s][k-1]+d[k][e]+r[s]*c[k]*c[e]);
				}
				d[s][e] = min;
			}
		}
		System.out.println(d[1][N]);
	}
	
	
	
}

 

 

p14002

 

package day08.P14002;

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

public class Main {
	static int N;
	static int[] A, d;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		A = new int[N+1];
		d = new int[N+1]; // i번째 수까지 LTS 길이
		st = new StringTokenizer(br.readLine());
		
		for (int i = 1; i <= N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
			//d[i] : i번째 수까지 LTS 길이
		}
		int lis = 0;
		for(int i = 1; i<=N;i++) {
			for(int j=1; j<i;j++) {
				if(A[i] > A[j]) {
					d[i] = Math.max(d[i], d[j] + 1);
					lis = Math.max(d[i], lis);
				}
			}
		}
		System.out.println(lis);
		
		ArrayList<Integer> ret = new ArrayList<Integer>();
		for(int i = N; i>=1; i--) {
			if(d[i] == lis) {
				ret.add(A[i]);
				lis--;
			}
			if(lis < 1) break;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = ret.size() - 1; i >= 0; i--) {
			sb.append(ret.get(i)).append(" ");
		}
		System.out.println(sb.toString());
	}

}

 

 

 

P14003

 

package day08.P14003;
// LIS
// https://shoark7.github.io/programming/algorithm/3-LIS-algorithms
// 응용문제 P2352 반도체 설계

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

public class Main {

	static int N;
	static int[] A, d, idx;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		A = new int[N+1];
		d = new int[N+1]; // i번째 수까지 LTS 길이
		idx = new int[N+1];
		
		st = new StringTokenizer(br.readLine());
		
		for (int i = 1; i <= N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
			//d[i] : i번째 수까지 LTS 길이
		}
		
		d[1] = A[1];
		idx[1] = 1;
		int len = 1;
		for(int i = 2; i<=N;i++) {
			
			if(A[i] > d[len]){
				len++;
				d[len] = A[i];
				idx[i] = len;
			}else {
				int tmp =binarySearch(1,len,A[i]);
				d[tmp] = A[i];
				idx[i] = tmp;
			}
		}
		System.out.println(len);
		
		ArrayList<Integer> ret = new ArrayList<>();
		for(int i = N; i>=1; i--) {
			if(d[i] == len) {
				ret.add(A[i]);
				len--;
			}
			if(len < 1) break;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = ret.size() - 1; i >= 0; i--) {
			sb.append(ret.get(i)).append(" ");
		}
		System.out.println(sb.toString());
		
		
	}
	
	
	
	
	static int binarySearch(int left, int right, int target) {
		while(left < right) {
			int mid = (left+right) /2;
			if(d[mid] < target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return right;
	}

}

 

 

P5582

package day08.P5582;


import java.util.Scanner;

public class Main {
	static int d[][]; // i,j 위치까지 공통부분문자열 길이
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s1 = sc.nextLine();
		String s2 = sc.nextLine();
		
		int M = s1.length();
		int N = s2.length();
		d = new int[M+1][N+1];
		
		int ans = 0;
		for (int i = 1; i <= M; i++) {
			for (int j = 1; j <= N; j++) {
				if(s1.charAt(i-1) == s2.charAt(j-1)) {
					d[i][j] = d[i-1][j-1] + 1;
					ans = Math.max(ans, d[i][j]);
				}
			}
		}
		System.out.println(ans);
		

	}

}

 

P5626

package day08.P5626;

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

public class Main {
	static int N;
	static int A[];
	static int dp[][];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		A = new int[N+1];
		for (int i = 1; i <= N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		dp = new int[N+2][N+2];
		
		for(int i = 1; i<= N; i++) {
			for(int j = 0;j<=N;j++) {
				if(A[1] == -1 || A[1] == 0) dp[1][0] = 1;
				else d[1][0] = 0;
				
				if(A[i] == -1) {
					if(j != 0) {
						dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1];
					}else {
					dp[i][j] = dp[i-1][j+1] + dp[i-1][j];
					}
				}else {
					int k = A[i];
					if(j == k) {
						dp[i][j] = k;
					}else {
						dp[i][j] = 0;
					}
				}
			}
		}
		int ans = dp[N][0];
		System.out.println(ans);
		
	}

}

 

 

P9252

 

package day08.P5626;

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

public class Main {
	static int N;
	static int A[];
	static int dp[][];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		A = new int[N+1];
		for (int i = 1; i <= N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		dp = new int[N+2][N+2];
		
		for(int i = 1; i<= N; i++) {
			for(int j = 0;j<=N;j++) {
				if(A[1] == -1 || A[1] == 0) dp[1][0] = 1;
				else d[1][0] = 0;
				
				if(A[i] == -1) {
					if(j != 0) {
						dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1];
					}else {
					dp[i][j] = dp[i-1][j+1] + dp[i-1][j];
					}
				}else {
					int k = A[i];
					if(j == k) {
						dp[i][j] = k;
					}else {
						dp[i][j] = 0;
					}
				}
			}
		}
		int ans = dp[N][0];
		System.out.println(ans);
		
	}

}

 

 

 

package day08.P9252;

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

public class Main2 {
	static int d[][]; // i,j 위치까지 LCS 최대길이
	static char[] s1, s2;
	static ArrayList<Character> ans;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str1 = br.readLine().trim();
		String str2 = br.readLine().trim();
		int M = str1.length();
		int N = str2.length();
		s1 = new char[M+1];
		s2 = new char[N+1];
		
		for(int i=1; i<= M; i++) s1[i] = str1.charAt(i-1);
		for(int i=1; i<=N; i++) s2[i] = str2.charAt(i-1);
		
		d = new int[M+1][N+1];
		
		for (int i = 1; i <= M; i++) {
			for (int j = 1; j <= N; j++) {
				if(s1[i] == s2[j]) {
					d[i][j] = d[i-1][j-1] + 1;
				}else {
					d[i][j] = Math.max(d[i-1][j],d[i][j-1]);
				}
			}
		}
		
		System.out.println(d[M][N]);
		
		ArrayList<Character> ans = new ArrayList<>();
		getRoute(M,N);
	
		for (int i=ans.size()-1;i>=0;i--) {
			System.out.println(ans.get(i));
		}
		System.out.println("");
	}
	
	
	static void getRoute(int r, int c) {
		if(r==0 || c==0) return;
		
		if(s1[r] == s2[c]) {
			ans.add(s1[r]);
			getRoute(r-1, c-1);
		}else {
			if(d[r-1][c] > d[r][c-1]) getRoute(r-1,c);
			else getRoute(r, c-1);
		}
	
	}
	

}

'공부기록 > 알고리즘' 카테고리의 다른 글

[알고리즘] P1456. 거의 소수  (1) 2024.03.25
[알고리즘] 8-9일차  (0) 2024.02.23
[알고리즘] 6일차  (0) 2024.02.20
[알고리즘] 5일차_그래프  (0) 2024.02.19
[알고리즘] 4일차  (0) 2024.02.16

'공부기록/알고리즘' Related Articles

티스토리툴바