코린이의 소소한 공부노트

1. Input 1) int[] nums 2. Output 1) nums의 부분 배열에서 요소 1개를 삭제했을 때 1로만 이루어진 가장 긴 부분 배열의 길이를 반환 2) 그런 배열이 없다면 0을 반환 3. Constraint 1) 1 Output: 5 Input: nums = [1,1,1] -> Output: 2 설명: - [0, 3] 구간의 부분 배열에서 2번째를 삭제하면 [1,1,1]이 된다. - [1, 6] 구간의 부분 배열에서 4번째를 삭제하면 [1,1,1,1,1]이 된다. - [0, 2] 구간의 부분 배열에서 아무거나 1개 삭제하면 [1,1]이 된다. 5. Code class Solution { public int longestSubarray(int[] nums) { int max = 0; fo..

1. Problem - 그리디 알고리즘을 이용하여 거스름돈으로 지급할 동전의 최소한의 개수를 구해보자. - 그리디 알고리즘은 가장 큰 것부터 또는 가장 작은 것부터 선택하며 최적의 답을 찾아가는 알고리즘으로, 탐욕법이라고도 불린다. - 그리디 알고리즘은 정렬, 다이나믹 프로그래밍과 함께 사용되는 경우가 대다수이다. - 그리디 알고리즘이 항상 최적의 답을 도출하지는 않는다. 2. Input 1) 거스름돈 액수 3. Output 1) 거스름돈을 500원, 100원, 50원, 10원짜리 동전을 이용해서 지급할 때 필요한 동전의 최소 개수 4. Example 거스름돈으로 지급해야 하는 금액: 947원 // 500 < 947 < 1000 500원: 1 // 남은 금액: 447원 // 400 < 447 < 500 ..

게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다. 편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자. 1. 입력 - 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. - 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 ..

2*n 크기의 직사각형을 1*2, 2*1, 1*1 타일로 채우려고 한다. 1. 입력 - 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000,000) - n이 직사각형의 가로다. 2. 출력 - 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다. 3. 예제 4. 코드 1) 잘 안풀려서 제시된 c++ 코드를 java로 바꿔서 돌려본 코드 import java.util.*; class Main{ public static void main(String[] args){ int n = new Scanner(System.in).nextInt(); long[] d = new long[n+1]; System.out.print(dp(n, d)); } static lo..

3*n 크기의 직사각형을 1*2, 2*1 타일로 채우려고 한다. 1. 입력 - 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 30) - n이 직사각형의 가로다. 2. 출력 - 첫째 줄에 경우의 수를 출력한다. 3. 예제 4. 코드 1) 잘 안풀려서 제시된 c++ 코드를 java로 바꿔서 돌려본 코드 import java.util.*; class Main{ public static void main(String[] args){ int n = new Scanner(System.in).nextInt(); int[] d = new int[n+1]; System.out.print(dp(n, d)); } static int dp(int x, int[] d){ if(x%2==1) return 0; if(x==0) ret..

2*n 크기의 직사각형을 1*2, 2*1, 2*2 타일로 채우려고 한다. 1. 입력 - 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) - n이 직사각형의 가로다. 2. 출력 - 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 3. 예제 4. 코드 import java.util.*; class Main{ public static void main(String[] args){ int n = new Scanner(System.in).nextInt(); if(n>2){ int[] d = new int[n]; d[0] = 1; d[1] = 3; for(int i=2 ; i

2*n 크기의 직사각형을 1*2, 2*1 타일로 채우려고 한다. 1. 입력 - 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) - n이 직사각형의 가로다. 2. 출력 - 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 3. 예제 4. 코드 import java.util.*; class Main{ public static void main(String[] args){ int n = new Scanner(System.in).nextInt(); if(n>2){ int[] d = new int[n]; d[0] = 1; d[1] = 2; for(int i=2 ; i

1. Input 1) String s 2) String t 2. Output 1) s가 t의 subsequence라면 true, 아니면 false를 반환 - subsequence란 문자가 연속적이지 않아도 차례대로 다른 문자열에 순서대로 있는 것을 말한다. 예를 들면 “ace"는 "abcde"의 subsequence지만 ”aec"는 아니다. 3. Constraint 1) 0

1. Input 1) int rowIndex 2. Output 1) 파스칼 삼각형에서 위에서 rowIndex+1층에 위치한 수를 리스트에 담아 반환 3. Constraint 1) 0

1. Input 1) int numRows 2. Output 1) numRows층으로 구성된 파스칼 삼각형을 리스트의 리스트로 반환 3. Constraint 1) 1