알고리즘 1. 부분집합을 구해 칼로리의 합을 구함. 2. 칼로리의 합이 제시한 칼로리보다 낮은경우 만족도의 합중 최대값을 저장함. 3. DP테이블을 만들어서 풀이할 수 있음. 추후 업로드 예정 import java.util.Scanner; public class Solution { static int T,N,L, arr[][],ans; static boolean[] v; public static void main(String[] args) { Scanner sc = new Scanner(System.in); T= sc.nextInt(); for (int tc = 1; tc
알고리즘 - 완전탐색 문제. - White와 Blue와 Red 전부 다 해보는 수밖에 없음. - 3중 for문으로 count값만 계산하여 최소값 저장. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 러시아국기같은깃발 { static int T, N, M, cnt = Integer.MAX_VALUE, wcount,rcount,bcount; static char map[][]; public static void main(String[] args) throws NumberFormatException, IOEx..
알고리즘 - 플로이드 워샬 기본문제. - 플로이드 워샬과 다익스트라의 차이점을 알아야 함. ※ 다익스트라 시간복잡도 : V E logV 플로이드 워샬 시간복잡도 : V^3 다익스트라 : 출발점에서 각 노드들간의 최소 거리. 플로이드 워샬 모든노드들의 최소 거리. * 다익스트라를 노드수 만큼 구했더니 실패한 문제. -> 이유 : 노드가100개 간선이 100000개 라서 100 * 100 * 100000 * log 100 = 시간초과인듯.. * 플로이드 워샬로 풀 경우 100^3 = 1,000,000 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays;..
알고리즘 - 4방탐색 - bfs - 최소값부터 시작하기 때문에 Priority Queue 사용 - 이미 계산한 값은 다음회차에 안해도 되기 때문에 증식한 값만 새로운 list에 저장한 후 큐의 모든 값이 계산되면(1회차) 저장한 리스트를 다시 큐에 넣어줌. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.StringTokenizer; public class 경쟁적전염_18405 { static int n, k, map[][]; static int[] ..
알고리즘 섬과 섬을 연결할 수 있는 다리의 길이가 최소인값을 찾는 알고리즘 1. dfs탐색을 통해 섬의 정보를 알아야 함. 각각 넘버링 예) 섬이 3개라면 -> 1번섬, 2번섬, 3번섬 2. 섬의 가장자리 즉, 바다와(0) 근접해있는 곳은 bfs탐색을 시작함 - 탐색 기준은 자신의 넘버와 같지않은곳을 따라가면서 탐색(count + 1) - 해당지점의 넘버링값을 보고 자신의 넘버링값과 다르다면 최소값을 갱신하고 리턴. 단, 현재의 cnt값에서 -1해줘야 함. - 모든섬이 연결되어 bfs를 돌릴 수 없는 경우도 있을 수 있기 때문에 Ans가 Max값이라면 0 출력! 아니면 Ans값 출력 * bfs를 사용한 이유 : 최소값을 찾는 알고리즘이기 때문 import java.io.BufferedReader; imp..
알고리즘 (0,0)에서 (N,M)의 위치까지의 최소 거리를 구하는 알고리즘 dfs, bfs둘 다 풀 수 있지만 최소 거리를 묻는 문제이기 때문에 bfs가 적당하다고 생각함. bfs 풀이 package baekjoon; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class 미로탐색 { static int N, M, map[][]; static int[] dr = { 1, -1, 0, 0 }; static int[] dc = { 0, 0, 1, -1 }; static int Ans = 1; public static void main(String[] args) { Scanner sc = new Sca..
알고리즘 경우의 수가 2가지 * 배달시간을 (공격 + 대기)로 나눈 나머지가 0이 아닐 때 * 나온값에 공격시간을 뺀값이 0이하면 물림 문제를 잘 파악하고 경우의 수만 찾아낼 수 있다면 쉽게 풀 수 있는 문제 package baekjoon; import java.util.Scanner; public class 사나운개 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int A, B, C, D; int P, M, N; int result = 0; int result1 = 0; int result2 = 0; A = sc.nextInt(); B = sc.nextInt(); C = sc.nextInt(); D = sc..
알고리즘 조건이 있는 완전탐색 문제. 물의 높이를 1씩 증가시키면서 탐색을 돌면 풀 수 있음. bfs탐색 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class 안전영역bfs { static int N, map[][]; static int[] dr = { -1, 1, 0, 0 }; static int[] dc = { 0, 0, -1, 1 }; static boolean[][] v; sta..
알고리즘 ※불과 사람의 배열을 따로 쓰기위해 체크배열을 각각 사용함. 불 부터 bfs를 돌리고 그다음 사람을 기준으로 bfs를 돌림. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class 불_5427 { static int T, w, h, Ans; static char[][] map; static int[] dr = { -1, 1, 0, 0 }; static int[] dc = { 0, 0, -1, 1 }; stati..
알고리즘 연결리스트를 만든 후 부분집합을 사용하여 구를 나누고 bfs를 돌려 연결되어 있는지 확인 연결되어 있다면 인구수의 최소값을 구함. package baekjoon; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class 게리맨더링_17471 { static int arr[], N, Ans = Integer.MAX_VALUE; static boolean[] v; static ArrayList[] list; public static void main(String[] args) { Scanner sc = new Scanner(System.in);..