본문 바로가기

반응형

Java/Java 알고리즘 인프런

(110)
자바 알고리즘 복습 (2) 1. 학급 회장(해쉬)import java.util.*; public class Main { public static void main(String[] args){ Scanner in=new Scanner(System.in); int cnt = in.nextInt(); in.nextLine(); char[] arr = new char[cnt]; arr= in.nextLine().toCharArray(); HashMap map = new HashMap(); for(int i=0;imap){ char c=' '; int max=Integer.MIN_VALUE; for(Map.Entry entry : map.entrySet()){ if(entr..
자바 알고리즘 입문 복습 (1) 1. 문자찾기import java.util.Scanner;public class Main { public static void main(String[] args){ Scanner sc=new Scanner(System.in); String s = sc.nextLine(); char c=sc.nextLine().charAt(0); // Main sol = new Solution();// System.println(sol(c,s)); System.out.println(Solution(c,s)); } public static int Solution(char c, String str){ int answer = 0; for(int i=0;i2. 대소문자 변환impo..
5. 퍼즐게임 (+ 2차원 DP) // 퍼즐게임 // 2장의 카드가 남을 때 까지 반복해서 뽑는다 -> (뽑은 카드)*(뽑은 왼쪽 카드)*(뽑은 오른쪽 카드) 결과를 더한다. // 나열된 카드 중에서 맨 왼쪽 카드와 맨 오른쪽 카드는 뽑아서는 안된다. // 맨 마지막 동작을 하고 나면, 두 장의 카드가 남는다. // 당신의 목표는 동작을 모두 하고나서, 각 동작의 점수의 합이 최소가 되도록 동작 +) 세련된 풀이 : 동적계획법 dy[i][j] : i번째부터 j번째까지의 까지의 부분수열을 게임동작했을 때 얻을 수 있는 최소 점수 package Q5; import java.util.*; class Main2 { public int solution(int[] nums){ int n=nums.length; int[][] dy = new int[..
4. 사과 먹기 (+BFS) DFS는 스택을 이용한 깊이 우선 탐색 BFS는 큐를 이용한 너비 우선 탐색 DFS를 이용한 풀이 : N이 커지면, 타임리밋 발생 -> BFS 이용하도록 변경 package Q4; public class Main { public static void main(String[] args) { // 하루 동안 먹을 수 있는 사과의 개수입니다. // 1) 사과 한 개를 먹는다. // 2) 현재 있는 사과의 개수가 2로 나누어 떨어지는 개수라면 그 절반(사과개수 / 2)을 먹는다. 3) 현재 있는 사과의 개수가 3으로 나누어 떨어진다면 (사과개수 / 3) * 2 개의 사과를 먹는 다. // 현수에게 N개의 사과가 주어지면 현수가 위 3가지 중 하나를 선택해서 먹을 때 최소 몇 일만 에 사과를 모두 먹을 수 있는지..
3. 그래프 최대점수 (+DFS) +) 세련된 풀이 : DFS 각 노드를 무한 반복해, ch 배열로 첫 번째로 방문 했는지를 확인 import java.util.*; class Edge { public int vex; public int cost; Edge(int vex, int cost) { this.vex = vex; this.cost = cost; } } class Main { public int answer=0; public ArrayList graph; public int[] ch; public void DFS(int cur, int time, int sum, int[] nums){ if(time
2. 카드 점수 (+슬라이딩 윈도우) DFS 이용한 풀이 package Q2; import java.util.Arrays; public class Main { //카드 점수 //카드 종류와 뽑을 카드 수가 주어지면 //가장 왼쪽 또는 가장 오른쪽 끝에 있는 카드를 가져온다. //가져온 카드의 총 합이 가장 큰 경우를 출력 public static void main(String[] args) { // int[] nums={3,2,5,6,7,1}; // int k=3; //int[] nums={3, 1, 4, 5, 4, 1, 2, 5}; //int k=5; int[] nums={6, 7, 1, 3, 1, 4, 3, 1, 1, 5, 4, 1, 2, 5}; int k=10; System.out.println(solve(nums, k)); } sta..
1. 빈도수 정렬 (+Hash) package Q1; import java.util.*; public class Main { //1. 빈도수 정렬 public static void main(String[] args) { //String str="aaAAcccbbbBB"; String str="kdkDKKGkdkgks"; solve(str); } public static String solve(String str){ Map map = new HashMap(); String answer=""; for(char c: str.toCharArray()){ map.put(c, map.getOrDefault(c, 0)+1); } //Map.Entry로 List만들어 정렬하기 List entryList= new LinkedList(map.entryS..
[Ch.09 - Greedy] 07. 원더랜드 (+ 최소스패닝트리 : 크루스칼, Union & Find) 7. 원더랜드(최소스패닝트리) 최소스패닝 트리 = 최소비용신장트리 MST (Minimum Spanning Tree) 설명 원더랜드에 문제가 생겼다. 원더랜드의 각 도로를 유지보수하는 재정이 바닥난 것이다. 원더랜드는 모든 도시를 서로 연결하면서 최소의 유지비용이 들도록 도로를 선택하고 나머지 도로는 폐쇄하려고 한다. 아래의 그림은 그 한 예를 설명하는 그림이다. 위의 지도는 각 도시가 1부터 9로 표현되었고, 지도의 오른쪽은 최소비용 196으로 모든 도시를 연결하는 방법을 찾아낸 것이다. 입력 첫째 줄에 도시의 개수 V(1≤V≤100)와 도로의 개수 E(1≤E≤1,000)가 주어진다. 다음 E개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 도시와 B번 도시가 유..

반응형