계란 블로그

1. 색종이 만들기 - 실버 2 출처: 백준 2630번 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net MySol) - while문으로 작성하려 해서 결국 못 풀었다. - 재귀함수, 백트래킹을 이용해서 풀어야한다. Sol) 스터디원 코드 - 종이를 자를지 말지 결정한다. - 재귀함수 인덱스 두 가지를 넘긴다. - 두 번째 방법: cut2() -> gap은 간격의 길이 -> boolean cutFlag: 잘라야 하는지 ..

1. substring의 index 찾기 - String haystack에 대해서 String needle이 haystack의 한 부분을 차지하는 경우 그 index를 반환하라. - 부분 문자열이 아닌 경우는 -1을 반환하라 - 포인터를 써서 풀도록 문제를 가져오셨는데 내가 단순하게 substr으로 풀었다. 포인터로 푸는 부분도 복습! 출처: https://leetcode.com/problems/implement-strstr/ Implement strStr() - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your n..

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(..

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..

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..

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..

1. 동적 계획법(Dynamic Programming, DP) - 특별한 속성을 가진 복잡한 문제를 푸는 방법 - 단순한 하위 문제를 나눠서 푼다. Ex) 배낭 문제 - 물품 하나가 추가될 때마다 경우의 수가 2배씩 늘어난다. - 시간복잡도: O(2^n) 2. 메모이제이션(memoization) - 계산 결과를 캐시에 저장해둔 뒤, 나중에 재사용하는 기법 -> 처음 계산할 때, 그 결과를 캐시에 저장한다. - 메모이제이션에 "배열"이 가장 적합하다. -> 배열은 매개변수에 대해 값을 저장할 수 있다. Ex) 메모이제이션을 사용한 피보나치 함수 public static int fibonacciRecursive(int number, int [] cache) { if(number 동적 계획에서 메모이제이션이 ..