자료구조와 알고리듬 With Java/[인프런] Algorithm 8

Chapter 08. DFS, BFS 활용

1. 합이 같은 부분집합 import java.util.*; public class Main { static String answer = "NO"; static int n, total = 0; boolean flag = false; public void DFS(int L, int sum, int [] arr){ if(flag == true) return;//재귀가 바로 끝나도록한다. if(sum > total / 2) return;// 확인할 필요가 없다. if(L == n){ if((total - sum) == sum){ answer = "YES"; flag = true; } } else{ DFS(L + 1, sum + arr[L], arr); // 무조건 + 1, arr[L]을 sum에 누적 DFS(..

Chapter 07. Recursive, Tree, Graph (DFS, BFS 기초)

1. 재귀함수 (스택 프레임) public class Main { public void DFS(int n){ if(n == 0) return; else{ System.out.println(n); DFS(n-1); } } public static void main(String[] args){ Main T = new Main(); T.DFS(5); return ; } } Note) - 실행 결과: 5 4 3 2 1 츨력 2. 이진수 출력 (재귀) import java.util.Scanner; public class Main { public void DFS(int n){ if(n == 0) return; else{ System.out.print(n + " "); DFS(n / 2); } } public sta..

Chapter 06. Sorting and Searching (정렬, 이분검색과 결정알고리즘)

1. 선택정렬 import java.util.*; public class Main { public static void main(String[] args){ Main T = new Main(); Scanner in=new Scanner(System.in); int n = in.nextInt(); int[] arr = new int[n]; for(int i = 0; i< n; ++i){ arr[i] = in.nextInt(); } for(int x : T.solution(n, arr)){ System.out.print(x + " "); } } public int[] solution(int n, int[] arr){ for(int i = 0; i < n-1; ++i){ int idx = i; for(int ..

Chapter 05. Stack, Queue (자료구조)

1. 올바른 괄호 import java.util.*; public class Main { public static void main(String[] args){ Main T = new Main(); Scanner in=new Scanner(System.in); String str = in.next(); System.out.println(T.solution(str)); return ; } public String solution(String str){ String answer = "YES"; Stack stack = new Stack(); for(char x : str.toCharArray() ){ if(x == '(') stack.push(x); else{ if(stack.isEmpty()) return..

Chapter 04. HashMap, TreeSet (해쉬, 정렬지원 Set)

1. 학급 회장 (Hash) import java.util.*; public class Main { public char solution(int n, String s){ char answer = ' '; HashMap map = new HashMap(); for(char x : s.toCharArray()){ map.put(x, map.getOrDefault(x, 0) + 1); // x의 value가 있으면 가져오고 없으면 0리턴 } int max = Integer.MIN_VALUE; for(char key : map.keySet() ){ // System.out.println(x + " " + map.get(x));// 각각의 key를 출력 if(map.get(key) > max){ max = map..

Chapter 03. Two pointers, Sliding window

1. 두 배열 합치기 (two pointers algorithm) import java.util.*; public class Main { public static void main(String[] args){ Main T = new Main(); Scanner in = new Scanner(System.in); int n = in.nextInt(); int [] A = new int[n]; for(int i = 0 ;i < n; ++i){ A[i] = in.nextInt(); } int m = in.nextInt(); int [] B = new int[m]; for(int i= 0; i < m; ++i){ B[i] = in.nextInt(); } T.solution(A, B); return ; } pub..

Chapter 02. Array (1, 2차원 배열)

1. 큰 수 출력하기 import java.util.*; public class Main { public static void main(String[] args){ Main T = new Main(); Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; ++i){ arr[i] = scan.nextInt(); } for(int x : T.solution(n, arr)){ System.out.print(x + " "); } } public ArrayList solution(int n, int[] arr) { ArrayList answer = new ArrayList(..

Chapter 01. String (문자열)

2. 대소문자 변환 import java.util.Scanner; public class Change { public static void main(String[] args) { Scanner scan = new Scanner(System.in); String str = scan.next(); System.out.println(solution(str)); } public static String solution(String str) { String answer = ""; for( char x : str.toCharArray()) { if ( Character.isLowerCase(x) ) { answer += Character.toUpperCase(x); }else { answer += Character..